Chương trình Quick Sort dùng đệ quy trong C#

Quick Sort là thuật toán sắp xếp sử dụng phương pháp chia để trị. Nó chọn một phần tử chốt (pivot) và đặt nó vào vị trí đúng. Sau đó, mảng bên trái và bên phải của pivot được sắp xếp lại bằng Quick Sort. Quá trình lặp lại cho đến khi toàn bộ mảng được sắp xếp.

Ví dụ

using System;

namespace QuickSortDemo
{
    class Example
    {
        static public int Partition(int[] arr, int left, int right)
        {
            int pivot = arr[left];
            
            while (true)
            {
                while (arr[left] < pivot)
                    left++;
                
                while (arr[right] > pivot)
                    right--;
                
                if (left < right)
                {
                    int temp = arr[right];
                    arr[right] = arr[left];
                    arr[left] = temp;
                }
                else
                {
                    return right;
                }
            }
        }
        
        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("Mảng ban đầu: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
            
            QuickSort(arr, 0, 9);
            
            Console.Write("\nMảng đã sắp xếp: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
        }
    }
}

Kết quả

Quick Sort
Mảng ban đầu: 67 12 95 56 85 1 100 23 60 9
Mảng đã sắp xếp: 1 9 12 23 56 60 67 85 95 100

Giải thích thuật toán

• Partition(): Chọn pivot là phần tử đầu tiên (arr[left]). Di chuyển hai con trỏ left/right về nhau, hoán đổi khi left < right. Trả về vị trí cuối cùng của pivot.
• QuickSort(): Gọi Partition để lấy pivot, sau đó đệ quy sắp xếp hai phần con.

Độ phức tạp: Trung bình O(n log n), Tệ nhất O(n²) (khi mảng đã sắp xếp hoặc pivot kém). Không ổn định (unstable).

Cải tiến: Chọn pivot ngẫu nhiên hoặc median-of-three để tránh trường hợp tệ nhất.