Tell me something about 'insertion sort'?

Software Development
#1

Tell me something about ‘insertion sort’?

#2

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

#3

Insertion sort is similar to arranging the documents of a bunch of students in order of their ascending roll number.

Starting from the second element, we compare it with the first element and swap it if it is not in order. Similarly, we take the third element in the next iteration and place it at the right place in the sublist of the first and second elements (as the sublist containing the first and second elements is already sorted).

We repeat this step with the fourth element of the list in the next iteration and place it at the right position in the sublist containing the first, second and the third elements. We repeat this process until our list gets sorted. So, the steps to be followed are:

  1. Compare the current element in the iteration (say A) with the previous adjacent element to it. If it is in order then continue the iteration else, go to step 2.
  2. Swap the two elements (the current element in the iteration (A) and the previous adjacent element to it).
  3. Compare A with its new previous adjacent element. If they are not in order then proceed to step 4.
  4. Swap if they are not in order and repeat steps 3 and 4.
  5. Continue the iteration.