Bài 14.5: Bài tập tổng hợp về Quick Sort

Chào mừng các bạn quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật của FullhouseDev!

Sau khi đã cùng nhau "mổ xẻ" và hiểu rõ cơ chế hoạt động đầy mạnh mẽ của Quick Sort – một trong những thuật toán sắp xếp dựa trên nguyên lý chia để trị (divide and conquer) được sử dụng rộng rãi nhất, đã đến lúc chúng ta xắn tay áo lên và áp dụng nó vào thực tế thông qua các bài tập. Lý thuyết là nền tảng, nhưng thực hành mới giúp chúng ta thực sự nắm vững và hiểu sâu sắc về sức mạnh cũng như những điểm cần lưu ý của Quick Sort.

Trong bài viết này, chúng ta sẽ cùng nhau giải quyết một số bài tập kinh điển và các biến thể thú vị liên quan đến Quick Sort. Tất cả các ví dụ minh họa sẽ được triển khai bằng C++, ngôn ngữ quen thuộc và hiệu quả cho việc học các thuật toán cơ bản.

Hãy cùng bắt đầu hành trình thực chiến với Quick Sort nhé!

Nhắc Lại Nhanh về Quick Sort

Trước khi đi vào bài tập, hãy cùng lướt qua các bước chính của Quick Sort:

Chọn Pivot: Chọn một phần tử làm pivot (điểm chốt) trong mảng/danh sách cần sắp xếp. Việc chọn pivot ảnh hưởng đến hiệu suất của thuật toán (có thể chọn phần tử đầu, cuối, giữa, hoặc ngẫu nhiên).
Phân hoạch (Partition): Sắp xếp lại các phần tử còn lại sao cho tất cả các phần tử nhỏ hơn pivot nằm ở bên trái nó, và tất cả các phần tử lớn hơn pivot nằm ở bên phải nó. Các phần tử bằng pivot có thể ở bất kỳ bên nào. Sau bước này, pivot nằm ở vị trí đúng của nó trong mảng đã sắp xếp. Hàm thực hiện bước này được gọi là hàm partition.
Đệ quy: Lặp lại quá trình Quick Sort một cách đệ quy cho mảng con ở bên trái pivot và mảng con ở bên phải pivot.

Quá trình đệ quy dừng lại khi mảng con chỉ còn 0 hoặc 1 phần tử (vì mảng như vậy đã được sắp xếp).

Bây giờ, chúng ta hãy thử sức với các bài tập!

Bài tập 1: Chuẩn hóa việc triển khai Quick Sort cơ bản

Đây là bài tập khởi động, giúp chúng ta củng cố lại cấu trúc cơ bản của Quick Sort. Chúng ta sẽ triển khai Quick Sort để sắp xếp một mảng số nguyên theo thứ tự tăng dần.

Yêu cầu:

Viết hàm quickSort nhận vào một mảng số nguyên và sắp xếp nó tăng dần. Sử dụng phần tử cuối cùng của mảng con làm pivot.

Mã nguồn C++:

#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

// Hàm phân hoạch (Partition)
// Nhận mảng, chỉ số bắt đầu (low), chỉ số kết thúc (high)
// Chọn phần tử cuối cùng (arr[high]) làm pivot
// Đặt pivot vào đúng vị trí trong mảng con,
// các phần tử nhỏ hơn pivot sang trái, lớn hơn sang phải
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // Chọn phần tử cuối làm pivot
    int i = (low - 1);     // Chỉ số của phần tử nhỏ hơn

    // Duyệt từ phần tử đầu (low) đến gần cuối (high-1)
    for (int j = low; j <= high - 1; j++) {
        // Nếu phần tử hiện tại nhỏ hơn hoặc bằng pivot
        if (arr[j] <= pivot) {
            i++; // Tăng chỉ số của phần tử nhỏ hơn
            // Hoán đổi arr[i] và arr[j]
            // arr[i] luôn trỏ đến vị trí mà phần tử nhỏ hơn pivot nên được đặt vào
            std::swap(arr[i], arr[j]);
        }
    }
    // Đặt pivot vào đúng vị trí của nó (sau tất cả các phần tử nhỏ hơn hoặc bằng)
    std::swap(arr[i + 1], arr[high]);
    // Trả về chỉ số của pivot sau khi phân hoạch
    return (i + 1);
}

