Algorithm and Example of Insertion Sort

Insertion Sort

Q) Explain the Insertion sort algorithm with a suitable example.

• Insertion sort is based on the principle of inserting the element to the proper position in the previously sorted list. if take (N-1)passes to sort N element of the array.
• In this sort, the first element is considered to be sorted and the remaining elements are in the unsorted list. One element from the unsorted list is picked-up and inserted in the sorted list to its proper position. This process is continued until the unsorted list is finished.

Initially: Data[1] is itself sorted. And remaining elements are unsorted.

Pass1:  Data[2] is inserted either before Data[1] or after Data[1] so that Data[1] and Data[2] are sorted.

Pass2: Data[3] is inserted to its proper position in Data[1] Data[2] so the Data[1], Data[2] and Data[3] are sorted.

Pass3: Data[4] is inserted to its proper position in Data[1], Data[2], Data[3]so that Data[1], Data[2], Data[3] and Data[4] are sorted.

.

.

.

PassN-1: Data[N] is inserted in Data[1], Data[2]...Data[N-1] so that Data[1], Data[2]...Data[N] are sorted.

Image Source ~ Crafted With ©Ishwaranand - 2020 ~ Image by ©Ishwaranand

Algorithm: Insertion_sort(Data[],N)

• This is the algorithm for inserted sort to sort the array in ascending order.
• Data[]-Array of elements
• N-size ofarray
• i,j-index variable
• temp-temporary variable

Step 1 : Start

Step 2 : Repeat the steps 3, 4, 5 and 6 for i = 2 to N

Step 3 : Set temp = Data[i]

Step 4 : Set j = i - 1

Step 5 : Repeat while j > 0 and temp < data[i]

      a) Set Data[j+1] = Data[j]

      b) Set j = j - 1

Step 6 : Set Data[j+1] = temp

Step 7 : Stop

Example Insertion Sort

Consider the following array with 6 elements.

Red is Sorted

Black is unsorted

1	2	3	4	5	6
50	30	10	40	60	20

Initially: Consider data[1] is sorted and the remaining list is unsorted.

1	2	3	4	5	6
50	30	10	40	60	20

Pass 1 : As Data[2] < Data[1] hence, insert Data[2] before Data[1]

Before Insertion

1	2	3	4	5	6
50	30	10	40	60	20

After Insertion

1	2	3	4	5	6
30	50	10	40	60	20

Pass 2 : As Data[3] < Data[2], Data[1] hence, insert Data[3] before Data[1]

Before Insertion

1	2	3	4	5	6
30	50	10	40	60	20

After Insertion

1	2	3	4	5	6
10	30	50	40	60	20

Pass 3 : As Data[4] < Data[3], hence, insert Data[4] before data[3]

Before Insertion

1	2	3	4	5	6
10	30	50	40	60	20

After Insertion

1	2	3	4	5	6
10	30	40	50	60	20

Pass 4 : As data[5] > Data[4], hence, Data[5] remain at the same position

Before Insertion

1	2	3	4	5	6
10	30	40	50	60	20

After Insertion

1	2	3	4	5	6
10	30	40	50	60	20

Pass 5 : Data[6] < Data[5], Data{4], Data[3], Data[2] hence, Data[6] is before Data[2]

Before Insertion

1	2	3	4	5	6
10	30	40	50	60	20

After Insertion

1	2	3	4	5	6
10	20	30	40	50	60