Toán tin vuotlen.com

Thuật Toán Sắp Xếp Nhanh (QuickSort)

Phân loại: Giải thuật sắp xếp không ổn định.

Cấu trúc dữ liệu: Ngẫu nhiên.
Độ phức tạp thời gian (Time Complexity): Trường hợp xấu nhất (Worst Case) O(n2) (xảy ra khi các phần tử đã sắp xếp hoặc pivot không được chọn tốt).

Độ phức tạp dung lượng (Space Complexity): O(n) (trong trường hợp đệ quy không cân bằng).

Độ phức tạp bộ nhớ (Memory Complexity): O(n) bộ nhớ phụ thuộc vào ngăn xếp đệ quy.

Cải tiến: Quick Sort có thể tối ưu hóa để giảm không gian phụ thông qua việc triển khai phiên bản không đệ quy hoặc sử dụng đệ quy đuôi.

Lịch sử thuật toán sắp xếp nhanh (Quick Sort):

Thuật toán Quick Sort được phát minh bởi Tony Hoare vào năm 1960. Tony Hoare đã phát triển thuật toán này khi ông còn là sinh viên tại Đại học Cambridge. Quick Sort được biết đến với hiệu suất cao và là một trong những thuật toán sắp xếp phổ biến nhất.

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

Quick Sort hoạt động theo nguyên tắc "chia để trị" (divide and conquer). Các bước chính của thuật toán bao gồm:

  1. Chọn một phần tử làm chốt (pivot): Phần tử này có thể được chọn ngẫu nhiên, chọn phần tử đầu, cuối, hoặc phần tử giữa.
  2. Phân hoạch (partition): Sắp xếp lại mảng sao cho tất cả các phần tử nhỏ hơn pivot nằm bên trái pivot và tất cả các phần tử lớn hơn pivot nằm bên phải.
  3. Đệ quy: Áp dụng quy trình trên cho hai mảng con (bên trái và bên phải pivot).

Ứng dụng của Quick Sort:

Quick Sort được sử dụng rộng rãi trong nhiều ứng dụng đòi hỏi sắp xếp dữ liệu, chẳng hạn như:

Ứng dụng nổi tiếng sử dụng Quick Sort:

Nhiều thư viện và framework nổi tiếng sử dụng Quick Sort cho các chức năng sắp xếp của họ, bao gồm:

Mã giả của Quick Sort:

procedure quicksort(A, low, high)  // Hàm quicksort được gọi với mảng A và các chỉ số low, high.
    if low < high then     // Nếu low nhỏ hơn high, nghĩa là mảng con có ít nhất hai phần tử.   
        pivotIndex := partition(A, low, high) // Gọi hàm partition để sắp xếp lại mảng và nhận vị trí của pivot.
        quicksort(A, low, pivotIndex - 1)        // Đệ quy gọi hàm quicksort cho mảng con bên trái của pivot.
        quicksort(A, pivotIndex + 1, high)    // Đệ quy gọi hàm quicksort cho mảng con bên phải của pivot.
     procedure partition(A, low, high)  // Hàm partition sắp xếp mảng và trả về vị trí của pivot. 
    pivot := A[high]     // Chọn phần tử cuối cùng của mảng làm pivot. 
    i := low - 1   // i là chỉ số của phần tử lớn hơn pivot.
    for j := low to high - 1 do   // Duyệt qua các phần tử từ low đến high - 1.
        if A[j] < pivot then        // Nếu phần tử hiện tại nhỏ hơn pivot:
            i := i + 1     // Tăng chỉ số i.
            swap A[i] with A[j] // Đổi chỗ phần tử tại i với phần tử tại j.
    swap A[i + 1] with A[high]    // Đổi chỗ phần tử ngay sau i với phần tử pivot.
    return i + 1  // Trả về vị trí của pivot.
 
code C++:

#include <iostream>
#include <vector>

using namespace std;

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

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: ";
    for (int x : arr) {
        cout << x << " ";
    }
    return 0;
}

 

Dùng mảng {10, 7, 8, 9, 1, 5} để minh họa:

Bước 1: Khởi tạo

Bước 2: Quicksort

Bước 3: Đệ quy

Lần gọi đệ quy thứ nhất: quickSort(arr, 0, 0)

Lần gọi đệ quy thứ hai: quickSort(arr, 2, 5)

Bước 4: Kết quả

Vậy là chương trình đã sắp xếp mảng ban đầu {10, 7, 8, 9, 1, 5} thành {1, 5, 7, 8, 9, 10} sử dụng thuật toán quicksort.