# Cấu trúc dữ liệu và giải thuật - Buổi 03

1. **Thuật toán Quick Sort**

- **Định nghĩa:**

- **Thuật toán QuickSort** là một thuật toán **sắp xếp nhanh** (được phát minh bởi Tony Hoare vào năm 1959), được sử dụng rộng rãi trong lĩnh vực khoa học máy tính và toán học.
- **Thuật toán QuickSort** sử dụng phương pháp **chia để trị (divide and conquer)** để sắp xếp các phần tử của một danh sách hoặc mảng.

2. **Đôi nét về tác giả của thuật toán Quick Sort**

- **Sir Charles Antony Richard Hoare** (sinh năm 1934) là một nhà khoa học máy tính người Anh có những đóng góp quan trọng cho ngành khoa học máy tính.
- Trong lĩnh vực thuật toán, Hoare được biết đến với công trình phát minh ra **thuật toán QuickSort** năm 1959, khi ông còn là sinh viên của Đại học Cambridge.
- **Thuật toán QuickSort** đã trở thành một trong những thuật toán sắp xếp phổ biến nhất được sử dụng trong khoa học máy tính và công nghệ thông tin.

3. **Cách thức hoạt động của thuật toán QuickSort**

- **Thuật toán QuickSort** sắp xếp một danh sách hoặc một mảng bằng cách sử dụng phương pháp **chia để trị (divide and conquer)**.

- **Các bước thực hiện của thuật toán QuickSort như sau:**
1. Chọn một **phần tử chốt (pivot)** từ danh sách hoặc mảng ban đầu.
2. Phân chia danh sách thành hai phần, một phần chứa các phần tử **nhỏ hơn phần tử chốt (pivot)** và một phần chứa các phần tử **lớn hơn phần tử chốt (pivot).**
3. Đệ quy áp dụng thuật toán QuickSort trên hai phần vừa được phân chia cho đến khi không còn phần tử nào để phân chia.
4. Kết hợp hai phần đã sắp xếp để tạo thành danh sách hoàn chỉnh.

4. **Giải thuật của thuật toán QuickSort**
- **Phân hoạch theo phương pháp Lomuto:**
- **Giải thuật của thuật toán QuickSort với phân hoạch Lomuto như sau:**
1. Nếu danh sách hoặc mảng chỉ có một phần tử hoặc không có phần tử nào, trả về danh sách ban đầu.
2. Chọn một **phần tử chốt (pivot)** từ danh sách hoặc mảng.
3. Sử dụng biến lưu trữ vị trí của phần tử lớn nhất hiện tại **(biến i)** và sử dụng **biến đếm j** duyệt qua danh sách hoặc mảng từ đầu đến cuối.
4. Nếu phần tử hiện tại nhỏ hơn hoặc bằng phần tử chốt, đổi chỗ phần tử hiện tại với phần tử tại vị trí **i**, sau đó tăng giá trị của biến **i** lên 1.
5. Sau khi duyệt xong danh sách hoặc mảng, **đổi chỗ phần tử chốt với phần tử tại vị trí i** để phân chia danh sách hoặc mảng thành hai phần, một phần chứa các phần tử nhỏ hơn phần tử chốt và một phần chứa các phần tử lớn hơn phần tử chốt.
6. Đệ quy áp dụng thuật toán QuickSort với phân hoạch Lomuto trên hai phần vừa được phân chia cho đến khi không còn phần tử nào để phân chia.
7. Kết hợp hai phần đã sắp xếp để tạo thành danh sách hoàn chỉnh.

- **Mã giả minh hoạ cho phân hoạch Lomuto:**

    function partitionLomuto(arr[], left, right) 
        pivot := arr[right]
        i := left - 1     
        for j := left to (right – 1) do
            if arr[j] <= pivot then
                i = i + 1 
                swap arr[i] with arr[j]
        swap arr[i+1] with arr[right]
        return i+1

    function quickSortLomuto(arr[], left, right)
        if left < right then
            pivotIndex := partitionLomuto(arr, left, right)
            quickSortLomuto(arr, left, pivotIndex - 1)
            quickSortLomuto(arr, pivotIndex + 1, right)

