Selection Sort คือ?

การเรียงลำดับแบบเลือก เป็นอัลกอริทึมการจัดเรียงที่ง่ายและมีประสิทธิภาพ ซึ่งทำงานโดยการเลือกค่าที่น้อยที่สุด (หรือมากที่สุด) ในแต่ละรอบ แล้วสลับค่าที่เลือกมาต่อท้ายของส่วนที่เรียงแล้ว

Selection Sort ทำงานอย่างไร?

ตัวอย่าง: 64 25 12 22 11 ให้เรียงจากน้อยไปมาก
รอบที่ 1: เริ่มต้นด้วยการหาค่าที่น้อยที่สุด ตั้งแต่ index ที่ 0 ถึง 4 ตามลำดับ จะเห็นได้ว่า 11 เป็นค่าน้อยที่สุด ดังนั้นจึงต้องสลับตำแหน่งของ 11 ไปเก็บไว้ที่ index 0

64 25 12 22 11 -> 11 25 12 22 64

รอบที่ 2: index 1 มี 25 อยู่ ให้หาค่าที่น้อยที่สุดของอาร์เรย์ที่เหลือ จะเห็นได้ว่า 12 เป็นค่าที่น้อยที่สุด ให้สลับตำแหน่งของ 12 ไปเก็บไว้ที่ index 1

11 25 12 22 64 -> 11 12 25 22 64

รอบที่ 3: index 2 มี 25 อยู่ ให้หาค่าที่น้อยที่สุดของอาร์เรย์ที่เหลือ จะเห็นได้ว่า 22 เป็นค่าที่น้อยที่สุด ให้สลับตำแหน่งของ 22 ไปเก็บไว้ที่ index 2

11 12 25 22 64 -> 11 12 22 25 64

รอบที่ 4: index 3 มี 25 อยู่ ให้หาค่าที่น้อยที่สุดของอาร์เรย์ที่เหลือ จะเห็นได้ว่า 25 เป็นค่าที่น้อยที่สุด และอยู่ในตำแหน่งที่ถูกต้องแล้ว จึงไม่มีการสลับตำแหน่ง

11 12 22 25 64 -> 11 12 22 25 64

ส่วนค่าที่มากที่สุดจะถูกวางไว้ที่ตำแหน่งสุดท้ายโดยอัตโนมัติ ดังนั้นเราจะได้อาร์เรย์ที่ถูกจัดเรียงแล้วดังนี้ 11 12 22 25 64

ตัวอย่างโค้ด Selection Sort

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n){
	for (int i = 0; i < n-1; i++)
	{
		int min_idx = i;
		for (int j = i+1; j < n; j++)
		{
		if (arr[j] < arr[min_idx])
			min_idx = j;
		}
		if (min_idx!=i)
			swap(arr[min_idx],arr[i]);
	}
}

void printArray(int arr[], int size){
	for (int i=0; i < size; i++)
	{
	cout << arr[i] << " ";
	}
}

int main(){
	int arr[] = {64, 25, 12, 22, 11};
	int n = sizeof(arr)/sizeof(arr[0]);
	selectionSort(arr, n);
	cout << "Sorted array: ";
	printArray(arr, n);
	return 0;
}

ผลลัพธ์:
Sorted array: 11 12 22 25 64

Time Complexity: O(N²)