เทคนิคการจัดเรียง (Sorting Techniques) ในภาษา C

โจทย์

เทคนิคการจัดเรียงในภาษา C มีอะไรบ้าง? อธิบายเทคนิคหนึ่งพร้อมตัวอย่าง

คำตอบ

ภาษา C มีเทคนิคการจัดเรียงหลัก 5 แบบ:

1. Bubble Sort (Exchange Sort) - จัดเรียงแบบฟองสบู่
2. Selection Sort - จัดเรียงแบบเลือก
3. Insertion Sort (Linear Sort) - จัดเรียงแบบแทรก
4. Quick Sort (Partition Exchange Sort) - จัดเรียงแบบเร็ว
5. Merge Sort (External Sort) - จัดเรียงแบบรวม

Bubble Sort (จัดเรียงแบบฟองสบู่)

เทคนิคที่ง่ายที่สุด เรียกอีกอย่างว่า Exchange Sort

ขั้นตอนการทำงาน

1. เปรียบเทียบองค์ประกอบตัวแรกกับองค์ประกอบที่เหลือ สลับที่กันถ้าอยู่ในลำดับผิด
2. ทำซ้ำสำหรับองค์ประกอบอื่นๆ จนกว่าจะเรียงลำดับครบ

ตัวอย่างการทำงาน (Pass by Pass)

ข้อมูลต้นฉบับ: 30 50 40 10 20

Pass 1: เปรียบเทียบ a[0] กับตัวอื่นๆ

30 > 50 (False) - ไม่สลับ
30 > 40 (False) - ไม่สลับ
30 > 10 (True)  - สลับ → 10 50 40 30 20
10 > 20 (False) - ไม่สลับ

Pass 2: เปรียบเทียบ a[1] กับตัวที่เหลือ

50 > 40 (True)  - สลับ → 10 40 50 30 20
40 > 30 (True)  - สลับ → 10 30 50 40 20
30 > 20 (True)  - สลับ → 10 20 50 40 30

Pass 3: เปรียบเทียบ a[2] กับตัวที่เหลือ

50 > 40 (True)  - สลับ → 10 20 40 50 30
40 > 30 (True)  - สลับ → 10 20 30 50 40

Pass 4: เปรียบเทียบ a[3] กับตัวสุดท้าย

50 > 40 (True)  - สลับ → 10 20 30 40 50

อัลกอริทึม (Pseudocode)

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

ตัวอย่างโปรแกรม Bubble Sort สมบูรณ์

#include <stdio.h>
int main() {
    int a[50], i, j, n, temp;
    printf("Enter number of elements: ");
    scanf("%d", &n);
    printf("Enter elements:\n");
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    printf("Before sorting:\n");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
    // Bubble Sort
    for (i = 0; i < n-1; i++) {
        for (j = i+1; j < n; j++) {
            if (a[i] > a[j]) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    printf("\nAfter bubble sorting:\n");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}

ผลลัพธ์:

Enter number of elements: 5
Enter elements: 12 11 45 26 67
Before sorting: 12 11 45 26 67
After sorting: 11 12 26 45 67

สรุปประสิทธิภาพ