Thuật toán với Swift Insertion Sort
Bài viết giải thích thuật toán sắp xếp Insertion Sort được triển khai bằng ngôn ngữ Swift theo cách dễ hiểu, dễ nhớ, không giống như trong sách giáo khoa.

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:
-
Cho một mảng số chưa sắp xếp
-
Chọn một số từ mảng đó, cho dễ thì chọn từ đầu mảng
-
Chèn số đó vào một mảng mới
-
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
-
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.
Related Posts
Discover more content you might enjoy

Vibe Coding - Code lại blog từ đầu và rebrand thành khoa.blog
Chia sẻ chi tiết quá trình build lại blog từ đầu với vibe coding, từ việc chuyển đổi dữ liệu đến việc triển khai các tính năng mới, giúp người đọc hiểu rõ hơn về quá trình phát triển blog cá nhân.

Dự đoán về Vibe Coding: Cách AI sẽ biến đổi việc tạo ra phần mềm
Phân tích chi tiết cách 'vibe coding' - phương pháp lập trình dựa trên mô tả ý định thay vì viết code trực tiếp - sẽ dân chủ hóa việc phát triển phần mềm, giúp người đọc hiểu rõ hơn về xu hướng công nghệ và tác động của nó đến ngành công nghệ thông tin.

The MVP #1: Làm một trang dạy học trực tuyến cần gì?
Bài viết phân tích những nhược điểm của Udemy và các yêu cầu cần thiết để xây dựng một nền tảng học trực tuyến độc lập.

English Course Challenge in 2 weeks - Day 12: Kinh nghiệm quay khoá học
Bài viết chia sẻ kinh nghiệm quay khóa học tiếng Anh về Bubble.io, bao gồm việc lựa chọn phần mềm Screen.Studio để quay màn hình và tự động tạo phụ đề, những bài học từ việc đặt mục tiêu và xác định đối tượng học viên trước khi chọn nội dung, cũng như lợi ích của việc thử thách bản thân để vượt qua nỗi sợ và hoàn thành dự định. Tác giả cũng giới thiệu khóa học 'Build your first web app in Bubble for beginners' dành cho người mới bắt đầu.

Vấn đề là không có vấn đề
Bài viết chia sẻ quan điểm về cách tiếp cận vấn đề trong cuộc sống, nhấn mạnh tầm quan trọng của tư duy tích cực và cách giải quyết vấn đề hiệu quả.

Day 11 - Profitable MVP in 30 Days - Bế tắc với những ý tưởng mới
Bài viết ngày 11 của thử thách xây dựng MVP có lợi nhuận, tác giả chia sẻ về việc tìm kiếm ý tưởng mới sau khi gặp khó khăn với sản phẩm đầu tiên. Bài viết giới thiệu ý tưởng Reading Tracker - công cụ giúp người dùng tạo, quản lý và chia sẻ danh sách sách đã đọc, với các tính năng như đồng bộ từ Goodreads, tự động hoàn thành khi nhập và tích hợp liên kết tiếp thị liên kết Amazon.