Insertion Sort Algorithm in Array
Insertion Sort Algorithm in Array is a part of Learning Data Structure Series. In the last article of Bubble Sort Algorithm in Array we learnt to sort the elements in increasing order by bubbling the largest element of the array to its correct location followed by bubbling second largest element and so on.
As we know sorting means rearranging the data in ascending or descending order. Insertion Sort Algorithm inserts smallest element to its correct location first. In next phase, it inserts second smallest element to its correct location and so on. Lets now learn how to execute Insertion Sort Algorithm in Array.
Insertion Sort Algorithm in Array
Let us consider an array DATA having n elements, DATA, DATA, …., DATA[N]. Insertion sort inserts –∞ value at 0th location of array. In each pass it places one element to its correct location. So N passes will require to sort N elements.
In Pass 1, DATA will be sorted. In Pass 2 DATA is inserted either before DATA or after DATA, so that DATA and DATA will be sorted. This continues till the array is sorted like DATA, DATA, . . ., DATA[N].
The sorting algorithm for Insertion Sort Algorithm in Array is as follows.
INSERTION (A, N)
1. Set DATA= -∞ 2. Repeat steps 3 to 5 for I=2 to N 3. Set TEMP:=DATA[I] PTR=I-1 4. Repeat while TEMP<DATA[PTR] a) Set DATA[PTR+1]=DATA[PTR] b) Set PTR=PTR-1 [End of while Loop] 5. Set DATA[PTR+1]=TEMP [End of For loop] 6. Return
In above algorithm DATA is an unsorted array with N elements. TEMP is a variable which holds the value of next element. The variable PTR is acting as index variable for array DATA. Lets now understand this algorithm with example.
In above array DATA we have 8 unsorted elements. The insertion sort algorithm will work as follows.
TEMP = 70 and PTR = 0
DATA[PTR] = -∞
TEMP < DATA[PTR] is False
70 will remain at its position
In each phase, we are comparing the next element with the previous elements. The element under consideration is stored in variable TEMP. We compare TEMP with each previous element DATA[PTR]. If TEMP is less than DATA[PTR] then we swap the elements with each other. We then decrement PTR by 1 and again compare it with new DATA[PTR].
So the next passes will be like
Here 30 < 70. So 30 moves forward.
Here 40 < 70 and 40 > 30. So 40 moves in between 30 and 70.
Here 10 < 70, 40 and 30. So 10 moves forward of 70, 40 and 30.
Now 80 !< 70 . So there will be no change.
Here 20 < 80, 70, 40 and 30 But 20 > 10. So it got placed in between 10 and 30.
Here 60 < 70 and 80 But 60 > 40 . So 60 got placed in between 40 and 70.
Here 50 < 80, 70 and 60 But 50 > 40. So 50 will be placed in between 40 and 60.
Now observe that, we have 8 elements in array and the array got sorted in 8 passes.
In this way Insertion Sort Algorithm sorts the array from left by inserting the smallest element.
Complexity of Insertion Sort Algorithm in Array
Insertion sort is the best sorting algorithm when number of elements are less. But the worst case occurs when array is in reverse order. In such case, the inner loop will be executed for I-1 times (maximum comparisons will be there). In average case there will be approximately (I-1)/2 comparisons in the inner loop.
So Worst case complexity is n(n-1)/2
Whereas Average case complexity is n(n-1)/4
This sorting algorithm is frequently used when N is small. But if N is large then efficiency of algorithm decreases. This calls for an algorithm which is efficient even to sort large arrays.
In my next article in Learning Data Structure Series we learn about Selection Sort Algorithm in Array and to maintain Worst and Average Case Complexities as equal to provide efficient solution to sort large arrays.