Question

1. Insertion sort for 12, 2, 3, 21, 11, 10,8

2. Bubble sort for 12, 2, 3, 21, 11, 10,8

3. selection sort for 12, 2, 3, 21, 11, 10,8

analysis of algorithm

Answer 1

Assuming all the sorting techniques are sorting the data in ascending order.

1) Insertion Sort steps: (Inserting one by one element and sorting like playing cards)

(i) 2, 12, 3, 21, 11, 10, 8 <12 inserted> No. of comparison:1 (comarison between 12 and 2)

(ii) 2, 3, 12, 21, 11, 10, 8 <3 inserted> No. of comparison: 2 (comarison between 12 and 3, then 2 and 3)

(iii) 2, 3, 12, 21, 11, 10, 8 <21 inserted> No. of comparison: 1 (comarison between 12 and 21)

(iv) 2, 3, 11, 12, 21, 10, 8 <11 inserted> No. of comparison: 3 (11 will be compared with 21, 12, 3)

(v) 2, 3, 10, 11, 12, 21, 8 <10 inserted> No. of comparison: 4 (10 will be compared with 21, 12, 11, 3)

(vi) 2, 3, 8, 10, 11, 12, 21 <8 inserted> No. of comparison: 5 (8 will be compared with 21, 12, 11, 10, 3)

Total No. of comparisons: 16

2) Buble Sort steps:

(i) 2, 3, 12, 11, 10, 8, 21 (Here the largest element would be bubbled up to the last slot of the array, for that there will be n - 1 = 7 -1 = 6 many compariosons).

In the next step the second largest element would be bubbled up to the second last slot of the array, which will require 6 - 1 = 5 many comparisons.

So in total number of comparisons would be : n * (n - 1) / 2 = 7 * 6 / 2 = 21 [where n is the number of elements]  

3) Selection Sort steps:

Here we are going to find max among the entire data set, which requires (n - 1) time comparison. Then in the next step we try to find second max from the rest of the data, which requires (n - 2) time comparison and this will go on untill only a single data is left. which turns out to be same as buble sort :  n * (n - 1) / 2 = 7 * 6 / 2 = 21 [where n is the number of elements]

Here the first step is shown:

(i) 12, 2, 3, 8, 11, 10, 21 <swaping takes place between the last element and the max element>