[Học lại] Bài 3 - Insertion Sort

https://www.geeksforgeeks.org/insertion-sort/

Ý tưởng của insertion sort cũng gần giống bubble sort (?), mình sẽ đưa phần tử nhỏ hơn về trước bằng cách tìm vị trí chính xác rồi chèn vào.
ví dụ: [1 2 4 3], [1 2 4] đã được sắp xếp, chúng ta cần chèn 3 vào giữa 2 và 4
để thành [1 2 3 4].

Cứ qua mỗi lần duyệt thì danh sách bên trái luôn luôn được sắp xếp.

Để việc chèn được hiệu quả thì khi duyệt về bên trái để tìm vì trí chèn thì đồng thời thực hiện việc dời từng vị trí về bên phải, tạo chỗ trống cho việc chèn.

Ví dụ: [1, 2, 4, 3] dịch 4 về bên phải [1, 2, 4, 4] và giữ giá trị 3 để chèn, thấy vị trí cần chèn (3 > 2), thay 3 vào -> [1, 2, 3, 4]

Okay, phân tích đã xong thử cài đặt nè.

1. Duyệt

func insertionSort(_ input: [Int]) -> [Int] {
    var tempArray = input
    for i in 1..<input.count {
        let willMove = tempArray[i]
        for j in stride(from: i - 1, through: 0, by: -1) {
            
            if tempArray[j] > willMove{
                tempArray[j+1] = tempArray[j]
            }else if tempArray[j] <= willMove {
                tempArray[j+1] = willMove
                //vì bên trái đã được sắp xếp nên break tại đây
                break
            }
            
            //chặn dưới nếu về đến 0 mà vẫn là nhỏ nhất
            if j == 0 {
                tempArray[j] = willMove
            }
        }
    }
    return tempArray
}

Time complexity: O(n^2),
Chúng ta có thể đổi input array thành inout để khỏi tạo thêm mảng temp -> tiết kiệm bộ nhớ (space complexity).
2. Đệ quy
Ý tưởng:
Sẽ trả về bản thân mảng nếu độ dài là 1,
Sắp xếp các phần tử bên trái
Chèn phần tử bên phải cùng vào đúng vị trí vào mảng đã được sắp xếp ở bên trái.

func insertionSortRecursive(_ input: inout [Int], _ index: Int) {
    if index <= 1 {
        return
    }
    
    insertionSortRecursive(&input, index - 1)
    moveIndexToRight(&input, index - 1)
}
func moveIndexToRight(_ input: inout [Int], _ index: Int){
    let rightElement = input[index]
    var toInsertIndex = index - 1
    
    for i in stride(from: index - 1, through: -1, by: -1) {
        
        //Find index
        toInsertIndex = i
        
        if i != -1 {
            
            //Shift to right
            input[i+1] = input[i]
            
            if input[i] <= rightElement {
                break
            }
        }
        
    }
    
    input[toInsertIndex + 1] = rightElement
}

Hãy làm thử một số Quiz nhé
https://www.geeksforgeeks.org/quiz-insertionsort-gq/

Insertion sort sẽ là nhanh nhất O(n) time-complexity khi mảng đã được sort hoặc gần như sort hoặc các phần tử đều giống nhau bởi vì lúc này khi chèn một phần tử vào mảng đã sắp xếp ở trước chỉ tốn O(1).