Insertion Sort is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time. It works by repeatedly taking an element from the unsorted part of the array and inserting it into its correct position within the sorted part of the array. The algorithm maintains two parts of the array: the sorted part and the unsorted part.
Step by Step procedure
Here’s a step-by-step explanation of the logic behind Insertion Sort:
Initialization
The algorithm starts with the first element of the array considered as the sorted part, and the rest of the array is considered as the unsorted part.
Iteration
In each iteration, the algorithm takes the first element from the unsorted part and compares it with the elements in the sorted part.
It shifts the elements in the sorted part to the right until it finds the correct position to insert the current element.
Insertion
Once the correct position is found, the current element is inserted into its place in the sorted part of the array.
Incrementing the Sorted Part
After insertion, the sorted part of the array grows by one element, and the unsorted part shrinks by one element.
Repeat
Steps 2 to 4 are repeated for the remaining unsorted elements until the entire array becomes sorted.
Termination
The algorithm terminates when all elements have been processed and inserted into their correct positions.
Invariants
Invariant 1: Partial Sorting
Throughout the execution of Insertion Sort, the elements before the current position in the array are in their correct sorted positions.
In other words, after each iteration of the algorithm, the first i elements (where i is the current iteration index) are sorted and in their final positions.
Invariant 2: Current Element Insertion
At each step of the iteration, the algorithm selects an element from the unsorted part of the array and inserts it into its correct position within the sorted part of the array.
This ensures that the current element is correctly placed relative to the already sorted elements.
Invariant 3: Sorted Part Growing
As Insertion Sort progresses through iterations, the sorted part of the array grows by one element in each iteration.
The newly added element comes from the unsorted part and is inserted into its appropriate position within the sorted part.
Invariant 4: Unsorted Part Decreasing
In each iteration, the unsorted part of the array becomes smaller by one element as the current element is moved from the unsorted part to its correct position in the sorted part.
Press enter or click to view image in full size
Diagram 1
Pseudocode
InsertionSort(A): n = length of array A
for i from 1 to n - 1: current_element = A[i] j = i - 1
// Move elements of the sorted part to make space for the current element while j >= 0 and A[j] > current_element: A[j + 1] = A[j] j = j - 1
// Insert the current element into its correct position A[j + 1] = current_element
// Array is now sorted
return A
In this pseudocode, the InsertionSort function takes an array A as input and sorts it using the Insertion Sort algorithm. It supports the invariants as follows:
Get Binayak Basu’s stories in your inbox
Join Medium for free to get updates from this writer.
Invariant 1 (Partial Sorting)
The outer loop runs from index 1 to n - 1. After each iteration (for each value of i), the first i elements are in their correct sorted positions.
Invariant 2 (Current Element Insertion)
Within the inner loop, the algorithm selects the current_element and finds its correct position by shifting larger elements to the right.
Invariant 3 (Sorted Part Growing)
The sorted part of the array grows by one element in each iteration as the current_element is inserted into its correct position.
Invariant 4 (Unsorted Part Decreasing)
The inner loop decrements j and shifts elements to the right until the correct position for current_element is found. This reduces the size of the unsorted part in each iteration.
The pseudocode follows the logic of the Insertion Sort algorithm while ensuring that the invariants are maintained throughout the sorting process.
Python Code
def InsertionSort(lst): l = len(lst) # Move the first card into the sorted array # Start from the next card
for j in range(1, l): # j represents the "current card" # the first card is moved to the sorted array - hence the count # starts from 1 and not from 0
key = lst[j] # key captures the element to be moved to the sorted array
# Insert the key to the sorted array # start from the left of the element to be placed in the sorted array # since lst[0:j-1] is sorted and lst[j+1:] is unsorted. i = j-1 while (i >= 0 and lst[i] > key): ''' # if the element in the sorted array is greater than the key, # the element in the sorted array is moved a position to the right, # thus creating a space in the left for the key. ''' ''' # repeat this until you find an element which is smaller or equal # to the key or the sorted array is exhausted and no element is # found to be smaller or equal to the key. ''' lst[i+1] = lst[i] i -= 1
''' # when the loop ends , you have found the position of the element # which is smaller than or equal to the key.
# This position is captured by i. Thus place the key to the right of # the ith element. ''' lst[i+1] = key return lst
lst = [4, 18, 7, 8, 6, 2, 1, 10, 54, 11]
print(InsertionSort(lst))
Alternative code
def InsertionSort(lst): l = len(lst) for i in range(1, l): key = lst[i] # key is the element to be inserted
j = i - 1 # j is the index of the element before the key while j >= 0 and key < lst[j]: # if key is smaller than the element before it lst[j], lst[j+1] = lst[j+1], lst[j] # swap the elements j -= 1 # decrement j
return lst # return the sorted list
lst = [4, 18, 7, 8, 6, 2, 2, 1, 10, 54, 11]
print(InsertionSort(lst))
Complexity
Time Complexity
In the best-case scenario, when the input array is already nearly sorted, Insertion Sort requires O(n) time complexity. This is because it can quickly determine that each element is already in its correct position and no further swaps are needed.
In the worst-case scenario, when the input array is in reverse order, Insertion Sort requires O(n²) time complexity. This is because for each element, it may need to compare and swap with all previous elements.
In the average-case scenario, the time complexity is still O(n²), making it less efficient than some other sorting algorithms like QuickSort or MergeSort.
Overall, Insertion Sort is efficient for small datasets or partially sorted datasets.
Space Complexity
Insertion Sort is an in-place sorting algorithm, meaning it doesn’t require additional memory proportional to the input size. It only needs a constant amount of extra space for variables (like loop indices).
Therefore, the space complexity of Insertion Sort is O(1), indicating constant space usage.
Stability
Insertion Sort is a stable sorting algorithm. It maintains the relative order of equal elements during the sorting process. If two elements have equal values, the one that appears earlier in the original array will come earlier in the sorted array.
Adaptive
Insertion Sort is an adaptive algorithm. It performs well when the input data is partially sorted, as it requires fewer comparisons and swaps in such cases.
When the input array is partially sorted, Insertion Sort can quickly identify that many elements are already in their correct positions. This leads to fewer comparisons and fewer swaps, which in turn results in better overall efficiency. Here’s why Insertion Sort runs in linear time for partially sorted arrays:
Fewer Comparisons: In a partially sorted array, there are fewer instances where an element needs to be compared with elements that are significantly larger than itself. This reduces the number of comparisons needed during the insertion step, which is the most time-consuming part of the algorithm.
Fewer Swaps: Similarly, in a partially sorted array, the number of swaps required to insert an element into its correct position is reduced. This is because many elements may already be in their correct places, requiring little or no swapping.
Early Termination: Since the sorted portion of the array is already well-ordered, Insertion Sort can quickly identify the correct position for each element by comparing it with only a few preceding elements. This can lead to early termination of the inner loop, further improving efficiency.
Due to these factors, the overall time complexity of Insertion Sort in the case of a partially sorted array becomes closer to linear time O(n) rather than the quadratic time O(n^2) that is observed in the average and worst cases for completely unsorted arrays. However, it’s important to note that the exact performance improvement depends on the degree of partial sorting present in the input array.
Number of Comparisons and Swaps
In the worst case, Insertion Sort performs approximately n*(n-1)/2 comparisons and n*(n-1)/2swaps.
Conclusion
Insertion Sort is often used in cases where the input data is already partially sorted or when the dataset is small. Its simplicity and adaptability make it a good choice for these scenarios. However, for larger datasets, more efficient sorting algorithms like QuickSort or MergeSort are generally preferred due to their better average-case performance.
