Insertion Sort

excerpt: How does insertionsort work? What is the time complexity? When can we use insertionsort? tags: nested-loop-with-for-and-while shift-right forward-and-backward-nested-loops

The goal is to order a list of integers in ascending order. The insertion sort is quadratic in time complexity but simple. It can outperform faster but more complicated algorithms for very small arrays.

The shift right is a basic building block for insertion sort. For example, the array [1, 2, 3] shifted right by one unit will be [3, 1, 2]. The implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def shift_right(a)
  n = a.size
  
  element = a[n-1]
  
  (n-1).downto(0) do |i|
    a[i] = a[i-1]
  end
  
  a[0] = element
end

a = [1, 2, 3]

p shift_right(a)
p a

The last element is saved in the variable called element. The array is processed from the right because we have a free slot to the right, this gets the value of the preceding element. The last element is copied to the first location outside the loop.

Insertionsort in Arrays

An item is taken from the input list and inserted into the proper position in a sorted output list.

  1. Iterate from 0 to array size - 1
  2. Move item i into position in the sorted part of the array.
    • Find the index j where j < i and values[j] > values[i]
    • Move the item into position j
  3. Repeat steps 1 and 2 for all elements in the array.

Iterate through the items in the array, the index i separates the items that have been sorted from those that are unsorted. The items with an index < i have already been sorted and those with an index >= i have not yet been sorted.

As i goes from 0 to the last index in the array, the item at index i is moved into the proper position in the sorted part of the array. The item’s position is found by looking through the already sorted items and finding the first item that is > values[i].

The element at values[i] is moved into its new position. This step can be time consuming. Suppose the item’s new index should be j. In that case, the items must be moved between indices j and i one position to the right to make room for the item at position j.

The key steps of the algorithm is shown in the diagrams. The first image shows the unsorted array. The second image shows the first four items as sorted and the code is preparing to insert the next item, 3 into the sorted part of the array. The code searches through the sorted items untils it determines the value 3 should be inserted before the value 5. The last image shows that the values 5,6 and 7 have moved to the right to make room for value 3. The value 3 is inserted and the for loop continues to insert the next item 2 into its correct position.

This algorithm sorts the items inplace so it does not require any additional space. If the array contains N items, each of the N positions in the array is considered. For each position i, it must search the previously sorted items in the array to find the ith item’s new position. It must then move the items between that location and index i one position to the right. If the item i should be moved to position j, it takes j steps to find the new location j and then i - j more steps to move items over, resulting in a total of i steps. That means in total it takes i steps to move item i into its new position.

The total run time is calculated by adding up all the steps required to position all the items.

1 + 2 + 3 + … + N = (N2 + N)/2

The run time is O(N2). This is fast enough for small arrays of size 10,000 or so. This algorithm is relatively simpler that complicated algorithms that are faster.

Implementation

Consider the list as if it was divided into two parts, one sorted and the other unsorted. At the beginning the sorted part is empty.

  1. Select the first element of the unsorted part of the list
  2. Insert such an element into its correct position in the sorted part of the list.
  3. Change where you divide the array from the sorted part to the unsorted part.

Mechanism is similar to inserting (adding) an element to an array list: Shift all elements ahead by one position to make a hole, and then fill the hole. The solution outline is shown below:

  1. Repeat until list is all sorted (~N times).
  2. Find where the element should be inserted in the sorted part of the list + make space for it (shift all the larger elements to the right).
  3. Insert the element in the sorted part of the list.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def sort(a)
  n = a.size
  
  for i in (0..n-1)
    element = a[i]
    
    k = i
    # Skip the loop for first element
    # Because first element has no preceding element for comparison
    while (k > 0 && element < a[k-1])
      # right shift the bigger element
      a[k] = a[k-1]
      k -= 1
    end
    
    # insert the element at index k
    a[k] = element
  end
end

a = [4,1,0,3,9,2]

sort(a)

p a

Alternative Implementation

Work on the array insert drill before the following insertion sort implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def insertion_sort(a)
  n = a.size
  
  for i in (0..n-1)
    insert_element = a[i]
    insert_index = i
    
    (insert_index-1).downto(0) do |j|
      # shift right if the element before the current
      # index is greater
      if insert_element < a[j]
        a[j+1] = a[j]
        insert_index -= 1
      end
      
      a[insert_index] = insert_element
    end
  end
end

a = [3,2,9,1,7,5,6,4,8]
insertion_sort(a)

p a

Building Blocks

The insertion sort algorithm uses the following basic building block:

  • Nested Loop with For and While
  • Nested Forward and Backward Loops
  • Right Shift

Language Agnostic Coding Drills

