What is Insertion Sort?
Insertion Sort is an intuitive and adaptive sorting algorithm that builds the final sorted array one element at a time. It works similarly to how most people sort playing cards in their hands - by taking one card at a time and inserting it into its correct position among the cards already sorted.
While not optimal for large datasets, Insertion Sort is efficient for small arrays and nearly-sorted data. Its simplicity and adaptiveness make it a practical choice in specific scenarios, and it's often used as part of more complex hybrid sorting algorithms.
When to Use Insertion Sort?
Insertion Sort shines in several specific scenarios:
Nearly Sorted Data: When the array is already partially sorted, Insertion Sort can perform nearly linearly.
Small Datasets: For arrays with fewer than 50 elements, Insertion Sort's simplicity can make it faster than more complex algorithms.
Online Sorting: When you need to sort data as it is received, Insertion Sort can efficiently insert new elements into an already-sorted portion.
However, for large, randomly ordered datasets, more efficient algorithms like QuickSort or MergeSort are preferable.
How Insertion Sort Works
Insertion Sort divides the array into sorted and unsorted sections, gradually moving elements from the unsorted section to their correct position in the sorted section.
Step-by-Step Explanation
Here's how Insertion Sort operates:
-
Start with First Element:
- Consider the first element as a sorted section of length one.
-
Take Next Element:
- Select the first unsorted element and store it as the 'key'.
-
Insert in Correct Position:
- Compare the key with each element in the sorted section from right to left.
- Shift larger elements one position ahead.
- Insert the key in its correct position.
Visual Representation of Insertion Sort
To sort the array [64, 34, 25, 12, 22]:
- Take 34 and insert it before 64: [34, 64, 25, 12, 22]
- Take 25 and insert it before 34: [25, 34, 64, 12, 22]
- Continue until fully sorted: [12, 22, 25, 34, 64]
Pseudocode for Insertion Sort
function insertionSort(arr):
for i from 1 to size of arr:
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key
return arr
Implementing Insertion Sort in Kotlin
fun insertionSort(arr: IntArray): IntArray {
for (i in 1 until arr.size) {
val key = arr[i]
var j = i - 1
// Move elements greater than key one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = key
}
return arr
}
Code Walkthrough
-
Outer Loop:
- Iterates through the unsorted section, starting from the second element.
-
Inner Loop:
- Shifts elements of the sorted section that are greater than the key.
-
Key Placement:
- Places the key in its correct position within the sorted section.
Visual Step-by-Step Process
Initial Array: [64, 34, 25, 12, 22]
Pass 1:
[64, 34, 25, 12, 22] // Compare 34 with sorted portion
↓ ↓
[34, 64, 25, 12, 22] // Insert 34 before 64
✓ ✓
Pass 2:
[34, 64, 25, 12, 22] // Compare 25 with sorted portion
↓ ↓ ↓
[25, 34, 64, 12, 22] // Insert 25 at start
✓ ✓ ✓
Pass 3:
[25, 34, 64, 12, 22] // Compare 12 with sorted portion
↓ ↓ ↓ ↓
[12, 25, 34, 64, 22] // Insert 12 at start
✓ ✓ ✓ ✓
Pass 4:
[12, 25, 34, 64, 22] // Compare 22 with sorted portion
↓ ↓ ↓ ↓ ↓
[12, 22, 25, 34, 64] // Insert 22 after 12
✓ ✓ ✓ ✓ ✓
Legend:
- ↓ : Elements being compared
- ✓ : Sorted portion
- Unmarked: Unsorted portion
Time Complexity Analysis
Best Case: O(n)
- Occurs when array is already sorted
- Only requires one comparison per element
- No shifting needed
Worst Case: O(n²)
- Occurs when array is sorted in reverse order
- Maximum comparisons and shifts needed for each element
- Each element must be compared with every sorted element
Average Case: O(n²)
- Random input data
- Approximately half of the sorted elements are compared
- Requires shifting of elements
Space Complexity: O(1)
- Only requires a single additional memory space for the key
- Sorts in-place
Detailed Performance Breakdown
Number of Operations
For an array of size n:
-
Comparisons:
- Best case: (n-1)
- Worst case: n(n-1)/2
- Average case: n(n-1)/4
-
Shifts:
- Best case: 0
- Worst case: n(n-1)/2
- Average case: n(n-1)/4
Performance Table
Array Size (n) | Best Case (n) | Average Case (n²/4) | Worst Case (n²/2) |
---|---|---|---|
10 | 9 | 22 | 45 |
100 | 99 | 2,475 | 4,950 |
1,000 | 999 | 249,750 | 499,500 |
Optimization Techniques
- Binary Search Insertion
fun insertionSortWithBinarySearch(arr: IntArray): IntArray {
for (i in 1 until arr.size) {
val key = arr[i]
val location = binarySearch(arr, key, 0, i)
for (j in i downTo location + 1) {
arr[j] = arr[j - 1]
}
arr[location] = key
}
return arr
}
- Shell Sort Variation
- A variation of Insertion Sort that allows exchange of items that are far apart
Comparison with Other Sorting Algorithms
Algorithm | Best Case | Average Case | Worst Case | Space | Stable |
---|---|---|---|---|---|
Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
Advantages and Disadvantages of Insertion Sort
Advantages:
- Adaptive - efficient for data that is already substantially sorted
- Stable - maintains relative order of equal elements
- In-place - only requires a constant amount O(1) of additional memory space
- Online - can sort a list as it receives it
Disadvantages:
- Quadratic time complexity makes it inefficient for large datasets
- Generally performs worse than advanced algorithms like QuickSort
- Requires shifting of elements, which can be expensive
Conclusion
Insertion Sort, while not suitable for large datasets, remains a valuable algorithm in specific scenarios, particularly for small or nearly-sorted arrays. Its adaptiveness, stability, and simple implementation make it a practical choice in certain applications, especially when dealing with continuous, real-time data streams.
Top comments (0)