Thuật toán sắp xếp nhanh Quicksort

Học lập trình

Thuật toán Quicksort là gì?

Quicksort là một thuật toán sắp xếp đệ quy được phát minh bởi Tony Hoare vào năm 1959. Thuật toán này hoạt động bằng cách chọn một phần tử làm pivot và phân hoạch các phần tử còn lại thành hai nhóm – một nhóm chứa các phần tử nhỏ hơn pivot và một nhóm chứa các phần tử lớn hơn pivot. Sau đó, thuật toán đệ quy áp dụng quá trình này cho từng nhóm con cho đến khi mỗi nhóm chỉ chứa một phần tử.

Quicksort là một trong những thuật toán sắp xếp nhanh nhất hiện nay với độ phức tạp trung bình là O(n log n). Thuật toán này có thể được cài đặt đệ quy hoặc không đệ quy, và có thể được tối ưu hóa bằng cách sử dụng phương pháp chọn pivot thông minh hoặc sử dụng thuật toán sắp xếp khác như insertion sort cho các mảng nhỏ hơn.

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

Thuật toán Quicksort được thực hiện theo các bước sau:

Bước 1. Chọn một phần tử từ mảng gọi là pivot.

Bước 2. Phân hoạch các phần tử còn lại thành hai nhóm – một nhóm chứa các phần tử nhỏ hơn pivot và một nhóm chứa các phần tử lớn hơn pivot.

Bước 3. Đưa pivot vào giữa hai nhóm, để tạo thành một mảng gồm các phần tử nhỏ hơn pivot ở bên trái và các phần tử lớn hơn pivot ở bên phải.

Bước 4. Lặp lại các bước trên đối với hai mảng con trái và phải, cho đến khi mỗi mảng con chỉ chứa một phần tử.

Kết hợp hai mảng con đã được sắp xếp theo thứ tự và đưa ra mảng đã được sắp xếp hoàn chỉnh.

Việc chọn pivot rất quan trọng trong Quicksort, vì nó ảnh hưởng đến hiệu quả của thuật toán. Một số phương pháp chọn pivot thông minh là sử dụng median-of-three (lấy giá trị trung bình của ba phần tử đầu tiên, giữa và cuối cùng của mảng làm pivot) hoặc random pivot (chọn ngẫu nhiên một phần tử làm pivot).

Ví dụ về Thuật toán Quicksort

Dưới đây là một ví dụ về cách sắp xếp một mảng các số nguyên bằng thuật toán Quicksort:

Giả sử ta có một mảng các số nguyên như sau:

[5, 2, 9, 3, 7, 6, 1, 8, 4]

  1. Ta chọn một phần tử làm pivot, ví dụ là 5.
  2. Phân hoạch các phần tử còn lại thành hai nhóm – một nhóm chứa các phần tử nhỏ hơn pivot và một nhóm chứa các phần tử lớn hơn pivot:
[2, 3, 1, 4] | 5 | [9, 7, 6, 8]

3. Đưa pivot vào giữa hai nhóm:

[2, 3, 1, 4, 5, 9, 7, 6, 8]

4. Lặp lại các bước trên đối với hai mảng con trái và phải:

[2, 3, 1, 4] | 5 | [9, 7, 6, 8]

[1] | 2 | [3, 4, 5] | 9 | [7, 6, 8]

[1] | 2 | [3] | 4 | [5] | 9 | [6] | 7 | [8]

5. Kết hợp hai mảng con đã được sắp xếp theo thứ tự và đưa ra mảng đã được sắp xếp hoàn chỉnh:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Cài đặt Thuật toán Quicksort với Python

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = [x for x in arr[1:] if x < pivot]
        right = [x for x in arr[1:] if x >= pivot]
        return quicksort(left) + [pivot] + quicksort(right)

# Ví dụ sử dụng hàm quicksort
arr = [5, 2, 9, 3, 7, 6, 1, 8, 4]
print(quicksort(arr)) # [1, 2, 3, 4, 5, 6, 7, 8, 9]

Cài đặt Thuật toán Quicksort với C++

#include <iostream>
#include <vector>

using namespace std;

void quicksort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int pivot = arr[(left + right) / 2];
        int i = left - 1;
        int j = right + 1;
        while (true) {
            do {
                i++;
            } while (arr[i] < pivot);
            do {
                j--;
            } while (arr[j] > pivot);
            if (i >= j) {
                break;
            }
            swap(arr[i], arr[j]);
        }
        quicksort(arr, left, j);
        quicksort(arr, j + 1, right);
    }
}

int main() {
    vector<int> arr = {5, 2, 9, 3, 7, 6, 1, 8, 4};
    quicksort(arr, 0, arr.size() - 1);
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

Tổng kết về Thuật toán Quicksort

Quicksort là một trong những thuật toán sắp xếp nổi tiếng và phổ biến nhất hiện nay. Với chi phí thời gian trung bình O(n log n), Quicksort cho phép sắp xếp nhanh chóng một mảng các phần tử. Nó hoạt động bằng cách chọn một phần tử làm pivot, phân hoạch các phần tử còn lại thành hai nhóm trái và phải tương ứng với các phần tử nhỏ hơn và lớn hơn pivot, rồi đệ quy sắp xếp hai nhóm này và ghép kết quả lại để tạo thành mảng đã được sắp xếp hoàn chỉnh.

Tuy nhiên, Quicksort cũng có nhược điểm, đặc biệt là trong trường hợp tệ nhất, nó có thể đạt đến chi phí thời gian O(n^2), khi mà pivot được chọn không đủ tốt, dẫn đến việc phân hoạch tạo ra các mảng con không cân bằng. Để giảm thiểu tình trạng này, các phương pháp khác nhau đã được đề xuất, như sử dụng pivot ngẫu nhiên, pivot trung vị hoặc pivot ngẫu nhiên từ một tập hợp nhỏ các phần tử được chọn trước đó.

Tóm lại, Quicksort là một thuật toán sắp xếp rất hiệu quả và được sử dụng rộng rãi trong các ứng dụng thực tế. Nó cũng cần được áp dụng một số kỹ thuật để giảm thiểu tình trạng tồi nhất và tối ưu hóa hiệu suất.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *