โปรแกรม Selection Sort ใน C#

ภาพรวม

Selection Sort เป็นอัลกอริทึมจัดเรียงที่ง่ายที่สุด ทำงานโดย:

1. หาค่าน้อยที่สุด (Minimum) ในส่วนที่ยังไม่เรียง
2. สลับค่านั้นกับองค์ประกอบแรกของส่วนที่ยังไม่เรียง
3. ขยายส่วนที่เรียงแล้วทีละหนึ่ง ทำซ้ำจนครบทุกอย่าง

Selection Sort ทำการสลับ (swap) น้อยที่สุดในกลุ่ม O(n²) - สลับเพียง n-1 ครั้งเท่านั้น

ตัวอย่างโปรแกรม

using System;

public class Example
{
    static void Main(string[] args)
    {
        int[] arr = new int[10] { 56, 1, 99, 67, 89, 23, 44, 12, 78, 34 };
        int n = 10;
        
        Console.WriteLine("Selection Sort");
        Console.Write("อาร์เรย์เริ่มต้น: ");
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
        
        int temp, smallest;
        
        // ลูปหลัก: i = ตำแหน่งที่จะวางค่าน้อยที่สุด
        for (int i = 0; i < n - 1; i++)
        {
            smallest = i; // สมมติว่าตำแหน่ง i น้อยที่สุด
            
            // หาค่าน้อยที่สุดในส่วนที่เหลือ
            for (int j = i + 1; j < n; j++)
            {
                if (arr[j] < arr[smallest])
                    smallest = j;
            }
            
            // สลับค่าน้อยที่สุดกับตำแหน่ง i
            temp = arr[smallest];
            arr[smallest] = arr[i];
            arr[i] = temp;
        }
        
        Console.WriteLine();
        Console.Write("อาร์เรย์ที่จัดเรียงแล้ว: ");
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
}

ผลลัพธ์

Selection Sort
อาร์เรย์เริ่มต้น: 56 1 99 67 89 23 44 12 78 34
อาร์เรย์ที่จัดเรียงแล้ว: 1 12 23 34 44 56 67 78 89 99

การทำงานแบบทีละขั้นตอน

1. เริ่มต้น

arr = [56, 1, 99, 67, 89, 23, 44, 12, 78, 34]
ส่วนที่เรียงแล้ว: [] | ส่วนที่ยังไม่: [56, 1, 99, 67, 89, 23, 44, 12, 78, 34]

2. รอบที่ 1 (i=0): หาค่าน้อยที่สุดทั้งอาร์เรย์ = 1

smallest = 1 (ดัชนี 1, ค่า 1)
สลับ arr[0] ↔ arr[1]
arr = [1, 56, 99, 67, 89, 23, 44, 12, 78, 34]

3. รอบที่ 2 (i=1): หาค่าน้อยที่สุดในดัชนี 1-9 = 12

smallest = 7 (ดัชนี 7, ค่า 12)
สลับ arr[1] ↔ arr[7]
arr = [1, 12, 99, 67, 89, 23, 44, 56, 78, 34]

4. ดำเนินต่อไปจนครบ...

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

Selection Sort มีเวลาคงที่ O(n²) ไม่ว่าข้อมูลจะเรียงอยู่แล้วหรือไม่ก็ตาม

ข้อสังเกตสำคัญ

• ไม่เสถียร (Unstable) - การสลับอาจเปลี่ยนลำดับค่าเท่ากัน
• In-place: ใช้พื้นที่ O(1)
• Swap น้อยที่สุด: เพียง n-1 ครั้ง - ดีสำหรับหน่วยความจำที่เขียนได้ยาก (EEPROM, Flash)
• ไม่เหมาะสำหรับข้อมูลขนาดใหญ่ ใช้เพื่อการศึกษาหรือข้อมูลเล็กมาก
• ไม่ได้ใช้ในทางปฏิบัติ แต่อยู่ใน Introsort เป็น fallback สำหรับขนาดเล็กมาก

การปรับปรุง: Bidirectional Selection Sort (Cocktail Selection Sort)

หาค่าน้อยที่สุดและมากที่สุดพร้อมกันในแต่ละรอบ วางที่ปลายทั้งสองด้าน → ลดจำนวนรอบลงครึ่งหนึ่ง

for (int i = 0, j = n - 1; i < j; i++, j--)
{
    int minIdx = i, maxIdx = i;
    for (int k = i; k <= j; k++)
    {
        if (arr[k] < arr[minIdx]) minIdx = k;
        if (arr[k] > arr[maxIdx]) maxIdx = k;
    }
    Swap(arr[i], arr[minIdx]);
    // ปรับ maxIdx หากมันอยู่ที่ i เดิม
    if (maxIdx == i) maxIdx = minIdx;
    Swap(arr[j], arr[maxIdx]);
}