Sắp xếp chèn là một thuật toán sắp xếp là một thuật toán dựa trên so sánh tại chỗ.
Thuật toán hoạt động bằng cách đặt phần tử vào vị trí của chúng trong mảng con đã sắp xếp, tức là mảng con đứng trước phần tử là mảng con đã sắp xếp.
Thuật toán
Bước1 - lặp từ 1 đến n-1 và thực hiện -
Bước 2.1 - chọn phần tử ở vị trí i, mảng [i].
Bước2.2 - chèn phần tử vào vị trí của nó trong mảng mảng con đã sắp xếp [0] đến arr [i].
Hãy lấy một ví dụ để hiểu thuật toán
Mảng =[34, 7, 12, 90, 51]
Đối với tôi =1, arr [1] =7, đặt ở vị trí của nó trong mảng con arr [0] - arr [1].
[7, 34, 12, 90, 51]
Đối với i =2 , arr [2] =12, đặt vị trí của nó trong mảng con arr [0] - arr [2].
[7, 12, 34, 90, 51]
Đối với i =3 , arr [3] =90, đặt vị trí của nó trong mảng con arr [0] - arr [3].
[7, 12, 34, 90, 51]
Đối với tôi =4, arr [4] =51, đặt ở vị trí của nó trong mảng con arr [0] - arr [4].
[7, 12, 34, 54, 90]
Ở đây, chúng ta sẽ xem cách sắp xếp chèn đệ quy hoạt động như thế nào. Nó hoạt động trên cơ sở ngược lại, tức là chúng ta sẽ gọi một cách đệ quy hàm recursiveInsertionSort () để sắp xếp mảng n-1 phần tử so với lần lặp hiện tại. Và sau đó trong mảng đã sắp xếp này sẽ được hàm trả về, chúng ta sẽ chèn phần tử thứ n vào vị trí của nó như trong mảng đã sắp xếp.
Chương trình sắp xếp chèn đệ quy -
Ví dụ
#include <stdio.h>
void recursiveInsertionSort(int arr[], int n){
if (n <= 1)
return;
recursiveInsertionSort( arr, n-1 );
int nth = arr[n-1];
int j = n-2;
while (j >= 0 && arr[j] > nth){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = nth;
}
int main(){
int array[] = {34, 7, 12, 90, 51};
int n = sizeof(array)/sizeof(array[0]);
printf("Unsorted Array:\t");
for (int i=0; i < n; i++)
printf("%d ",array[i]);
recursiveInsertionSort(array, n);
printf("\nSorted Array:\t");
for (int i=0; i < n; i++)
printf("%d ",array[i]);
return 0;
} Đầu ra
Unsorted Array: 34 7 12 90 51 Sorted Array: 7 12 34 51 90