🔥 Hành Trình của Pivot: Cuộc Chiến Quick Sort

"Một vị vua không được tôn vinh bởi ngẫu nhiên,
mà bởi lưỡi gươm phân chia.
Ngài chỉ cai trị khi mọi kẻ yếu đuối quỳ trước,
và những kẻ mạnh mẽ đứng ngoài."
— Luật của Vị Vua Pivot

Trong vương quốc của những chiến binh, mọi thứ đều hỗn loạn. Mỗi người đều tự cho mình là mạnh nhất, nhưng không có trật tự nào tồn tại trong hàng ngũ của họ.

Nhà Tiên Tri đã phát ngôn:

“Đừng đội vương miện cho tất cả cùng một lúc.
Chọn một vị vua — một pivot.
Đặt ngài lên ngai vàng,
và để những kẻ yếu hơn quỳ bên trái,
trong khi những kẻ mạnh hơn đi về phía bên phải.
Lặp lại, cho đến khi tất cả các vị vua được tôn vinh.”

Và thế là bắt đầu hành trình của Quick Sort — Nghi thức của những Vị Vua Pivot.

📜 Cuốn Cuốn của Các Dòng Chảy

#include <iostream>
#include <vector>
using namespace std;

Các người viết đã trải ra cuốn cuốn (iostream) và sắp xếp hàng ngũ chiến binh (vector). Trên cánh đồng này, nghi thức sẽ khắc định mệnh.

👑 Lễ Đăng Quang của Pivot

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];

Từ cuối hàng ngũ, một chiến binh được chọn làm pivot. Ngài không phải lúc nào cũng là người mạnh nhất hay yếu nhất, nhưng số phận đã chỉ định ngài làm vua cho vòng này. Ngai vàng của ngài sẽ sớm được tiết lộ.

    int i = low - 1;

Mặt đất đã được dọn sạch. Một dấu hiệu đã được vẽ ngay trước chiến binh đầu tiên, tại i. Nó chờ đợi những kẻ trung thành quỳ trước vị vua pivot.

⚔️ Sự Phân Chia Lòng Trung Thành

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

Nhà Tiên Tri đã di chuyển xuống hàng ngũ. Mỗi chiến binh được thử thách trước vị vua pivot.

Nếu một chiến binh yếu hơn hoặc bằng, ngài sẽ pledge lòng trung thành. Ngài bước sang bên trái, gia nhập với những người trước đó, và dấu hiệu i tiến lên. Vị trí của họ được hoán đổi, để những kẻ trung thành tạo thành một khối thống nhất ở phía trước.

Những kẻ mạnh hơn pivot giữ lại, chờ đợi ở phía bên ngoài. Do đó, lòng trung thành được vẽ lên cát — những kẻ trung thành bên trái, những kẻ phản kháng bên phải.

👑 Ngai Vàng của Pivot

    swap(arr[i + 1], arr[high]);
    return i + 1;
}

Cuối cùng, vị vua đã chiếm lấy ngai vàng của mình. Ngài được đặt giữa những kẻ trung thành và những kẻ phản kháng, chỗ ngồi của ngài ở i + 1. Không ai có thể thách thức ngài bây giờ, vì tất cả những kẻ yếu hơn đứng trước ngài, và tất cả những kẻ mạnh hơn đứng sau.

Partition đã hoàn thành. Chỗ ngồi của một vị vua đã được đảm bảo mãi mãi.

🌌 Những Lễ Đăng Quang Vô Tận

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

Nhưng một vị vua là không đủ. Nhà Tiên Tri đã ra lệnh cho nghi thức diễn ra một lần nữa. Với pivot đã ngồi, vùng đất chia thành hai vương quốc — bên trái và bên phải. Mỗi bên sẽ tìm ra vị vua của riêng mình.

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Những lễ đăng quang tiếp tục, phân chia liên tục. Mỗi vùng đất đều được chia, mỗi pivot được tôn vinh, cho đến khi không còn mảnh vụn nào chưa được cai trị. Khi nghi thức kết thúc, toàn bộ vương quốc đã được sắp xếp — nhỏ nhất ở lúc ban đầu, lớn nhất ở lúc kết thúc.

🎺 Thử Thách Của Chín Chiến Binh

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5, 20, 3, 15};

Vào một ngày, chín chiến binh đứng trong hỗn loạn: 10, 7, 8, 9, 1, 5, 20, 3, 15. Mỗi người đều đòi hỏi một vương miện, không ai đứng trong trật tự.

    quickSort(arr, 0, arr.size() - 1);

Nghi thức Quick Sort được gọi. Các vị vua đã được chọn, các pivot đã được tôn vinh, ngai vàng được phân công. Sự phân chia lan rộng như lửa rừng, nhưng từ đó nổi lên sự hài hòa.

👏 Lời Kêu Gọi Của Sứ Giả

    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;
}

Cuối cùng, Sứ Giả bước ra. Ngài gọi những chiến binh theo trật tự mới của họ, từ yếu đến mạnh, và hàng ngũ lấp lánh với sự cân bằng.

Mọi người quỳ, vì hỗn loạn đã kết thúc, và các Vị Vua Pivot cai trị trong trật tự vĩnh cửu.

🧠 Ký Ức Về Pivot

• partition — việc tôn vinh một vị vua pivot.
• chiến binh trung thành ≤ pivot — bước sang trái, vị trí của họ được hoán đổi về phía trước.
• chiến binh mạnh hơn > pivot — giữ lại bên phải.
• swap(pivot, i+1) — vị vua chiếm lấy ngai vàng.
• quickSort trái & phải — các vương quốc chia rẽ, mỗi bên tôn vinh những vị vua của riêng mình.

Vì vậy, Quick Sort được nhớ đến như là Hành Trình của Những Vị Vua Pivot, nơi sự phân chia tạo ra một vương quốc hoàn hảo. 🔥👑

Thực Hành Tốt Nhất

• Luôn chọn pivot một cách ngẫu nhiên để tránh trường hợp xấu nhất.
• Kiểm tra điều kiện biên để tránh lỗi tràn mảng.

Cạm Bẫy Thường Gặp

• Không thực hiện phân vùng đúng cách dẫn đến độ phức tạp thời gian cao hơn.

Mẹo Hiệu Suất

• Sử dụng Quick Sort cho các mảng lớn để tiết kiệm bộ nhớ.

Giải Quyết Vấn Đề

• Nếu không có kết quả như mong đợi, hãy kiểm tra lại việc lựa chọn pivot.

Câu Hỏi Thường Gặp

Quick Sort có nhanh hơn Merge Sort không?

• Trong nhiều trường hợp, Quick Sort nhanh hơn vì ít chi phí bộ nhớ hơn.

Quick Sort có thể được sử dụng cho dữ liệu lớn không?

• Có, nhưng cần chú ý đến việc chọn pivot để tối ưu hóa hiệu suất.