ในส่วนนี้เราจะดูวิธีทำ sorting algorithm ใน C++ Sorted array คืออาร์เรย์ที่สมาชิกถูกจัดเรียงในบางลำดับ เช่น ตัวเลข อักษร เป็นต้น มีอัลกอริทึมมากมายสำหรับจัดเรียงอาร์เรย์ตัวเลข เช่น bubble sort, insertion sort, selection sort, merge sort, quick sort, heap sort รายละเอียดเพิ่มเติมเกี่ยวกับ selection sort ด้านล่าง
Selection sort เป็นวิธีจัดเรียงที่ให้ sorted array ทำงานโดยหา smallest element ในอาร์เรย์ซ้ำๆ แล้วนำไปสลับกับสมาชิกที่จุดเริ่มต้นของส่วนที่ยังไม่จัดเรียง
ตัวอย่างโค้ด
#include <iostream>
using namespace std;
void selectionSort(int a[], int n) {
int i, j, min, temp;
for (i = 0; i < n - 1; i++) {
min = i;
for (j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
int main() {
int a[] = { 22, 91, 35, 78, 10, 8, 75, 99, 1, 67 };
int n = sizeof(a) / sizeof(a[0]);
int i;
cout << "Given array is:" << endl;
for (i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
selectionSort(a, n);
printf("\nSorted array is: \n");
for (i = 0; i < n; i++)
cout << a[i] << " ";
return 0;
}
ผลลัพธ์
Given array is: 22 91 35 78 10 8 75 99 1 67 Sorted array is: 1 8 10 22 35 67 75 78 91 99
ในโปรแกรมข้างต้น selectionSort() เป็นฟังก์ชันจัดเรียงอาร์เรย์ a[] ด้วย selection sort มี for loop 2 ชั้น ในแต่ละรอบของ outer loop จะหา minimum element ในส่วนที่เหลือหลัง i แล้วนำไปสลับกับสมาชิกที่อยู่ตำแหน่ง i ทำซ้ำจนอาร์เรย์เรียงลำดับครบ
