Selection Sort (การจัดเรียงแบบเลือก) ในภาษา C

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

1. หาค่าน้อยที่สุดจากทั้งอาร์เรย์ วางที่ตำแหน่งแรก (Index 0)
2. หาค่าน้อยที่สุดจากที่เหลือ (Index 1 ถึง n-1) วางที่ตำแหน่งที่ 2
3. ทำซ้ำจนครบทุกตำแหน่ง

ตัวอย่างการทำงาน Pass โดย Pass

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

Pass 1

หาค่าน้อยที่สุด = 10 สลับกับตำแหน่ง 0 → 10, 50, 40, 30, 20

Pass 2

หาค่าน้อยที่สุดจากตำแหน่ง 1 เป็นต้นไป = 20 สลับกับตำแหน่ง 1 → 10, 20, 40, 30, 50

Pass 3

หาค่าน้อยที่สุดจากตำแหน่ง 2 เป็นต้นไป = 30 สลับกับตำแหน่ง 2 → 10, 20, 30, 40, 50

Pass 4

เหลือแค่ 2 ตัวสุดท้าย ตรวจสอบแล้วเรียบร้อย → 10, 20, 30, 40, 50

โค้ดอัลกอริทึม

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;
}

ตัวอย่างโปรแกรมครบถ้วน

#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]);
    
    // Selection Sort
    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: 45 12 37 68
After sorting: 12 37 45 68

ความซับซ้อน

• Time: O(n²) ทุกกรณี (Best/Average/Worst)
• Space: O(1) - In-place sorting
• ไม่เสถียร (Unstable) - อาจสลับตำแหน่งค่าที่เท่ากัน