Thuật Toán Quick Sort (Sắp Xếp Nhanh) Trong C++: Giải Thích Chi Tiết, Dễ Hiểu Kèm Ví Dụ

Quick Sort (Sắp xếp nhanh) là một trong những thuật toán sắp xếp hiệu quả và phổ biến nhất trong lập trình C++. Bài viết này sẽ cung cấp cho bạn cái nhìn chi tiết, dễ hiểu về Quick Sort, giúp bạn nắm vững nguyên lý hoạt động và áp dụng nó một cách hiệu quả.

I. Tổng Quan Về Quick Sort

1. Định Nghĩa Quick Sort

Quick Sort là một thuật toán sắp xếp thuộc loại so sánh, hoạt động dựa trên nguyên tắc “chia để trị” (Divide and Conquer). Ý tưởng chính của thuật toán là chọn một phần tử làm “chốt” (pivot), sau đó phân chia mảng thành hai mảng con: một mảng chứa các phần tử nhỏ hơn hoặc bằng chốt, và một mảng chứa các phần tử lớn hơn chốt. Quá trình này được thực hiện đệ quy trên các mảng con cho đến khi toàn bộ mảng được sắp xếp.

Minh họa thuật toán Quick SortMinh họa thuật toán Quick Sort

2. Cách Thức Hoạt Động Của Quick Sort

Quick Sort hoạt động theo các bước sau:

  1. Chọn Chốt (Pivot): Chọn một phần tử trong mảng làm chốt. Việc lựa chọn chốt ảnh hưởng lớn đến hiệu suất của thuật toán. Các phương pháp chọn chốt phổ biến bao gồm:

    • Chọn phần tử đầu tiên.
    • Chọn phần tử cuối cùng.
    • Chọn phần tử trung vị.
    • Chọn ngẫu nhiên.

  2. Phân Vùng (Partitioning): Sắp xếp lại mảng sao cho tất cả các phần tử nhỏ hơn hoặc bằng chốt nằm trước chốt, và tất cả các phần tử lớn hơn chốt nằm sau chốt. Sau bước này, chốt nằm đúng vị trí cuối cùng trong mảng đã sắp xếp.

  3. Đệ Quy (Recursion): Gọi đệ quy Quick Sort trên hai mảng con: mảng các phần tử nhỏ hơn chốt và mảng các phần tử lớn hơn chốt.

II. Giải Thuật Quick Sort Chi Tiết

1. Hàm Partition (Phân Vùng)

Hàm partition là trái tim của thuật toán Quick Sort. Hàm này nhận vào mảng, chỉ số đầu low, chỉ số cuối high, và thực hiện việc phân vùng mảng dựa trên chốt.

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Chọn phần tử cuối làm chốt
    int i = (low - 1); // Chỉ số của phần tử nhỏ hơn

    for (int j = low; j <= high - 1; j++) {
        // Nếu phần tử hiện tại nhỏ hơn hoặc bằng chốt
        if (arr[j] <= pivot) {
            i++; // Tăng chỉ số của phần tử nhỏ hơn
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}

Hàm Partition trong Quick SortHàm Partition trong Quick Sort

Giải thích:

  • pivot: Phần tử được chọn làm chốt, trong ví dụ này là phần tử cuối cùng của mảng con.
  • i: Chỉ số của phần tử cuối cùng nhỏ hơn chốt.
  • Vòng lặp for: Duyệt qua mảng từ low đến high - 1. Nếu một phần tử arr[j] nhỏ hơn hoặc bằng pivot, ta tăng i và đổi chỗ arr[i] và arr[j].
  • Cuối cùng, đổi chỗ arr[i + 1] và arr[high] để đưa chốt về đúng vị trí của nó trong mảng đã sắp xếp.
  • Hàm trả về chỉ số của chốt sau khi phân vùng.

2. Hàm Quick Sort

Hàm quickSort thực hiện sắp xếp đệ quy trên các mảng con.

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi là chỉ số phân vùng, arr[p] *đã ở đúng vị trí*
        int pi = partition(arr, low, high);

        // Sắp xếp riêng các phần tử trước phân vùng và
        // sau phân vùng
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Giải thích:

  • Điều kiện if (low < high): Đảm bảo rằng có ít nhất hai phần tử trong mảng con để sắp xếp.
  • pi = partition(arr, low, high): Gọi hàm partition để phân vùng mảng. pi là chỉ số của chốt sau khi phân vùng.
  • quickSort(arr, low, pi - 1): Gọi đệ quy quickSort trên mảng con bên trái chốt.
  • quickSort(arr, pi + 1, high): Gọi đệ quy quickSort trên mảng con bên phải chốt.

3. Hàm Swap (Đổi Chỗ)

Hàm swap dùng để đổi chỗ hai phần tử trong mảng. Trong C++, bạn có thể sử dụng trực tiếp hàm std::swap từ thư viện <algorithm>.

#include <algorithm>

// ...
std::swap(arr[i], arr[j]);
// ...

III. Ví Dụ Minh Họa Quick Sort

Đề bài: Sắp xếp mảng arr[] = {9, -3, 5, 2, 6, 8, -6, 1, 3} theo thứ tự tăng dần sử dụng thuật toán Quick Sort.

Code C++:

#include <iostream>
#include <algorithm>

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}

int main() {
    int arr[] = {9, -3, 5, 2, 6, 8, -6, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    std::cout << "Mảng sau khi sắp xếp: ";
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
    return 0;
}

Kết quả:

Mảng sau khi sắp xếp: -6 -3 1 2 3 5 6 8 9

Kết quả Input và Output của Quick SortKết quả Input và Output của Quick Sort

IV. Đánh Giá Hiệu Suất Của Quick Sort

  • Độ phức tạp thời gian:
    • Trường hợp tốt nhất: O(n log n)
    • Trường hợp trung bình: O(n log n)
    • Trường hợp xấu nhất: O(n^2) (xảy ra khi chốt luôn là phần tử nhỏ nhất hoặc lớn nhất)
  • Độ phức tạp không gian: O(log n) (do sử dụng đệ quy)

Quick Sort thường được coi là một trong những thuật toán sắp xếp nhanh nhất trong thực tế. Tuy nhiên, hiệu suất của nó phụ thuộc nhiều vào việc lựa chọn chốt.

V. Lời Kết

Quick Sort là một thuật toán sắp xếp mạnh mẽ và được sử dụng rộng rãi. Việc hiểu rõ nguyên lý hoạt động và cách triển khai Quick Sort sẽ giúp bạn giải quyết các bài toán sắp xếp một cách hiệu quả hơn. Hy vọng bài viết này đã cung cấp cho bạn kiến thức cần thiết để làm chủ thuật toán Quick Sort trong C++. Chúc bạn thành công!