// Hàm Quick Sort
// Nhận mảng, chỉ số bắt đầu (low), chỉ số kết thúc (high)
void quickSort(std::vector<int>& arr, int low, int high) {
    // Điều kiện dừng đệ quy: mảng con có 0 hoặc 1 phần tử
    if (low < high) {
        // pi là chỉ số của pivot sau khi phân hoạch
        int pi = partition(arr, low, high);

        // Đệ quy cho mảng con bên trái pivot
        quickSort(arr, low, pi - 1);
        // Đệ quy cho mảng con bên phải pivot
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();

    std::cout << "Mang ban dau: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    quickSort(arr, 0, n - 1);

    std::cout << "Mang sau khi sap xep tang dan: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Giải thích mã nguồn:

Hàm partition(arr, low, high):
- Nó chọn arr[high] làm pivot.
- Biến i theo dõi chỉ số của phần tử nhỏ hơn pivot. Ban đầu nó là low - 1.
- Vòng lặp for duyệt qua các phần tử từ arr[low] đến arr[high - 1].
- Nếu arr[j] nhỏ hơn hoặc bằng pivot, chúng ta tăng i và hoán đổi arr[i] với arr[j]. Điều này đảm bảo rằng tất cả các phần tử nhỏ hơn hoặc bằng pivot được đưa về phía bên trái của mảng con.
- Sau vòng lặp, tất cả các phần tử từ arr[low] đến arr[i] đều nhỏ hơn hoặc bằng pivot.
- Cuối cùng, chúng ta hoán đổi arr[i + 1] với arr[high] (pivot). Điều này đặt pivot vào đúng vị trí của nó (i + 1), với tất cả các phần tử nhỏ hơn hoặc bằng ở bên trái và các phần tử lớn hơn ở bên phải.
- Hàm trả về chỉ số của pivot sau khi nó đã được đặt vào vị trí cuối cùng.
Hàm quickSort(arr, low, high):
- Đây là hàm đệ quy chính.
- Điều kiện dừng là low < high, nghĩa là mảng con vẫn còn ít nhất 2 phần tử. Nếu low >= high, mảng con đã được sắp xếp (có 0 hoặc 1 phần tử).
- Nó gọi partition để phân hoạch mảng con arr[low...high] và nhận về chỉ số pi của pivot.
- Sau đó, nó gọi đệ quy quickSort cho mảng con bên trái pivot (arr[low...pi-1]) và mảng con bên phải pivot (arr[pi+1...high]).

Bài tập này giúp chúng ta làm quen lại với cấu trúc cơ bản của Quick Sort, đặc biệt là vai trò quan trọng của hàm partition.

Bài tập 2: Sắp xếp giảm dần

Quick Sort thường được trình bày với mục tiêu sắp xếp tăng dần. Nhưng nếu chúng ta muốn sắp xếp giảm dần thì sao? Chúng ta chỉ cần thực hiện một thay đổi nhỏ trong logic phân hoạch.

Yêu cầu:

Sửa đổi hàm Quick Sort từ Bài tập 1 để sắp xếp mảng số nguyên theo thứ tự giảm dần. Vẫn sử dụng phần tử cuối cùng làm pivot.

Mã nguồn C++:

#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

// Hàm phân hoạch (Partition) cho sắp xếp giảm dần
int partitionDescending(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // Chọn phần tử cuối làm pivot
    int i = (low - 1);     // Chỉ số của phần tử lớn hơn

    // Duyệt từ phần tử đầu (low) đến gần cuối (high-1)
    for (int j = low; j <= high - 1; j++) {
        // *** Thay đổi ở đây: Kiểm tra nếu phần tử hiện tại lớn hơn HOẶC BẰNG pivot ***
        if (arr[j] >= pivot) {
            i++; // Tăng chỉ số của phần tử lớn hơn
            // Hoán đổi arr[i] và arr[j]
            std::swap(arr[i], arr[j]);
        }
    }
    // Đặt pivot vào đúng vị trí của nó (sau tất cả các phần tử lớn hơn hoặc bằng)
    std::swap(arr[i + 1], arr[high]);
    // Trả về chỉ số của pivot sau khi phân hoạch
    return (i + 1);
}

// Hàm Quick Sort cho sắp xếp giảm dần
void quickSortDescending(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        // Gọi hàm phân hoạch cho sắp xếp giảm dần
        int pi = partitionDescending(arr, low, high);

        // Đệ quy cho mảng con bên trái pivot (chứa các phần tử lớn hơn hoặc bằng)
        quickSortDescending(arr, low, pi - 1);
        // Đệ quy cho mảng con bên phải pivot (chứa các phần tử nhỏ hơn)
        quickSortDescending(arr, pi + 1, high);
    }
}

int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();

    std::cout << "Mang ban dau: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    quickSortDescending(arr, 0, n - 1);

    std::cout << "Mang sau khi sap xep giam dan: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Giải thích mã nguồn:

Sự thay đổi duy nhất và quan trọng nhất nằm trong hàm partitionDescending. Thay vì kiểm tra arr[j] <= pivot để đưa các phần tử nhỏ hơn hoặc bằng về bên trái, chúng ta kiểm tra arr[j] >= pivot. Điều này đảm bảo rằng các phần tử lớn hơn hoặc bằng pivot được đưa về phía bên trái của pivot.

Sau khi phân hoạch, pivot vẫn nằm ở vị trí i + 1, nhưng lúc này, tất cả các phần tử bên trái của nó đều lớn hơn hoặc bằng nó, và tất cả các phần tử bên phải đều nhỏ hơn nó. Khi chúng ta đệ quy trên hai mảng con, chúng ta đang sắp xếp chúng theo cùng logic giảm dần, dẫn đến kết quả cuối cùng là mảng được sắp xếp giảm dần.

Bài tập này minh họa tính lin hoạt của thuật toán Quick Sort – chỉ cần điều chỉnh tiêu chí so sánh trong bước phân hoạch là có thể thay đổi thứ tự sắp xếp.

Bài tập 3: Tìm phần tử lớn thứ k (QuickSelect)

Đây là một ứng dụng cực kỳ hiệu quả của ý tưởng phân hoạch trong Quick Sort, gọi là QuickSelect. Thay vì sắp xếp toàn bộ mảng, chúng ta chỉ cần tìm ra phần tử nằm ở vị trí thứ k nếu mảng được sắp xếp.

Ý tưởng:

QuickSelect sử dụng hàm partition của Quick Sort. Sau khi phân hoạch, pivot nằm ở vị trí pi.

Nếu pi bằng k-1 (vì chỉ số mảng bắt đầu từ 0, phần tử thứ k sẽ có chỉ số k-1), thì pivot chính là phần tử lớn thứ k mà chúng ta cần tìm.
Nếu pi lớn hơn k-1, thì phần tử lớn thứ k phải nằm trong mảng con bên trái của pivot. Chúng ta chỉ cần đệ quy tìm phần tử lớn thứ k trong mảng con bên trái.
Nếu pi nhỏ hơn k-1, thì phần tử lớn thứ k phải nằm trong mảng con bên phải của pivot. Chúng ta cần đệ quy tìm phần tử lớn thứ k trong mảng con bên phải, nhưng lúc này, chúng ta đang tìm phần tử thứ (k - 1 - pi) trong mảng con bên phải (vì pi + 1 phần tử đầu tiên đã bị loại bỏ).

Điểm khác biệt quan trọng so với Quick Sort là QuickSelect chỉ gọi đệ quy trên một nhánh (trái hoặc phải), giúp nó có độ phức tạp trung bình chỉ là O(n), trong khi Quick Sort là O(n log n).

Yêu cầu:

Viết hàm quickSelect nhận vào một mảng số nguyên, chỉ số bắt đầu, chỉ số kết thúc, và số k (phần tử lớn thứ k cần tìm). Hàm trả về giá trị của phần tử đó.

Mã nguồn C++:

#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

// Sử dụng lại hàm partition từ Bài tập 1 (cho sắp xếp tăng dần)
int partition(std::vector<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);
}

