Thuật toán với Swift Insertion Sort

Giới thiệu

Nói thiệt chứ không biết mấy bạn sao, chứ mấy cái thuật toán mà không xài là vài bữa mình quên hết. Dù đã học qua thuật toán này 3,4 lần cũng hem nhớ gì hết. Ahuhu, hay trí nhớ mình kém :'(

Giờ ghét quá, nên mình quyết định viết hết seri về thuật toán luôn cho nhớ. Mục tiêu là viết theo kiểu dễ nhớ, dễ hiểu không như trong sách giáo khoa. Cài đặt thì mình xài Swift luôn, chứ mấy ngôn ngữ khác có nhớ gì đâu.

Nguồn bài viết thì mình lấy ở swift-algorithm-club

Mấy bạn không biết Swift cũng đọc được vì Swift nó dễ nhìn lắm :))

Thôi hôm nay bắt đầu từ bài dễ nhất trước nhé đó là thuật toán sắp xếp Insertion Sort

Ý tưởng

Ví dụ đang sắp xếp mảng số nha. Ý tưởng của Insertion Sort như sau:

1. Cho một mảng số chưa sắp xếp

2. Chọn một số từ mảng đó, cho dễ thì chọn từ đầu mảng

3. Chèn số đó vào một mảng mới

4. Chọn tiếp một số từ mảng chưa sắp xếp vào mảng mới. So sánh với số ở mảng mới để sắp xếp vị trí cho chúng. Như vậy bạn được mảng mới với 2 phần tử đã sắp xếp

5. Tiếp tục lấy số từ mảng chưa sắp xếp -> so sánh với các số đã sắp xếp ở mảng mới -> đến khi mảng chưa sắp xếp rỗng -> nghỉ

Đó là lý do gọi thuật toán này là Insertion Sort

Ví dụ

Có mảng [ 7, 2, 0, 4 ] cần sắp xếp tăng dần, cứ bốc ra tửng phần tử rồi insert vào mảng mới

Lần 1: Bóc 7 được [7]

Lần 2: Bóc 2 được [2,7]

Lần 3: Bóc 0 được [0,2,7]

Lần 4: Bóc 4 được [0,2,4,7]

In-place sorting

Nếu xài 2 mảng thì nhìn gà lắm, nên người ta mới có thuật ngữ là In-place sort

an in-place algorithm is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space.

Tức là không dung thêm tài nguyên nào cả. Lấy một mảng mần luôn.

Chúng ta sẽ dùng một thanh | để chặn 2 phần của một mảng là phần chưa và phần đã sắp xếp

[ | 7, 2, 0, 4 ]

[7 | , 2, 0, 4 ]

[2 , 7 | , 0, 4 ]

[0, 2 , 7 | , 4 ]

[0, 2 , 4 , 7 | ]

Chèn như thế nào?

Ví dụ đang ở bước này, cần đưa 0 về đầu mảng đã sắp xếp:

[2 , 7 , 0 | , 4 ] lưu 0

[2 , 7, 7 | , 4 ] đẩy 7 qua bên phải

[ 2 , 2 , 7 | , 4 ] đây 2 qua bên phải

[ 0 , 2 , 7 | , 4 ] giờ không có số nào bé hơn 0 nữa nên thay 2 bằng 0

Bạn nhớ là do từng bước thì phần mảng đầu luôn luôn là đã sắp xếp rồi. Tưởng tượng một thanh | trong mảng, đi tới đâu thì phần nó đi qua đã được sắp xếp.

Khi bóc một số từ phần mảng chưa sắp xếp ra, rồi chạy ngược lại để check với phần mảng đã sắp xếp đó.

Code

func insertionSort(_ array: [Int]) -> [Int] {
    var a = array
    for x in 1..<a.count {
        var y = x
        let temp = a[y]
        while y > 0 && temp < a[y - 1] {
            // -> đẩy cái bé về trước, lớn về sau -> sắp xếp tăng dần.
            a[y] = a[y - 1] // Bước dịch sang phải nè
            y -= 1
        }
        a[y] = temp // Không còn số nào bé hơn số đã lưu
    }
    return a
}

Độ phức tạp

Có 2 vòng lặp nên nếu khả năng xất nhất thì sẽ là O(n^2). Nghe giang hồ đồn Insertion Sort chỉ nhanh khi mảng có ít phần tử thôi.