เทคนิค Merge Sort ในภาษา C

ประเภทของการเรียงลำดับ

C มีเทคนิคเรียงลำดับ 5 แบบ:

• Bubble Sort (หรือ Exchange Sort)
• Selection Sort
• Insertion Sort (หรือ Linear Sort)
• Quick Sort (หรือ Partition Exchange Sort)
• Merge Sort (หรือ External Sort)

Merge Sort

Merge Sort เป็นวิธีแบ่งและเอาชนะ (Divide and Conquer) แบ่งอาร์เรย์ครึ่งๆ เรียงย่อย แล้วรวม (merge) กลับกัน

ตัวอย่าง: อาร์เรย์ไม่เรียงลำดับ

38, 27, 43, 3, 9, 82, 10

แบ่งครึ่งเรื่อยๆ จนเหลือองค์ประกอบเดี่ยว (รูปภาพไม่ได้รวม)

จากนั้นรวมกลับโดยเรียงลำดับ (รูปภาพไม่ได้รวม)

ตัวอย่างโค้ด

#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("List before sorting\n");
    for(i = 0; i <= max; i++)
        printf("%d ", a[i]);
    sort(0, max);
    printf("\nList after sorting\n");
    for(i = 0; i <= max; i++)
        printf("%d ", a[i]);
    return 0;
}

ผลลัพธ์

List before sorting
10 14 19 26 27 31 33 35 42 44 0
List after sorting
0 10 14 19 26 27 31 33 35 42 44