Algorithms For Dummies

Switching to an insertion sort

An insertion sort works by using a single item as a starting point and adding items 

to the left or right of it based on whether these items are less than or greater than 

the selected item. As the number of sorted items builds, the algorithm checks new 

items against the sorted items and inserts the new item into the right position in 

the list. An insertion sort has a best-case sort speed of O(n) and a worst case sort 

speed of O(n

2

).

---

CHAPTER 7

  Arranging and Searching Data 

     137

An example of best-case sort speed is when the entire dataset is already sorted 

because  the  insertion  sort  won’t  have  to  move  any  values.  An  example  of  the 

worst-case sort speed is when the entire dataset is sorted in reverse order because 

every insertion will require moving every value that already appears in the out-

put. You can read more about the math involved in this sort at 

https://www.

khanacademy.org/computing/computer-science/algorithms/insertion- 

sort/a/analysis-of-insertion-sort

.

The insertion sort is still a brute-force method of sorting items, but it can require 

fewer comparisons than a selection sort. Here’s an example of an insertion sort:

data = [9, 5, 7, 4, 2, 8, 1, 10, 6, 3]

  

for scanIndex in range(1, len(data)):

    temp = data[scanIndex]

  

    minIndex = scanIndex

  

    while minIndex > 0 and temp < data[minIndex - 1]:

        data[minIndex] = data[minIndex - 1]

        minIndex -= 1

    data[minIndex] = temp

    print(data)

  

[5, 9, 7, 4, 2, 8, 1, 10, 6, 3]

[5, 7, 9, 4, 2, 8, 1, 10, 6, 3]

[4, 5, 7, 9, 2, 8, 1, 10, 6, 3]

[2, 4, 5, 7, 9, 8, 1, 10, 6, 3]

[2, 4, 5, 7, 8, 9, 1, 10, 6, 3]

[1, 2, 4, 5, 7, 8, 9, 10, 6, 3]

[1, 2, 4, 5, 7, 8, 9, 10, 6, 3]

[1, 2, 4, 5, 6, 7, 8, 9, 10, 3]

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]