Insertion Sort
Insertion sort
How do you sort playing cards? Suppose you hold the 6, 7, 9, and 10 of hearts in ascending order, then draw the 8 of hearts.
Rather than apply bubble or selection sort, you naturally locate the position between 7 and 9 and insert the 8 there.
For example, sort this eight-item sequence:
Direct insertion: save, compare and shift
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
Algorithm analysis
Insertion sort performs n−1 passes. In the worst case these need 1,2,3,…,n−1 comparisons and copies, for time.
It works in place without an additional data structure, using extra space.
| Time | Extra space | Stability | Design idea |
|---|---|---|---|
| Stable | Decrease and conquer |
Insertion sort
#include <stdio.h>
typedef int T;
/**
* Insertion Sort (original v1.0)
*/
T *insertion_sort(T *arr, int n) {
for (int i = 1; i < n; i++) {
T temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
return arr;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
insertion_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}Binary insertion sort
Binary insertion improves how the insertion position is found. Each item is still inserted into the sorted prefix, but binary search locates the position.
Binary insertion sort
Binary insertion: locate, then shift
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
#include <stdio.h>
typedef int T;
/**
* Insertion Sort (original v1.0)
*/
T *insertion_sort(T *arr, int n) {
for (int i = 1; i < n; i++) {
T temp = arr[i];
int left = 0;
int right = i - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (temp < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = temp;
}
return arr;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
insertion_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}KNOWLEDGE QUIZ
KNOWLEDGE QUIZ
Record temp and individual shifts
Use direct insertion sort on [6,2,4,3]. Record temp, comparisons, every shift, and the final insertion slot. Explain what binary search can reduce and what it cannot remove.