Insertion sort is a sorting algorithm in O(n2) time. It basically inserts each item into its correct position.
Pseudocode[]
This pseudocode takes a list .
for i = 2 to n value = a at i j = i - 1 while j ≥ 1 and value < a at j a at j + 1 = a at j j = j - 1 a at j + 1 = value
This is the code in C (integer list assumed):
void insertion_sort(int* a, int n) { int i, j, value; for(i=1;i<n;i++) { value = a[i]; j=i-1; while(j>=0 && value < a[j]) { a[j+1] = a[j]; j--; } a[j+1] = value; } }
See Also[]
|