// Hàm Quick Select để tìm phần tử lớn thứ k
int quickSelect(std::vector<int>& arr, int low, int high, int k) {
    // Giả sử k hợp lệ (1 <= k <= high - low + 1)
    // Nếu k nằm ngoài phạm vi, xử lý lỗi hoặc trả về giá trị đặc biệt
    if (k > 0 && k <= high - low + 1) {
        // pi là chỉ số của pivot sau khi phân hoạch
        int pi = partition(arr, low, high);

        // Nếu pivot là phần tử lớn thứ k-1 (chỉ số k-1)
        if (pi == k - 1) {
            return arr[pi];
        }

        // Nếu pivot lớn hơn phần tử lớn thứ k-1, tìm ở mảng con bên trái
        if (pi > k - 1) {
            return quickSelect(arr, low, pi - 1, k);
        }

        // Nếu pivot nhỏ hơn phần tử lớn thứ k-1, tìm ở mảng con bên phải
        // Lưu ý: K lúc này cần được điều chỉnh
        // Chúng ta đang tìm phần tử thứ k trong mảng gốc,
        // nhưng trong mảng con bên phải, nó là phần tử thứ (k - số phần tử đã loại bỏ ở bên trái và pivot)
        // Số phần tử đã loại bỏ = pi + 1
        // Số phần tử cần tìm trong mảng con bên phải = k - (pi + 1)
        return quickSelect(arr, pi + 1, high, k - (pi + 1));
    }

    // Trường hợp k không hợp lệ
    return -1; // Hoặc ném exception
}

