[Sorting] Insertion Sort

In the final post, we have studied about the selection sort and its implementation in Python. 

https://code-studies.tistory.com/123

[Sorting] Introduction & Selection Sort

 

In this post, we will study about the second sorting algorithm, insertion sort.

 

---

Insertion Sort

 

Insertion sort is a sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part.

insertion sort gif

 

It is much easier to understand following the flow of the code. 

Let's look into Python function implementation of insertion sort. 

 

---

Python Implementation

 

def insertion_sort(arr: list[int]) -> None:
    for i in range(1, len(arr)):
        j = i
        
        while (j > 0) and (arr[j-1] > arr[j]):
            arr[j-1], arr[j] = arr[j], arr[j-1]
            j -= 1

Starting from the second index position i = 1, i traverse through all of the index.

i denotes the starting position of the current element in the unsorted part. 

The inner loop repeatedly swaps elements if the left element has higher value, to put current element in the right position of sorted part. 

 

After slowly following the path of the code, you can quickly grasp the concept of insertion sort.

 

---

Runtime Complexity

 

To get straight to the point, typical runtime of insertion sort is O(N²).

 

If a list has N terms, the outer loop will execute N - 1 times (because it starts from i = 1).

For each outer loop execution, the inner loop has on average N/2 executions. 

So the total number of comparisons is proportional to N(N - 1)/2, or O(N²).

 

 

---

Nearly Sorted Lists

 

For sorted or nearly sorted lists, runtime complexity of insertion sort is O(N). 

 

A nearly sorted list only contains a few elements not in sorted order.

Ex: (4, 5, 17, 25, 89, 14) is nearly sorted having only one element not in sorted position.

 

 

In a nearly sorted list with total N elements, say there are constant C number of unsorted elements, giving N - C sorted elements. 

Each outer loop will require at most N comparisons for the unsroted elements, and constant 1 comparison for the sorted elements. 

Thus, the runtime complexity sums up to be: 

O(C * N + (N - C) * 1) = O(N²)

 

---

 

In the following post, we will delve into shell sort.