HàPhan 河

[Học lại] Bài 5 - Quick Sort

À ừm, QuickSort dịch sát nghĩa xoạc nhanh =))

Ý tưởng của Quick Sort:

Lấy một phần tử bất kỳ (pivot) của danh sách, 
Làm như thế nào đó (partition) để biến danh sách thành 3 phần: 
 trái <= pivot <= phải
làm tương tự cho 2 danh sách con trái và phải.

Partition được thực hiện Linear time O(n)

Cách cài đặt partion là quan trọng nhất nên thôi nhảy vào luôn khỏi dạo đầu tốn thời gian =))

func partion(_ arr: inout [Int], left: Int, right: Int) -> Int {
    let pivot = arr[right] //lấy pivot cuối danh sách
    
    let i = left - 1
    for j in left..<right-1 {
        if arr[j] <= pivot {
            i += 1
            swap(&arr[i], &arr[j])
        }
    }
    
    swap(&arr[i + 1], &arr[right])
    return i + 1
}

việc partition có thể áp dụng tương tự để giải bài toán tìm số nhỏ thứ n trong danh sách

Quick Sort chỉ cần gọi đệ quy cho trái phải là giải quyết được vấn đề

func quickSort(_ arr: inout [Int], left: Int, right: Int) {
    if (left < right)  
    {  
        let pi = partition(&arr, left, right);  
        quickSort(&arr, low, pi - 1);  
        quickSort(&arr, pi + 1, high);  
    }  
}

Có rất nhiều cách để chọn pivot:

  • luôn luôn chọn phần tử đầu tiên của danh sách
  • luôn luôn chọn phần tử cuối của danh sách
  • chọn phần tử ngẫu nhiên
  • chọn phần tử giữa mảng

Độ phức tạp thuật toán của cái xoạc nhanh này không ổn định, tức là có lúc 3s có lúc 5 phút có lúc cả buổi sáng, phụ thuộc vào chọn tư thế (pivot) =))

T(n) = T(k) + T(n-k-1) + \theta(n)

Hai cái time đầu là thời gian trái phải lúc gọi đệ quy, cái cuối là thời gian partion một lần.

Worst Case: này là phê lâu nhất nè, bữa bị chị Google hỏi cái này mà không làm được chị thoả mãn =)) )
Xảy ra khi chọn pivot luôn luôn là số nhỏ nhất hoặc lớn nhất (số nhọ), trái hoặc phải qua mỗi lần chỉ giảm đi một phần tử.

T(n) = T(0) + T(n-1) + \theta(n) = T(n-1) + \theta(n) = \theta(n^2)

Best Case:
Pivot được chọn luôn nằm giữa mảng. Ừ ở giữa lúc nào chả sướng =))

T(n) = 2T(n/2) + \theta(n) = \theta(nLogn)

Average Case

T(n) = T(n/9) + T(9n/10) + \theta(n) = O(nLogn)

Cái này nó hơi cao siêu quá nên phải xem thêm mới hiểu rõ được.
https://www.geeksforgeeks.org/analysis-of-algorithms-set-2-asymptotic-analysis/

Một số thông tin liên quan cần lưu ý với giải thuật này, xoạc nhanh lúc nào cũng thú vị nên có nhiều hậu quả =))

  • Mặc xét về độ ổn định thì không bằng Merge Sort hay Heap Sort, xấu nhất O(n^2), nhưng Quick Sort rất dễ cài đặt ở hầu hết các kiến trúc và dữ liệu thực tế.
  • Hàm chọn pivot có thể cài đặt tự do nên trường hợp xấu nhất rất khó có thể xảy ra với những bộ dữ liệu cụ thể.

Đang nâng bi gặp cái này tụt mút nhỉ =))

However, merge sort is generally considered better when data is huge and stored in external storage.

Thôi xoạc lần này cũng đã mệt nghỉ bữa sau qua thử cái Heap chắc có vẻ vui hơn.
Happy Coding!

Comments