QuickSort cải tiến

Mã C++ với Quick Sort không đệ quy:

#include <iostream>
#include <vector>
#include <stack>

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) {
    stack<pair<int, int>> stk;
    stk.push({low, high});

    while (!stk.empty()) {
        int start = stk.top().first;
        int end = stk.top().second;
        stk.pop();

        if (start < end) {
            int pivotIndex = partition(arr, start, end);

            stk.push({start, pivotIndex - 1});
            stk.push({pivotIndex + 1, end});
        }
    }
}

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;
}

Giải thích Mã:

• Hàm partition và quickSort vẫn được giữ nguyên, chỉ có sự thay đổi ở hàm quickSort.
• Thay vì sử dụng đệ quy, chúng ta sử dụng một stack để lưu trữ các phần tử cần được xử lý.
• Ban đầu, ta đưa phần tử đầu và cuối của mảng vào stack.
• Tiếp theo, lặp qua stack. Mỗi lần lấy một phần tử ra, ta thực hiện phân chia và đẩy các phần tử con vào stack.
• Quá trình tiếp tục cho đến khi stack rỗng, lúc đó mảng đã được sắp xếp hoàn chỉnh.

Quick Sort sử dụng đệ quy đuôi:

1. Chọn Pivot và Phân Chia Mảng:

   • Chọn một phần tử làm pivot từ mảng.
   • Phân chia mảng thành hai phần: một phần có giá trị nhỏ hơn pivot và một phần có giá trị lớn hơn hoặc bằng pivot.

2. Sắp Xếp Các Phần Nhỏ Hơn và Lớn Hơn Pivot:

   • Sắp xếp đệ quy hai phần mảng con đã được phân chia.

3. Kết hợp Kết Quả:

   • Kết hợp các phần đã sắp xếp để có một mảng hoàn chỉnh được sắp xếp.

Mã C++ với Quick Sort đệ quy đuôi:

#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 quickSortTailRecursive(vector<int>& arr, int low, int high) {
    while (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSortTailRecursive(arr, low, pivotIndex - 1);
        low = pivotIndex + 1; // Thiết lập lại low cho mảng con bên phải
    }
}

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

Giải thích Mã:

• Hàm partition giữ nguyên như trong các phiên bản trước.
• Hàm quickSortTailRecursive thay vì sử dụng đệ quy, sử dụng vòng lặp while để thực hiện quá trình sắp xếp.
• Trong mỗi vòng lặp, chúng ta thực hiện phân chia và gọi đệ quy trên mảng con bên trái của pivot.
• Sau đó, thiết lập lại chỉ số low cho mảng con bên phải của pivot và tiếp tục vòng lặp cho đến khi low >= high.
• Khi low >= high, mảng đã được sắp xếp hoàn chỉnh.