Insert algorithm (Insertion Sort)

Sort insertion is a sorting algorithm based on in-place comparison. Here, a sub-list is always maintained in sorted form. Inserting is inserting an element into the sorted list of children. The element is inserted in the appropriate position so that the list is still in order.

What is sort insertion (Insertion Sort)?

With the array data structure, we imagine that: the array consists of two parts: a sorted list of children and the other part are unordered elements. The insertion sort algorithm will perform a continuous search through that array, and unordered elements will be moved and inserted into the appropriate position in the sub-list (of the same array).

This algorithm is not suitable for use with large data sets when the case complexity is worst and the average case is Ο (n2) where n is the number of elements.

How to solve the insertion arrangement?

For example, we have an array of unordered elements:

Picture 1 of Insert algorithm (Insertion Sort)

The insertion sort algorithm compares the first two elements:

Picture 2 of Insert algorithm (Insertion Sort)

The algorithm found that both 14 and 33 were in ascending order. Now, 14 is in the sorted list of children.

Picture 3 of Insert algorithm (Insertion Sort)

The insertion algorithm continues to move to the next element and compares 33 and 27.

Picture 4 of Insert algorithm (Insertion Sort)

And see that 33 is not in the right position.

Picture 5 of Insert algorithm (Insertion Sort)

Algorithm to insert and swap positions of 33 and 27. Also check all elements in the sorted list. Here, we see that in this sub-list only one element 14 and 27 is greater than 14. Therefore the sub-list remains the same after the swap.

Picture 6 of Insert algorithm (Insertion Sort)

Now in the list of children we have two values 14 and 27. Continue to compare 33 with 10.

Picture 7 of Insert algorithm (Insertion Sort)

These two values are not in order.

Picture 8 of Insert algorithm (Insertion Sort)

So we swap them.

Picture 9 of Insert algorithm (Insertion Sort)

Swapping leads to 27 and 10 in no order.

Picture 10 of Insert algorithm (Insertion Sort)

So we also exchange them.

Picture 11 of Insert algorithm (Insertion Sort)

We see again that 14 and 10 are not in order.

Picture 12 of Insert algorithm (Insertion Sort)

And we continue to swap these two numbers. Finally, after the third loop we have 4 elements.

Picture 13 of Insert algorithm (Insertion Sort)

The above process will continue until all unordered values are sorted into the sorted child list.

Next we explore the programming aspect of insertion sorting algorithm.