Giải thích sắp xếp chèn (insertion sort) bằng C

Sắp xếp là sắp xếp phần tử tăng/giảm dần.

Loại sắp xếp

C cung cấp 5 kỹ thuật:

• Nổi bọt
• Chọn
• Chèn (Insertion/Linear)
• Nhanh
• Trộn

Insertion Sort

Logic sắp xếp chèn:

for(i = 1; i <= n - 1; i++){ 
    for(j = i; j > 0 && a[j-1] > a[j]; j--){ 
        t = a[j]; 
        a[j] = a[j-1]; 
        a[j-1] = t; 
    } 
}

Giải thích

Xét các phần tử chưa sắp xếp:

Ví dụ

Chương trình C insertion sort:

#include <stdio.h> 
int main(){ 
    int a[50], i, j, n, t; 
    printf("Nhap so phan tu:\n"); 
    scanf("%d", &n); 
    printf("Nhap cac phan tu:\n"); 
    for(i = 0; i < n; i++) scanf("%d", &a[i]); 
    for(i = 1; i <= n - 1; i++){ 
        for(j = i; j > 0 && a[j-1] > a[j]; j--){ 
            t = a[j]; 
            a[j] = a[j-1]; 
            a[j-1] = t; 
        } 
    } 
    printf("Sau insertion sort:\n"); 
    for(i = 0; i < n; i++) printf("%d\t", a[i]); 
    return 0; 
}

Đầu ra

Kết quả chạy chương trình:

Nhap so phan tu: 10 
Nhap phan tu: 34 125 2 6 78 49 1 3 89 23 
Sau insertion sort: 1 2 3 6 23 34 49 78 89 125