Here’s a breakdown of the key learning units for the Insertion Sort algorithm:

  1. Iteration and Looping: Understanding the concept of iteration, particularly how for and while loops work. Insertion sort involves moving through an array multiple times.

  2. List Indexing: Being able to index into a list to get, set, and compare values. Insertion sort constantly accesses and modifies elements at different positions in a list.

  3. Nested Looping: Insertion sort involves a nested loop where for each element, the algorithm iterates over all the previous elements.

  4. Variable Updating: The ability to update the value of a variable. Insertion sort includes updating the current index and the current value to be sorted.

  5. Condition Checking: Understanding if-else conditions. Insertion sort involves a key comparison operation to check whether one element is greater than another.

  6. Swapping Elements: In insertion sort, when the current element is less than the previous element, the algorithm performs a swap.

  7. Problem Decomposition: Understanding how to decompose the insertion sort problem into smaller, manageable tasks that correspond to the steps of the algorithm.

  8. Algorithm Analysis: Understand how to analyze the time and space complexity of insertion sort algorithm.

  9. Complete Insertion Sort Algorithm: Bringing all these units together to understand and implement the full insertion sort algorithm.

Solution for Coding Drills in Python

Here are Python code examples for each of the learning units:

  1. Iteration and Looping:
1
2

for i in range(10):
    print(i)
  1. List Indexing:
1
2
3

lst = [1, 2, 3, 4, 5]
print(lst[2])  # prints '3'
lst[2] = 10  # modifies the list to [1, 2, 10, 4, 5]
  1. Nested Looping:
1
2
3

for i in range(5):
    for j in range(i):
        print(i, j)
  1. Variable Updating:
1
2
3

x = 1
x = x + 2
print(x)  # prints '3'
  1. Condition Checking:
1
2
3
4
5
6

a = 10
b = 20
if a < b:
    print("a is less than b")
else:
    print("a is not less than b")
  1. Swapping Elements:
1
2
3
4
5

a = 1
b = 2
a, b = b, a  # swap
print(a)  # prints '2'
print(b)  # prints '1'
  1. Problem Decomposition: Not applicable as it’s a cognitive skill rather than a coding skill.
  2. Algorithm Analysis: Not applicable as it’s a theoretical aspect of computer science, not a Python coding skill.
  3. Complete Insertion Sort Algorithm:
1
2
3
4
5
6
7
8
9

def insertion_sort(lst):
    for i in range(1, len(lst)):
        key = lst[i]
        j = i - 1
        while j >= 0 and key < lst[j]:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = key
    return lst

Sure, here’s a general template for practicing insertion sort. This example sorts an array of integers in ascending order.

  1. Understand the problem: Given an array of integers, sort them in increasing order using insertion sort.

  2. Plan: Insertion sort works by maintaining a sorted section of the array, and with each iteration, it expands this sorted section by one element, placing the new element in the correct position.

  3. Code:

1
2
3
4
5
6
7
8

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >=0 and key < arr[j] :
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

  1. Review: Test the function with various input arrays to ensure it sorts correctly. If there are any bugs, review your implementation against the algorithm and correct them.

  2. Test:

1
2
3
4

test_array = [4, 3, 2, 10, 12, 1, 5, 6]
print("Original array: ", test_array)
insertion_sort(test_array)
print("Sorted array: ", test_array)

This should print:

Original array: [4, 3, 2, 10, 12, 1, 5, 6]
Sorted array: [1, 2, 3, 4, 5, 6, 10, 12]

Please note that the above code is in Python, so you might need to adjust it based on the language you’re using. Insertion sort is best suited for nearly sorted arrays or small-sized arrays, as its worst-case and average time complexity is O(n^2), where n is the number of elements in the array.

Practice Phase Template for Insertion Sort

Sure, here’s a general template for practicing insertion sort. This example sorts an array of integers in ascending order.

  1. Understand the problem: Given an array of integers, sort them in increasing order using insertion sort.

  2. Plan: Insertion sort works by maintaining a sorted section of the array, and with each iteration, it expands this sorted section by one element, placing the new element in the correct position.

  3. Code:

1
2
3
4
5
6
7
8

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >=0 and key < arr[j] :
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

  1. Review: Test the function with various input arrays to ensure it sorts correctly. If there are any bugs, review your implementation against the algorithm and correct them.

  2. Test:

1
2
3
4

test_array = [4, 3, 2, 10, 12, 1, 5, 6]
print("Original array: ", test_array)
insertion_sort(test_array)
print("Sorted array: ", test_array)

This should print:

Original array: [4, 3, 2, 10, 12, 1, 5, 6]
Sorted array: [1, 2, 3, 4, 5, 6, 10, 12]

Insertion sort is best suited for nearly sorted arrays or small-sized arrays, as its worst-case and average time complexity is O(n^2), where n is the number of elements in the array.