int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();
    int k = 3; // Tìm phần tử lớn thứ 3

    // Tạo một bản sao để quickSelect không làm thay đổi mảng gốc nếu không muốn
    // (Mặc dù thuật toán partition có thay đổi mảng)
    std::vector<int> arr_copy = arr;

    std::cout << "Mang ban dau: ";
    for (int x : arr_copy) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    int kth_smallest = quickSelect(arr_copy, 0, n - 1, k);

    if (kth_smallest != -1) {
        std::cout << "Phan tu lon thu " << k << " la: " << kth_smallest << std::endl;
        // Để kiểm chứng, bạn có thể sắp xếp mảng gốc và in ra phần tử thứ k-1
        // std::sort(arr.begin(), arr.end());
        // std::cout << "Phan tu lon thu " << k << " (kiem chung): " << arr[k-1] << std::endl;
    } else {
        std::cout << "Gia tri k khong hop le." << std::endl;
    }

    return 0;
}

Giải thích mã nguồn:

Chúng ta tái sử dụng hàm partition từ bài tập 1 (vì chúng ta muốn tìm phần tử lớn thứ k theo thứ tự tăng dần, nên logic phân hoạch theo tăng dần là phù hợp).
Hàm quickSelect(arr, low, high, k):
- Nó kiểm tra tính hợp lệ của k (đảm bảo k nằm trong phạm vi số phần tử của mảng con hiện tại).
- Nó gọi partition để tìm chỉ số pi của pivot.
- Nó so sánh pi với k-1:
  - Nếu pi == k-1, phần tử tại arr[pi] chính là phần tử lớn thứ k.
  - Nếu pi > k-1, phần tử lớn thứ k phải nằm trong mảng con bên trái (arr[low...pi-1]). Chúng ta gọi đệ quy quickSelect trên mảng con này với cùng giá trị k ban đầu.
  - Nếu pi < k-1, phần tử lớn thứ k phải nằm trong mảng con bên phải (arr[pi+1...high]). Đây là điểm mấu chốt. Chúng ta cần tìm phần tử thứ k trong mảng ban đầu, nhưng trong mảng con bên phải, chúng ta đã bỏ qua pi + 1 phần tử (từ low đến pi). Do đó, phần tử thứ k trong mảng gốc trở thành phần tử thứ k - (pi + 1) trong mảng con bên phải. Chúng ta gọi đệ quy quickSelect trên mảng con này với giá trị k mới là k - (pi + 1).
