What is insertion sort? Trace and sort the following data using the insertion sorting algorithm.

90, 56, 80, 10, 22, 21, 45, 9

This answer is restricted. Please login to view the answer of this question.

Login Now

In insertion sort, an element get compared and inserted into the correct position in the list. To apply this sort, we must consider one part of the list to be sorted and other to be unsorted.

To begin, consider the first element to be sorted position and the other elements of the list are unsorted. Now compare each element from the unsorted position with the element in the sorted portion. Then insert it in the correct position in the sorted part.

Here we will sort and trace the following data using insertion sort:

{90, 56, 80, 10, 22, 21, 45, 9}

Solution:

Array Position 0 1 2 3 4 5 6 7
Initial State 90 56 80 10 22 21 45 9
After a[0…1] is sorted (pass 1) 90 56 80 10 22 21 45 9
After a[0…2] is sorted (pass 2) 56 90 80 10 22 21 45 9
After a[0…3] is sorted (pass 3) 56 80 90 10 22 21 45 9
After a[0…4] is sorted (pass 4) 10 56 80 90 22 21 45 9
After a[0…5] is sorted (pass 5) 10 22 56 80 90 21 45 9
After a[0…6] is sorted (pass 6) 10 21 22 56 80 90 45 9
After a[0…7] is sorted (pass 7) 10 21 22 45 56 80 90 9
After a[0…8] is sorted (pass 8) 9 10 21 22 45 56 80 90
If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .