Selection Sort (การจัดเรียงแบบเลือก)

Selection Sort เป็นอัลกอริทึมจัดเรียงที่ง่ายที่สุด แบ่งอาเรย์เป็น 2 ส่วน: ส่วนที่เรียงแล้ว (Sorted) และ ส่วนที่ยังไม่เรียง (Unsorted) หาค่า min/max จากส่วน Unsorted มาวางต่อท้ายส่วน Sorted

ความซับซ้อน (Complexity)

แนวคิดการทำงาน

1. ตั้ง i = 0 (ขอบเขตส่วนที่เรียงแล้ว)
2. หา index ของค่า น้อยที่สุด ในช่วง i ถึง n-1
3. สลับค่านั้นกับ array[i]
4. i++ ขยายส่วนที่เรียงแล้ว
5. ทำซ้ำจน i = n-1

ตัวอย่างข้อมูล

Input:  5 9 7 23 78 20
Output: 5 7 9 20 23 78

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

selectionSort(array, size)
  for i = 0 to size-2:
    iMin = i
    for j = i+1 to size-1:
      if array[j] < array[iMin]:
        iMin = j
    swap(array[i], array[iMin])

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

#include <iostream>
using namespace std;

void selectionSort(int *array, int size) {
    for (int i = 0; i < size-1; i++) {
        int iMin = i;
        for (int j = i+1; j < size; j++)
            if (array[j] < array[iMin])
                iMin = j;
        swap(array[i], array[iMin]);
    }
}

void display(int *array, int size) {
    for (int i = 0; i < size; i++) cout << array[i] << " ";
    cout << endl;
}

int main() {
    int n; cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cout << "Before: "; display(arr, n);
    selectionSort(arr, n);
    cout << "After: "; display(arr, n);
}

คุณสมบัติสำคัญ

• In-place: O(1) extra space
• Not Stable: การสลับอาจเปลี่ยนลำดับค่าเท่ากัน (แก้ได้ด้วยการเลื่อนแทนสลับ)
• Not Adaptive: O(n²) เสมอ แม้ข้อมูลเรียงแล้ว
• Minimal Swaps: สลับเพียง O(n) ครั้ง (น้อยที่สุดใน Comparison sorts)

เปรียบเทียบกับ Insertion Sort

เมื่อไหร่ควรใช้?

• ข้อมูลเล็กมาก (n < 20-30)
• เมื่อ "การเขียนหน่วยความจำ" แพง (Flash/EEPROM) - เพราะ Swap น้อย
• การศึกษา/สอน概念พื้นฐาน
• ไม่แนะนำ สำหรับข้อมูลขนาดใหญ่หรือ Production