Sorted Array คือ อาร์เรย์ที่ข้อมูลเรียงลำดับแล้ว (น้อยไปมาก หรือ มากไปน้อย) มีอัลกอริทึมการเรียงมากมาย เช่น Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, Heap Sort
หลักการ Selection Sort
- หาค่าน้อยที่สุดในส่วนที่ยังไม่เรียง
- สลับกับตำแหน่งแรกของส่วนที่ยังไม่เรียง
- ขยายส่วนที่เรียงแล้วทีละ 1 ตัว
- ทำซ้ำจนครบทุกตัว
โค้ดโปรแกรม Selection Sort
#include <iostream>
using namespace std;
void selectionSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
// หาค่าน้อยที่สุดในส่วนที่เหลือ
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIdx])
minIdx = j;
}
// สลับกับตำแหน่ง i
if (minIdx != i)
swap(a[i], a[minIdx]);
}
}
int main() {
int a[] = {22, 91, 35, 78, 10, 8, 75, 99, 1, 67};
int n = sizeof(a) / sizeof(a[0]);
cout << "Given array: ";
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
selectionSort(a, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
return 0;
}ผลลัพธ์
Given array: 22 91 35 78 10 8 75 99 1 67 Sorted array: 1 8 10 22 35 67 75 78 91 99
การทำงานทีละขั้นตอน (Trace)
Initial: 22 91 35 78 10 8 75 99 1 67
i=0: min=1 (idx 8) → swap 22↔1
[1] 91 35 78 10 8 75 99 22 67
i=1: min=8 (idx 5) → swap 91↔8
[1 8] 35 78 10 91 75 99 22 67
i=2: min=10 (idx 4) → swap 35↔10
[1 8 10] 78 35 91 75 99 22 67
i=3: min=22 (idx 8) → swap 78↔22
[1 8 10 22] 35 91 75 99 78 67
... จนครบ
Complexity Analysis
| Metric | Complexity | คำอธิบาย |
|---|---|---|
| Time - Best | O(n²) | ยังต้องสแกนหา min ทุกรอบ |
| Time - Average | O(n²) | |
| Time - Worst | O(n²) | |
| Space | O(1) | In-place, ไม่ใช้ memory เพิ่ม |
| Swaps | O(n) | น้อยกว่า Bubble Sort (O(n²) swaps) |
| Stable | No | อาจเปลี่ยนลำดับค่าที่เท่ากัน |
เปรียบเทียบ Sorting Algorithms
| Algorithm | Time (Avg) | Space | Stable | เหมาะสำหรับ |
|---|---|---|---|---|
| Selection Sort | O(n²) | O(1) | No | ข้อมูลน้อย, Memory จำกัด |
| Insertion Sort | O(n²) | O(1) | Yes | ข้อมูลใกล้เรียงแล้ว, Online |
| Merge Sort | O(n log n) | O(n) | Yes | ข้อมูลเยอะ, ต้อง Stable |
| Quick Sort | O(n log n) | O(log n) | No | ทั่วไป เร็วที่สุดในทางปฏิบัติ |
| Heap Sort | O(n log n) | O(1) | No | Garantueed O(n log n) |
| std::sort | O(n log n) | O(log n) | No* | ใช้ใน Production (Introsort) |
*C++17 มี std::stable_sort
Modern C++: ใช้ std::sort
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> v = {22, 91, 35, 78, 10, 8, 75, 99, 1, 67};
sort(v.begin(), v.end()); // เรียงน้อยไปมาก
// เรียงมากไปน้อย
sort(v.rbegin(), v.rend());
// หรือ
sort(v.begin(), v.end(), greater<int>());
for (int x : v) cout << x << " ";
return 0;
}สรุป
- Selection Sort เข้าใจง่าย ใช้ได้กับข้อมูลเล็ก
- ข้อมูลเยอะ ควรใช้
std::sort(Introsort = Quick + Heap + Insertion) - ต้องการ Stable ใช้
std::stable_sort - In-place + No recursion = เหมาะ Embedded Systems
