Insertion sort and Quick sort

Question

In the lectures and in the notes, We examined the exact Worst-case cost of sorting five elements using two different sorting algorithms: Insertion sort and Quick sort Merge Sort and an ad hoc optimal algorithm for sorting exactly five items. In this problem, you are being asked to give the exact cost of sorting five items using other approaches. And In all parts of this problem, “cost” means the number of comparisons performed between two inputs items.

1. What is the exact worst-case cost of sorting five elements using insertion sort?
2. And What is the exact worst-case cost of sorting five elements using quick sort?
3. What is the exact expected cost of sorting five elements using quick sort? assuming all 5! Permutations are equally likely. (For this part, it is fine to use a calculator or write and run a computer program.

 

Summary

1. 1.  Using insertion sort, the Worst-case cost of sorting five elements is 10.
   2.  And Using Quicksort, the worst-case cost of sorting five elements is 14.
   3.  Using Quicksort, the excepted cost of sorting five elements items is 7.4

Explanation

Here we are going to compare the first number with the second number. so If first number is bigger than the second, we are going to place the second number in the position of the first. For example, let’s consider a five number for insertion sort.

(a)

Numbers are 5,4,3,2,1. We have to sort this in ascending order. We are going to count a number every time we replace the digit.

• • • 5 4  3  2  1            Count 0
    • [5  4]  3  2  1        let’s compare the first two numbers. Here 4 is less than 5 so exchange their position. This is Count 1.
    • 4 [5  3]  2  1         compare 5 with 3, here 3 is less than 5 so we will exchange their positions. This is Count 2.
    • [4 3]  5 2  1          compare 4 and 3, here 3 is less than 4, so we will change their positions. This is count 3.
    • 3  4  [5   2]  1       Now compare 5 and 2, here 2 is less than 5, so exchange their positions. This is Count 4.
    • 3 [4  2]  5  1         Compare 4 with 2, now 2 is smaller so exchange their position. This is Count 5.
    • [3 2]  4  5  1         compare 3 and 2, here 2 is less than 3, so exchange their positions. This is Count 6.
    • 2 3  4  [5  1]         compare 5 and 1, here 1 is less than 5, so exchange their positions. This is Count 7.
    • 2 3  [4  1]  5         compare 4 and 1, here 1 is less than 4, so exchange their positions. This is Count 8.
    • 2 [3  1]  4  5         compare 3 and 1, here 1 is less than 3, so exchange their positions. This is Count 9.
    • [2 1]  3  4  5         compare 2 and 1, here 1 is less than 2, so exchange their positions. This is Count 10.

Here we get our ascending sequence by Insertion sort by count 10.

 

(b)

Worst-case complexity by Quicksort. For this, we have one formula i.e.

Cost = [ n + (n-1) + (n-2) + (n-3) +……..+2]

In the above question we are given n=5.

Put the value of n=5 in the given formula.

Cost = [5 + (5-1) + (5-2) + (5-3) +……..+2]

=  [5 + 4 + 3 +2]

= 14

Worst-case of five elements is 14 by Quick sort.

(c)

Excepted cost of sorting five elements using quicksort.

     E[X] = ∑ _i=1^n-1       ∑^n-i _k=1

here n=5

put the value of n=5 in the given formula.

E[X]=  ∑ ⁴_i=1      ∑ ⁵⁼ⁱ_k=1

=   2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2

= (4*1) + (3*) + (2*) +

= 4 + 2 + 1 + 0.4

= 7.4

 

Also read, Make a flowchart of MICE (Meeting Incentive Convention Exhibition).