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
Ví dụ đang sắp xếp mảng số nha. Ý tưởng của Insertion Sort như sau:
Đó là lý do gọi thuật toán này là Insertion Sort
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]
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 |]
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 đó.
func insertionSort(_ array: [Int]) -> [Int] {
var a = array
for x in 1..<a.count {
var y = x // lưu vị trí cái thanh |
let temp = a[y] // lưu giá trị hiện tại
while y > 0 && temp < a[y - 1] { // Đang check ngược lại phần mảng đã sắp xếp, hiện tại bé hơn trước ->
// -> đẩ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
}
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.
NIVIKI.COM | Telegram | Twitter
Thất nghiệp. Đang rủ rê nhiều người thất nghiệp. Hy vọng với NIVIKI.COM có thể lan toả tinh thần thất nghiệp đến với nhiều người hơn nữa
Join Discord Channel để giao lưu với mình