- Nếu k không hợp lệ, hàm trả về -1.

QuickSelect là một ví dụ tuyệt vời cho thấy cách chúng ta có thể điều chỉnh các thuật toán cơ bản để giải quyết các bài toán cụ thể một cách hiệu quả hơn là chỉ áp dụng giải thuật gốc một cách mù quáng.

Vượt Ra Ngoài Bài Tập Cơ Bản

Quick Sort và ý tưởng phân hoạch của nó không chỉ dừng lại ở việc sắp xếp số nguyên. Bạn có thể mở rộng các bài tập này:

Sắp xếp các đối tượng: Áp dụng Quick Sort để sắp xếp một danh sách các đối tượng (ví dụ: sinh viên, sản phẩm) dựa trên một thuộc tính cụ thể (ví dụ: điểm số, giá). Bạn chỉ cần sửa đổi hàm partition để so sánh các thuộc tính của đối tượng thay vì trực tiếp các giá trị.
Chọn pivot ngẫu nhiên: Thay vì luôn chọn phần tử cuối cùng, hãy thử chọn một phần tử ngẫu nhiên làm pivot để cải thiện hiệu suất trung bình và tránh trường hợp xấu nhất khi mảng đã gần được sắp xếp hoặc ngược lại.
Sử dụng các chiến lược chọn pivot khác: Thử nghiệm với "median-of-three" (chọn median của 3 phần tử: đầu, cuối, và giữa) để có pivot tốt hơn.
Quick Sort cho danh sách liên kết: Đây là một bài tập thử thách hơn. Partitioning một danh sách liên kết yêu cầu quản lý con trỏ cẩn thận hơn nhiều so với mảng.
Phân hoạch 3 chiều (3-way partitioning): Đối với các mảng có nhiều phần tử trùng lặp, phân hoạch 3 chiều (chia thành 3 nhóm: nhỏ hơn pivot, bằng pivot, lớn hơn pivot) có thể cải thiện hiệu suất.

Bài tập ví dụ:

Giải đấu cricket

Trong một buổi tập luyện thể thao, FullHouse Dev được huấn luyện viên thách thức với một bài toán thú vị về giải đấu cricket. Với tinh thần thể thao và sự đoàn kết, họ bắt tay vào phân tích và giải quyết vấn đề này.

Bài toán

Trong một giải đấu cricket, \(n\) trận đấu sẽ diễn ra giữa Bob và James. FullHouse Dev được cung cấp hai mảng \(A\) và \(B\), mỗi mảng có \(n\) phần tử. Mảng \(A\) đại diện cho mức năng lượng của Bob, và mảng \(B\) đại diện cho mức năng lượng của James.

Trong trận đấu thứ \(i\), mức năng lượng ở chỉ số \(i\) của cả hai người chơi sẽ được so sánh. Người chiến thắng là người có mức năng lượng cao hơn. Nếu Bob thắng trong trận đấu thứ \(i\), điểm số của anh ấy sẽ được cộng thêm bằng hiệu số năng lượng giữa hai người. Nếu thua, điểm số của Bob không thay đổi.

