Thuật toán sắp xếp Quicksort trong C#

Các bước thực hiện thuật toán Quicksort:

1. Chọn một phần tử trong mảng gọi là phần tử pivot. Thông thường, phần tử cuối cùng trong mảng được chọn làm pivot.
2. Đặt hai con trỏ tại đầu và cuối mảng.
3. Di chuyển con trỏ bên trái tìm phần tử đầu tiên lớn hơn hoặc bằng pivot.
4. Di chuyển con trỏ bên phải tìm phần tử đầu tiên nhỏ hơn hoặc bằng pivot.
5. Nếu hai con trỏ chưa gặp nhau, hoán đổi hai phần tử được chỉ bởi chúng và tiếp tục từ bước 3.
6. Khi hai con trỏ gặp nhau, hoán đổi phần tử tại vị trí đó với pivot. Bước này đảm bảo rằng pivot đang ở đúng vị trí của nó trong mảng được sắp xếp.
7. Sau đó, quá trình được lặp lại đối với mảng con bên trái và mảng con bên phải của pivot. Đệ quy được sử dụng để sắp xếp các mảng con này.
8. Quá trình sắp xếp kết thúc khi mảng con chỉ chứa một phần tử hoặc không có phần tử nào cần sắp xếp.
9. Cuối cùng, mảng được sắp xếp được trả về.

Với cách thức hoạt động này, Quicksort là một trong những thuật toán sắp xếp hiệu quả nhất với độ phức tạp trung bình là O(n log n) và làm việc tốt với các tập dữ liệu lớn.

Dưới đây là một ví dụ về thuật toán sắp xếp Quicksort trong C#:

using System;

class Quicksort {
    static void Main() {
        int[] arr = { 5, 2, 8, 3, 9, 4, 1, 7, 6 };
        QuicksortAlgorithm(arr, 0, arr.Length - 1);
        for (int i = 0; i < arr.Length; i++) {
            Console.Write(arr[i] + " ");
        }
    }

    static void QuicksortAlgorithm(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = Partition(arr, left, right);
            QuicksortAlgorithm(arr, left, pivotIndex - 1);
            QuicksortAlgorithm(arr, pivotIndex + 1, right);
        }
    }

    static int Partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp2 = arr[i + 1];
        arr[i + 1] = arr[right];
        arr[right] = temp2;
        return i + 1;
    }
}

Trong ví dụ này, một mảng được khởi tạo và truyền vào phương thức QuicksortAlgorithm với các tham số left và right được thiết lập cho đầu và cuối của mảng. Phương thức QuicksortAlgorithm được gọi đệ quy đến khi left bằng hoặc lớn hơn right.

Phương thức Partition được sử dụng để tìm chỉ số của phần tử pivot và chia mảng thành hai phần. Các phần tử nhỏ hơn pivot được đưa về phía bên trái của pivot và các phần tử lớn hơn pivot được đưa về phía bên phải của pivot. Cuối cùng, phần tử pivot được đưa vào giữa hai phần.

Sau khi các phần tử được sắp xếp, mảng được xuất ra màn hình bằng cách sử dụng vòng lặp for.