โปรแกรม Quick Sort แบบ Recursive ใน C#

ภาพรวม

Quick Sort เป็นอัลกอริทึมการจัดเรียงแบบ Divide and Conquer ที่มีประสิทธิภาพสูง เลือก Pivot (องค์ประกอบเกณฑ์) แล้วจัดเรียงใหม่โดยวางค่าน้อยกว่า Pivot ไปทางซ้าย และค่ามากกว่าไปทางขวา จากนั้นเรียกตัวเองซ้ำ (Recursive) กับสองส่วนย่อย จนกว่าจะจัดเรียงเสร็จทั้งอาร์เรย์

ตัวอย่างโปรแกรม Quick Sort (Recursive)

using System;

namespace QuickSortDemo
{
    class Example
    {
        // ฟังก์ชัน Partition: เลือก Pivot และจัดเรียง
        static public int Partition(int[] arr, int left, int right)
        {
            int pivot = arr[left]; // เลือกองค์ประกอบแรกเป็น Pivot
            
            while (true)
            {
                // หาองค์ประกอบที่ >= Pivot จากซ้าย
                while (arr[left] < pivot)
                    left++;
                
                // หาองค์ประกอบที่ <= Pivot จากขวา
                while (arr[right] > pivot)
                    right--;
                
                // หากยังไม่ทับซ้อน ให้สลับ
                if (left < right)
                {
                    int temp = arr[right];
                    arr[right] = arr[left];
                    arr[left] = temp;
                }
                else
                {
                    return right; // คืนตำแหน่งแบ่งสุดท้าย
                }
            }
        }
        
        // ฟังก์ชัน Quick Sort หลัก
        static public void QuickSort(int[] arr, int left, int right)
        {
            if (left < right)
            {
                int pivot = Partition(arr, left, right);
                
                // เรียกซ้ำสำหรับส่วนซ้าย (ถ้ามีข้อมูล)
                if (pivot > 1)
                    QuickSort(arr, left, pivot - 1);
                
                // เรียกซ้ำสำหรับส่วนขวา (ถ้ามีข้อมูล)
                if (pivot + 1 < right)
                    QuickSort(arr, pivot + 1, right);
            }
        }
        
        static void Main(string[] args)
        {
            int[] arr = { 67, 12, 95, 56, 85, 1, 100, 23, 60, 9 };
            int n = 10, i;
            
            Console.WriteLine("Quick Sort");
            Console.Write("อาร์เรย์เริ่มต้น: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
            
            QuickSort(arr, 0, 9);
            
            Console.Write("\nอาร์เรย์ที่จัดเรียงแล้ว: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
        }
    }
}

ผลลัพธ์

Quick Sort
อาร์เรย์เริ่มต้น: 67 12 95 56 85 1 100 23 60 9
อาร์เรย์ที่จัดเรียงแล้ว: 1 9 12 23 56 60 67 85 95 100

การทำงานของ Partition (Hoare Partition Scheme)

int pivot = arr[left];
while (true)
{
    while (arr[left] < pivot) left++;
    while (arr[right] > pivot) right--;
    
    if (left < right)
    {
        Swap(arr[left], arr[right]);
    }
    else
    {
        return right; // จุดแบ่ง
    }
}

ขั้นตอน:

1. เลือก Pivot (ที่นี่คือองค์ประกอบแรก)
2. เลื่อน pointer ซ้ายไปขวา จนพบค่า ≥ Pivot
3. เลื่อน pointer ขวาไปซ้าย จนพบค่า ≤ Pivot
4. ถ้ายังไม่ทับซ้อน ให้สลับค่า
5. ซ้ำจนกว่าจะทับซ้อน แล้วคืนตำแหน่งแบ่ง

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

กรณีแย่ที่สุดเกิดเมื่อ Pivot เป็นค่ามากที่สุดหรือน้อยที่สุดเสมอ (ข้อมูลเรียงลำดับแล้ว)

การปรับปรุงประสิทธิภาพ

• Pivot Selection: ใช้ Median-of-three (กลาง, แรก, สุดท้าย) หรือ Random pivot
• Tail Recursion Elimination: แปลง recursive call สุดท้ายเป็น loop
• Insertion Sort สำหรับอาร์เรย์เล็ก: สลับไปใช้ Insertion Sort เมื่อขนาด < 10-20
• 3-way Partition: สำหรับข้อมูลที่มีค่าซ้ำมาก (Dutch National Flag)

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

• In-place: ใช้พื้นที่ O(log n) สำหรับ stack
• ไม่เสถียร (Unstable): ค่าเท่ากันอาจสลับตำแหน่ง
• ใน .NET ใช้ Array.Sort() (Introsort: QuickSort + HeapSort + InsertionSort) ซึ่งจัดการกรณีแย่ที่สุดได้ดีกว่า