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.
Bài viết liên quan
[Case Study] - StatcWeb.Studio dùng nocode để làm tool nocode: 200h - 0 sales - 5 min(s) read - published on January 24, 2021[Case Study] Bán No-code MVP làm trong 100h giá $5000 - 11 min(s) read - published on January 15, 2021Chi tiết mình validate idea với nocode - 3 tuần 60 sales - $567 - 7 min(s) read - published on December 15, 2020Do things that don't scale - Lời khuyên tốt nhất để validate idea làm app - 2 min(s) read - published on November 22, 2020GPT-3 sẽ là phát minh quan trọng kể từ Blockchain - 4 min(s) read - published on September 15, 2020#6 - NoCode MVP - Tổng kết - 5 min(s) read - published on August 22, 2020#5 - NoCode MVP - Buông bỏ để hạnh phúc - 2 min(s) read - published on July 28, 2020#4 - NoCode MVP - Ý tưởng. Một lần chơi lớn - 4 min(s) read - published on July 2, 2020#3 - NoCode MVP - Sức mạnh của Bubble.io - 5 min(s) read - published on June 29, 2020#2 - NoCode MVP - Tại sao là NoCode và tương lai của nó - 7 min(s) read - published on June 28, 2020