Goseeko blog

What is Insertion sort?

Insertion style is a decrease & conquer technique application. Moreover, It is a sort based on comparison in which the sorted array is constructed on one entry at a time.

Insertion sorting is a very basic process for sorting numbers in an ascending or descending order. Moreover, The gradual method is accompanied by this method. On the other hand, It can contrast with the method of sorting cards at the time of playing a game.

In addition, The numbers that are needed to be sorted are known as keys. On the other hand, there is the insertion sort method algorithm.

Algorithm:

Algorithm: Insertion-Sort (A)

for j = 2 to A.length

key = A[j]

// Insert A[j] into the sorted sequence A[1.. j – 1]

i = j – 1

while i > 0 and A[i] > key

A[i + 1] = A[i]

i = i -1

A[i + 1] = key

Analysis:

This algorithm’s run time is very dependent on the input given.

In addition, If the numbers given are sorted, this algorithm runs in O(n) time. On the other hands, If the numbers given are in reverse order, the algorithm runs in O(n2) time.

Example of insertion sort:

For instance, Using insertion sort to sort the following list of elements:

89, 45, 68, 90, 29, 34, 17

89  |45  68  90  29  34  17

45  89  |68  90  29  34  17

45  68  89  |90  29  34  17

45  68  89  90  |29  34  17

29  45  68  89  90  | 34  17

29  34  45  68  89  90  |17

17  29  34  45  68  89  90

Application:

In the following instances, the insertion sort algorithm is used:

●  Firstly, When only a few elements are in the list.

●  Lastly, When there are few elements for sorting.