แนวคิดการจัดเรียงข้อมูล (Sorting) ในภาษา C

ในชีวิตประจำวัน เราต้องค้นหาบ่อยๆ เช่น:

• บันทึกเฉพาะในฐานข้อมูล
• หมายเลขนักเรียนในรายชื่อ
• เบอร์โทรใน телефон북
• หน้าที่ต้องการในหนังสือ

ถ้าข้อมูลไม่ได้จัดเรียง การค้นหาจะยากและช้า แต่เมื่อจัดเรียงแล้ว การค้นหาจะมีประสิทธิภาพมากขึ้น (เช่น Binary Search ใช้ได้เฉพาะข้อมูลที่จัดเรียงแล้ว)

เกณฑ์วัดประสิทธิภาพการจัดเรียง (Sorting Efficiency)

คอมพิวเตอร์ไม่จัดเรียงแบบลองผิดลองถูกเหมือนมนุษย์ จึงมีอัลกอริทึมมากมาย เกณฑ์เปรียบเทียบคือ:

1. เวลา (Time Complexity) - ใช้เวลานานแค่ไหนในการจัดเรียง
2. พื้นที่หน่วยความจำ (Space Complexity) - ใช้หน่วยความจำเพิ่มเติมเท่าไหร่

ตัวอย่างโปรแกรม (Selection Sort)

#include <stdio.h>

int main() {
    int a[50], n, i, j, t, sm;
    
    printf("Enter number of elements: ");
    scanf("%d", &n);
    
    printf("Enter elements: ");
    for(i = 0; i < n; i++)
        scanf("%d", &a[i]);
    
    for(i = 0; i < n-1; i++) {
        sm = i;
        for(j = i+1; j < n; j++) {
            if(a[j] < a[sm])
                sm = j;
        }
        t = a[i];
        a[i] = a[sm];
        a[sm] = t;
    }
    
    printf("After sorting: ");
    for(i = 0; i < n; i++)
        printf("%d ", a[i]);
    
    return 0;
}

ผลลัพธ์

Enter number of elements: 4
Enter elements: 34 12 56 7
After sorting: 7 12 34 56

อัลกอริทึมจัดเรียงยอดนิยมอื่นๆ

* Quick Sort worst case O(n²) แต่เฉลี่ย O(n log n)