Algorithm(thuật toán)
Insertion sortÝ tưởng của insertion sort như sếp bài nếu số phía sau nhỏ hơn phía trước thì cho thì cho nó lên trên.
|
1 2 3 4 5 6 7 8 9 10 |
Tư tưởng của thuật toán là i, j để chỉ vị trí, ví dụ j=2 tức là vị trí thứ 2 INSERTION-SORT.A/ for j = 2 to A:length key = A[j] // Insert A[j] into the sorted sequence A[1.. j - 1]. i = j - 1 while i > 0 and A[i] > key A[i + 1] = A[i] i = i - 1 A[i + 1] = key |
Cách thực hiện như sau
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } |
