11.12 Insertion Sort
Insertion sort is another simple, but inefficient, sorting algorithm. The first iteration of this algorithm takes the second element in the array and, if it’s less than the first element, swaps it with the first element. The second iteration looks at the third element and inserts it into the correct position with respect to the first two, so all three elements are in order. At the ith iteration of this algorithm, the first i elements in the original array will be sorted.
Consider as an example the following array, which is identical to the one used in the discussion of selection sort.
34 56 14 20 77 51 93 30 15 52A program that implements the insertion sort algorithm will first look at the first two elements of the array, 34 and 56. These are already in order, so the program continues. If they were out of order, the program would swap them.
In the next iteration, the program looks at the third value, 14. This value is less than 56, so the program stores 14 in a temporary variable and moves 56 one element to the right. The program then checks and determines that 14 is less than 34, so it moves 34 one element to the right. The program has now reached the beginning of the array, so it places 14 in element 0. The array now is
14 34 56 20 77 51 93 30 15 52In the next iteration, the program stores 20 in a temporary variable. Then it compares 20 to 56 and moves 56 one element to the right because it’s larger than 20. The program then compares 20 to 34, moving 34 right one element. When the program compares 20 to 14, it observes that 20 is larger than 14 and places 20 in element 1. The array now is
14 20 34 56 77 51 93 30 15 52Using this algorithm, at the ith iteration, the first i elements of the original array are sorted, but they may not be in their final locations—smaller values may be located later in the array.
11.12.1 Insertion Sort Implementation
The file insertionsort.py defines:
Function
insertion_sort, which implements the insertion sort algorithm, andFunction
mainto test theinsertion_sortfunction.
Function main (lines 22–27) is identical to main in Section 11.11.1 except that line 26 calls function insertion_sort to sort the array’s elements into ascending order.
The following is a sample output of the program. The -- notation below a given number indicates the values that have been sorted so far after the algorithm’s specified pass.
Unsorted array: [34 56 14 20 77 51 93 30 15 52]
after pass 1: 34 56* 14 20 77 51 93 30 15 52
--
after pass 2: 14* 34 56 20 77 51 93 30 15 52
-- --
after pass 3: 14 20* 34 56 77 51 93 30 15 52
-- -- --
after pass 4: 14 20 34 56 77* 51 93 30 15 52
-- -- -- --
after pass 5: 14 20 34 51* 56 77 93 30 15 52
-- -- -- -- --
after pass 6: 14 20 34 51 56 77 93* 30 15 52
-- -- -- -- -- --
after pass 7: 14 20 30* 34 51 56 77 93 15 52
-- -- -- -- -- -- --
after pass 8: 14 15* 20 30 34 51 56 77 93 52
-- -- -- -- -- -- -- --
after pass 9: 14 15 20 30 34 51 52* 56 77 93
-- -- -- -- -- -- -- -- --
Sorted array: [14 15 20 30 34 51 52 56 77 93]
Function insertion_sort
Lines 6–20 declare the insertion_sort function. Lines 9–20 loop over the elements at indices 1 up to len(data) items in the array. In each iteration, line 10 declares and initializes variable insert, which holds the value of the element that will be inserted into the sorted portion of the array. Line 11 declares and initializes the variable move_item, which keeps track of where to insert the element. Lines 14–17 loop to locate the correct position where the element should be inserted. The loop will terminate either when the program reaches the front of the array or when it reaches an element that’s less than the value to be inserted. Line 19 moves an element to the right in the array, and line 17 decrements the position at which to insert the next element. After the loop ends, line 19 inserts the element into place.
1 # insertionsort.py2 """Sorting an array with insertion sort."""3 import numpy as np4 from ch11utilities import print_pass56def insertion_sort(data):7 """Sort an array using insertion sort."""8 # loop over len(data) - 1 elements9 for next in range(1, len(data)):10 insert = data[next] # value to insert11 move_item = next # location to place element1213 # search for place to put current element14 while move_item > 0 and data[move_item - 1] > insert:15 # shift element right one slot16 data[move_item] = data[move_item - 1]17 move_item -= 11819 data[move_item] = insert # place inserted element20 print_pass(data, next, move_item) # output pass of algorithm2122 def main():23 data = np.array([35, 73, 90, 65, 23, 86, 43, 81, 34, 58])24 print(f'Unsorted array: {data} ')25 insertion_sort(data)26 print(f' Sorted array: {data} ')2728 # call main if this file is executed as a script29 if __name__ == '__main__':30 main()
11.12.2 Big O of the Insertion Sort
The insertion sort algorithm also runs in O(n2) time. Like selection sort, the implementation of insertion sort contains two loops. The for loop iterates len(data) - 1 times, inserting an element into the appropriate position among the elements sorted so far. For the purposes of this application, len(data) - 1 is equivalent to n – 1 (as len(data) is the size of the array). The while loop (lines 14–17) iterates over the preceding elements in the array. In the worst case, this while loop will require n – 1 comparisons. Each individual loop runs in O(n) time. In Big O notation, nested loops mean that you must multiply the number of comparisons. For each iteration of an outer loop, there will be a certain number of iterations of the inner loop. In this algorithm, for each O(n) iterations of the outer loop, there will be O(n) iterations of the inner loop. Multiplying these values results in a Big O of O(n2).
Self Check
(True/False) Like the selection sort algorithm, the insertion sort algorithm has linear run time.
Answer: False. Both algorithms have quadratic run time.(True/False) Each iteration of the selection sort algorithm inserts one value into sorted order among the values that have been sorted so far.
Answer: True.