Bob muốn tối đa hóa điểm số của mình bằng cách thay đổi mức năng lượng, tức là Bob có thể hoán vị mảng của mình. Nhiệm vụ của FullHouse Dev là giúp Bob xác định điểm số tối đa mà anh ấy có thể đạt được.

INPUT FORMAT:

Dòng đầu tiên chứa một số nguyên \(n\) - số lượng trận đấu.
Dòng thứ hai chứa \(n\) số nguyên đại diện cho mức năng lượng của Bob.
Dòng thứ ba chứa \(n\) số nguyên đại diện cho mức năng lượng của James.

OUTPUT FORMAT:

In ra một số nguyên duy nhất biểu thị điểm số tối đa mà Bob có thể đạt được.

Ràng buộc:

\(1 \leq n \leq 10^5\)
\(1 \leq A[i], B[i] \leq 10^9\)

VÍ DỤ

INPUT

5
1 2 3 4 5
1 2 3 4 5

OUTPUT

Giải thích

Bob sẽ hoán vị mảng của mình thành {5, 4, 3, 2, 1}. Vì vậy, ở mức năng lượng đầu tiên và thứ hai, Bob sẽ nhận được điểm số lần lượt là 4 và 2. Ở các mức năng lượng còn lại, Bob sẽ không nhận được điểm số dương. Do đó, tổng điểm tối đa của Bob là 4 + 2 = 6. Tuyệt vời! Đây là hướng dẫn ngắn gọn giúp FullHouse Dev giải quyết bài toán Giải đấu cricket bằng C++:

Hiểu rõ mục tiêu: Bob muốn tối đa hóa tổng điểm của mình. Điểm chỉ được cộng khi Bob thắng (năng lượng của Bob > năng lượng của James) và điểm cộng chính là hiệu số năng lượng. Bob có quyền sắp xếp lại mảng năng lượng của mình (A).
Phân tích cách tính điểm: Điểm được tính là tổng của các hiệu số A'[i] - B[i] cho tất cả các trận đấu i mà A'[i] > B[i], trong đó A' là mảng năng lượng đã được Bob hoán vị.
Chiến lược tối ưu: Để tối đa hóa tổng các hiệu số dương, Bob nên cố gắng sử dụng các mức năng lượng cao của mình để thắng các trận đấu. Đặc biệt, để tạo ra hiệu số lớn nhất có thể (A - B lớn nhất khi A > B), Bob nên dùng năng lượng cao của mình đấu với năng lượng thấp tương ứng của James.
Áp dụng sắp xếp: Bài toán này có thể được giải quyết bằng cách sắp xếp hai mảng.
- Sắp xếp mảng năng lượng của Bob (A) theo thứ tự giảm dần.
- Sắp xếp mảng năng lượng của James (B) theo thứ tự tăng dần.
Ghép cặp và tính điểm: Sau khi sắp xếp, hãy ghép cặp phần tử thứ i của mảng A (đã sắp xếp giảm dần) với phần tử thứ i của mảng B (đã sắp xếp tăng dần).
- Duyệt qua các cặp từ i = 0 đến n-1.
- Tại mỗi cặp (A[i], B[i]), nếu A[i] > B[i], cộng thêm A[i] - B[i] vào tổng điểm của Bob.
Lưu trữ kết quả: Tổng điểm có thể rất lớn, vì vậy hãy sử dụng kiểu dữ liệu số nguyên 64-bit (ví dụ: long long trong C++) để lưu trữ tổng điểm.

Tóm tắt các bước cần thực hiện:

Đọc n.
Đọc mảng A.
Đọc mảng B.
Sắp xếp A giảm dần.
Sắp xếp B tăng dần.
Khởi tạo biến tổng điểm (kiểu long long) bằng 0.
Dùng vòng lặp từ i = 0 đến n-1: Nếu A[i] > B[i], cộng A[i] - B[i] vào tổng điểm.
In ra tổng điểm.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.