Giải thích thuật toán trộn (merge sort) trong C

Sắp xếp là quá trình 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 (Bubble/Exchange)
• Chọn (Selection)
• Chèn (Insertion/Linear)
• Nhanh (Quick/Partition exchange)
• Trộn (Merge/External)

Merge Sort

Merge sort là phương pháp chia để trị. Chia mảng thành hai nửa, đệ quy conquistar, sau đó trộn (kết hợp).

Ví dụ mảng chưa sắp: 38, 27, 43, 3, 9, 82, 10

Kết hợp sắp xếp:

Ví dụ

Chương trình C sắp xếp trộn:

#include <stdio.h> 
#define max 10 
int a[11] = {10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0}; 
int b[10]; 
void merging(int low, int mid, int high){ 
    int l1, l2, i; 
    for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++){ 
        if(a[l1] <= a[l2]) b[i] = a[l1++]; 
        else b[i] = a[l2++]; 
    } 
    while(l1 <= mid) b[i++] = a[l1++]; 
    while(l2 <= high) b[i++] = a[l2++]; 
    for(i = low; i <= high; i++) a[i] = b[i]; 
} 
void sort(int low, int high){ 
    int mid; 
    if(low < high){ 
        mid = (low + high) / 2; 
        sort(low, mid); 
        sort(mid + 1, high); 
        merging(low, mid, high); 
    } else return; 
} 
int main(){ 
    int i; 
    printf("Truoc sap xep\n"); 
    for(i = 0; i <= max; i++) printf("%d ", a[i]); 
    sort(0, max); 
    printf("\nSau sap xep\n"); 
    for(i = 0; i <= max; i++) printf("%d ", a[i]); 
}

Đầu ra

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

Truoc sap xep: 10 14 19 26 27 31 33 35 42 44 0 
Sau sap xep: 0 10 14 19 26 27 31 33 35 42 44