Insertion Sort
An Introduction with Examples |
Prof. David Bernstein |
Computer Science Department |
bernstdh@jmu.edu |
insertionsort(a[]) { for all i { move all elements larger than a[i] one position; put a[i] in the resulting "hole"; } }
4 | 8 | 7 | 3 | 9 | 3 |
4 | 7 | 8 | 3 | 9 | 3 |
3 | 4 | 7 | 8 | 9 | 3 |
3 | 4 | 7 | 8 | 9 | 3 |
3 | 3 | 4 | 7 | 8 | 9 |
/** * Sort an array of integers using an insertion sort. * * Side Effects: The array is sorted "in place". * * @param a The array of integers * @param length The number of elements in the array */ void sort(int a[], int length) { int i, j, temp; for (i = 1; i < length; i++) { temp = a[i]; j = i; while ((j > 0) && (temp < a[j - 1])) { a[j] = a[j - 1]; j--; } a[j] = temp; } }
\( T(n) = 1 + 2 + \cdots + (n-1) = n \cdot (n-1)/2 \)
So: \( T(n) = O(n^2) \)