Given the sequence 9 2 3 8 7 4 5 6 List all the element comp

Given the sequence 9, 2, 3, 8, 7, 4, 5, 6 List all the element comparisons made by insertion sort in the corresponding order. Use to denote a comparison of a and b. If the algorithm compares A[i] with A[j], you should write , rather than . For example, if the algorithms compares the first element with the fourth element, you should write , rather than .

Solution

Insertion sort starts at the beginning of the array and checks each element with the next and swaps them if necessary.

Begin the insertion sort:

1: 9,2,3,8,7,4,5,6

2: 9 2 3 8 7 4 5 6 - 2^nd element to be soretd

3: <2 9> 3 8 7 4 5 6 – swap the elements

4: 2 <9 3> 8 7 4 5 6 – comparison between <9,3>

5: 2 3 9 8 7 4 5 6 - swap <9,3>

6:2 3 <9 8 > 7 4 5 6- comparison between <9,8>

7: 2 3 8 9 7 4 5 6 – swap <9,8>

8:2 3 8 <9 7> 4 5 6 – comparision between <9,7>

9: 2 3 <8 7> 9 4 5 6 – comparison between <8,7>

10: 2 3 7 8 9 4 5 6 – swap <8,7>

11: 2 3 7 8 <9,4> 5 6 – comparison between <9,4> after <8,4> after <7,4>

12: 2 3 4 7 8 9 5 6 – swap done here

13: 2 3 4 7 8 9 5 6 – comparison between <9,5> after <8,5> after <7,5>

14: 2 3 4 5 7 8 9 6 – swap here

15: 2 3 4 5 7 8 9 6 – comparison between <9,6> after <8,6> after <7,6>

16: 2 3 4 5 6 7 8 9 sorting done

Here in the comparison

For(int i=1; i<array.length; i++)

For(int j=I; j>0 && (array[j].compareTo(array[j-1])<0); j--)

Swap(array,j,j-1);

}