[Học lại] Bài 4 - Merge Sort

Ý tưởng cơ bản của Merge sort (sắp xếp trộn) như sau:

Chúng ta có 2 danh sách đã được sắp xếp, trộn hai danh sách đó lại sẽ được danh sách dài hơn cũng được sắp xếp.
Việc trộn sẽ thực hiện bằng cách so sánh từng phần tử ở 2 danh sách con ban đầu, bên nào nhỏ hơn sẽ được đưa vào danh sách kết quả, thực hiện đến khi một danh sách hết phần tử và sẽ đưa toàn bộ phần tử còn lại của danh sách dài hơn vào kết quả.

Ví dụ: ta có 2 danh sách sau: [1, 2, 6], [3, 4]
Bước 1: so sánh 1 vs 3, đưa 1 vào ds kết quả, [1]
Bước 2: so sánh 2 vs 3, đưa 2 vào ds kết quả, [1, 2]
Bước 3: so sánh 6 vs 3, đưa 3 vào ds kết quả, [1, 2, 3]
Bước 4: so sánh 6 vs 4, đưa 4 vào ds kết quả, [1, 2, 3, 4]
Bước 5: đưa 6 vào ds kết quả vì ds thứ 2 đã duyệt hết, [1, 2, 3, 4, 6]

Việc trộn được thực hiện ở 2 nửa của một danh sách chưa được sắp xếp, chia về các danh sách nhỏ hơn (chỉ gồm 1 phần tử) rồi trộn lại.

Cách thực hiện trên có thể gọi là chia để trị, xem thêm ở đây:

https://www.geeksforgeeks.org/divide-and-conquer-introduction/

Tiếp theo chúng ta sẽ thử cài đặt hàm trộn trước:

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    
    var result: [Int] = []

    var leftIndex = 0
    var rightIndex = 0
    
    while (true) {
        
        //we will break if left or right is already iterated all values
        if (leftIndex == left.count) && (rightIndex == right.count) {
            break
        }
        
        //when left is done, just focus on right
        if (leftIndex == left.count) {
            result.append(right[rightIndex])
            rightIndex += 1
            continue
        }
        
        //when right is done, just focus on left
        if (rightIndex == right.count) {
            result.append(left[leftIndex])
            leftIndex += 1
            continue
        }
        
        //normal case
        if left[leftIndex] < right[rightIndex] {
            result.append(left[leftIndex])
            leftIndex += 1
        }else{
            result.append(right[rightIndex])
            rightIndex += 1
        }
    }
    
    return result
}

Okay, việc merge đã xong, bây giờ cài đặt merge sort nhé

func mergeSort(_ input: [Int]) -> [Int] {
    if input.count == 1 {
        return input
    }
    
    let middle = input.count / 2
    let leftArray = mergeSort(Array(input[0..<middle]))
    let rightArray = mergeSort(Array(input[middle..<input.count]))
    
    return merge(leftArray, rightArray)
}

Xét về time complexity, chúng ta có số bước chia nhỏ là logn, việc merge tốn n bước. Như vậy O(nlogn) là tổng thời gian để thực hiện.

Việc cài đặt như trên có một vấn đề là rất nhiều mảng con được sinh ra nên rất tốn bộ nhớ. Có thể giải quyết bằng thực hiện việc chia nhỏ và trộn trên bản thân array đó luôn, thông qua inout parameter.

https://docs.swift.org/swift-book/ReferenceManual/Declarations.html#ID545

Bài sau mình sẽ đi chi tiết hơn về cách làm này.

Thân.