- **Phân hoạch theo phương pháp Hoare:**
- **Giải thuật của thuật toán QuickSort với phân hoạch Hoare như sau:**
1. Nếu danh sách hoặc mảng chỉ có một phần tử hoặc không có phần tử nào, trả về danh sách ban đầu.
2. Chọn một **phần tử chốt (pivot)** từ danh sách hoặc mảng.
3. Sử dụng hai biến lưu trữ vị trí, một biến **i** bắt đầu từ vị trí đầu tiên và một biến **j** bắt đầu từ vị trí cuối cùng của danh sách hoặc mảng.
4. Duyệt qua danh sách hoặc mảng từ đầu đến cuối với biến **i** và từ cuối đến đầu với biến **j**.
5. Nếu phần tử tại vị trí **i** lớn hơn phần tử chốt và phần tử tại vị trí **j** nhỏ hơn **phần tử chốt**, đổi chỗ hai phần tử đó.
6. Lặp lại bước 4 và 5 cho đến khi **i > j** để hân chia danh sách hoặc mảng thành hai phần, một phần chứa các phần tử nhỏ hơn phần tử chốt và một phần chứa các phần tử lớn hơn phần tử chốt.
7. Đệ quy áp dụng thuật toán QuickSort với phân hoạch Hoare trên hai phần vừa được phân chia cho đến khi không còn phần tử nào để phân chia.
8. Kết hợp hai phần đã sắp xếp để tạo thành danh sách hoàn chỉnh.

- **Mã giả minh hoạ phân hoạch Hoare:**

    function partitionHoare(arr[], left, right)
        pivot := arr[left]
        i := left - 1
        j := right + 1
        while true do
            repeat i := i + 1 until arr[i] >= pivot
            repeat j := j - 1 until arr[j] <= pivot
            if i < j then
               swap(arr[i], arr[j])
            else return j

    function quickSortHoare(arr[], left, right)
        if left < right then
            pivotIndex := partitionHoare(arr, left, right)
            quickSortHoare(arr, left, pivotIndex)
            quickSortHoare(arr, pivotIndex + 1, right)

5. Độ phức tạp

- Độ phức tạp trung bình của thuật toán QuickSort là **O(n log n).**
- Trong trường hợp xấu nhất, khi danh sách hoặc mảng đã được sắp xếp và phần tử chốt được chọn là phần tử đầu tiên hoặc cuối cùng của danh sách hoặc mảng, độ phức tạp sẽ là **O(n^2).**

6. **Code mẫu**

- **Code minh hoạ cho phương pháp phân hoạch Lomuto:**

int partitionLomuto(int arr[], int left, int right){
    int pivot = arr[right];
    int i = left - 1;
    for(int j=left; j<right; j++){
        if(arr[j] <= pivot){
            ++i;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[right]);
    return i+1;
}

void quickSortLomuto(int arr[], int left, int right){
    if(left < right){
        int pivot = partitionLomuto(arr, left, right);
        quickSortLomuto(arr, left, pivot-1);
        quickSortLomuto(arr, pivot+1, right);
    }
}

- **Code minh hoạ cho phương pháp phân hoạch Hoare:**

int partitionHoare(int arr[], int left, int right)
{
    int pivot = arr[left];
    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)
            swap(arr[i], arr[j]);
        else
            return j;
    }
}

void quicksortHoare(int arr[], int left, int right)
{
    if (left < right)
    {
        int pivot = partitionHoare(arr, left, right);
        quicksortHoare(arr, left, pivot);
        quicksortHoare(arr, pivot + 1, right);
    }
}

7. **Ưu điểm và nhược điểm của QuickSort**

- **Ưu điểm:**

- **Tốc độ sắp xếp nhanh:** QuickSort là một trong những thuật toán sắp xếp nhanh nhất.
- **Xử lý được các bộ dữ liệu lớn:** QuickSort có thể sắp xếp các bộ dữ liệu lớn hơn so với các thuật toán khác.
- **Dễ dàng tối ưu hóa:** QuickSort có thể được tối ưu hóa để tăng tốc độ sắp xếp và giảm độ phức tạp.
- **Không sử dụng thêm bộ nhớ bổ sung.**

- **Nhược điểm:**

- **Sử dụng đệ quy:** QuickSort sử dụng đệ quy để phân hoạch danh sách hoặc mảng, có thể gây ra lỗi tràn bộ nhớ hoặc thực thi chậm nếu danh sách hoặc mảng quá lớn.
- **Không ổn định:** QuickSort không ổn định, nghĩa là các phần tử có cùng giá trị có thể được sắp xếp không đúng thứ tự trong danh sách hoặc mảng kết quả.
- **Tùy thuộc vào lựa chọn phần tử chốt:** Hiệu suất của QuickSort phụ thuộc vào cách lựa chọn phần tử chốt. Nếu phần tử chốt được chọn không tốt, nó có thể làm giảm hiệu suất của thuật toán.

8. **Tài liệu, video tham khảo**

- [28tech - Thuật Toán Sắp Xếp Nhanh QuickSort](https://youtu.be/eT9Epyf0XLM)
- [Paper của tác giả thuật toán QuickSort - Tony Hoare](https://dl.acm.org/doi/pdf/10.1145/366622.366644)