Chương trình C cho Sắp xếp chèn đệ quy

Sắp xếp chèn (Insertion sort) là một thuật toán sắp xếp dựa trên so sánh tại chỗ (in-place comparison-based algorithm).

Thuật toán hoạt động bằng cách đặt phần tử vào vị trí đúng trong mảng con đã sắp xếp, tức là mảng con đi trước phần tử đang xét (mảng con đã được sắp xếp).

Thuật toán

Bước 1 – Lặp từ 1 đến n-1 và thực hiện:

Bước 2.1 – Chọn phần tử tại vị trí i, array[i].

Bước 2.2 – Chèn phần tử vào vị trí của nó trong mảng con đã sắp xếp array[0] đến arr[i].

Ví dụ minh họa thuật toán

Mảng = [34, 7, 12, 90, 51]

Với i = 1, arr[1] = 7, đặt vào vị trí trong mảng con arr[0] - arr[1].

[7, 34, 12, 90, 51]

Với i = 2, arr[2] = 12, đặt vào vị trí trong mảng con arr[0] - arr[2].

[7, 12, 34, 90, 51]

Với i = 3, arr[3] = 90, đặt vào vị trí trong mảng con arr[0] - arr[3].

[7, 12, 34, 90, 51]

Với i = 4, arr[4] = 51, đặt vào vị trí trong mảng con arr[0] - arr[4].

[7, 12, 34, 51, 90]

Ở đây, chúng ta sẽ xem sắp xếp chèn đệ quy hoạt động như thế nào. Nó hoạt động dựa trên cơ sở ngược: gọi đệ 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. Sau đó, trong mảng đã sắp xếp được trả về bởi hàm, chèn phần tử thứ n vào vị trí thích hợp như trong mảng đã sắp xếp.

Chương trình sắp xếp chèn đệ quy:

Ví dụ

#include 
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;
}

Kết quả

Unsorted Array: 34 7 12 90 51
Sorted Array: 7 12 34 51 90