Sắp xếp chèn (insertion sort) trong Python
Bài 16/20 · Chương 23
Cấu trúc dữ liệu và giải thuật
- 9 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 12
Sắp xếp chèn (insertion sort) là thuật toán sắp xếp lấy lần lượt từng phần tử và chèn nó vào đúng chỗ trong phần đầu list đã xếp. Nó giống như cầm bài trên tay và cài từng lá mới vào giữa các lá đã xếp. Thuật toán hợp với dãy gần đúng thứ tự, như danh bạ đã xếp theo tên vừa thêm vài liên hệ ở cuối.
Cần biết trước: sắp xếp chọn và vòng lặp while.
Chèn một phần tử vào phần đã xếp
Danh bạ có bốn tên đã xếp, "Minh" vừa được thêm vào cuối. Để chèn "Minh", bạn cầm nó ra (biến x), rồi đi ngược từ phần tử đứng ngay trước nó: mỗi tên lớn hơn "Minh" được dịch sang phải một ô. Gặp tên không lớn hơn thì dừng, và chỗ trống ngay sau tên đó là chỗ của "Minh":
danh_ba = ["Hà", "Lan", "Ngọc", "Quân", "Minh"]
x = danh_ba[4]
j = 3
while j >= 0 and danh_ba[j] > x:
danh_ba[j + 1] = danh_ba[j]
j -= 1
print(danh_ba)
danh_ba[j + 1] = x
print(danh_ba)KẾT QUẢ
['Hà', 'Lan', 'Ngọc', 'Quân', 'Quân']
['Hà', 'Lan', 'Ngọc', 'Ngọc', 'Quân']
['Hà', 'Lan', 'Minh', 'Ngọc', 'Quân']Khi dịch, tên cũ còn nằm ở ô bên trái nên list tạm có hai "Quân", rồi hai "Ngọc". Không mất gì, vì "Minh" đang nằm an toàn trong x. Vòng while cần cả hai điều kiện: j >= 0 để không đi quá đầu list, danh_ba[j] > x để dừng khi đã tới chỗ. Dừng ở j = 1 (tên "Lan"), nên "Minh" vào ô j + 1 = 2.
Viết insertion sort
Thuật toán lặp lại bước chèn cho từng chỉ số i từ 1 tới cuối. Phần tử ở chỉ số 0 đứng một mình nên coi như đã xếp. Mỗi lần chèn, phần đầu đã xếp dài thêm một phần tử:
def insertion_sort(ds):
ds = ds.copy()
for i in range(1, len(ds)):
x = ds[i]
j = i - 1
while j >= 0 and ds[j] > x:
ds[j + 1] = ds[j]
j -= 1
ds[j + 1] = x
print("Sau khi chèn", x, ds)
return ds
print(insertion_sort(["Ngọc", "Hà", "Quân", "Lan"]))KẾT QUẢ
Sau khi chèn Hà ['Hà', 'Ngọc', 'Quân', 'Lan']
Sau khi chèn Quân ['Hà', 'Ngọc', 'Quân', 'Lan']
Sau khi chèn Lan ['Hà', 'Lan', 'Ngọc', 'Quân']
['Hà', 'Lan', 'Ngọc', 'Quân']"Quân" lớn hơn "Ngọc" đứng ngay trước nó, nên vòng while không chạy lượt nào và "Quân" ở yên chỗ cũ. Khác sắp xếp chọn, phần đầu ở đây chưa chắc chứa các phần tử nhỏ nhất của cả list: "Lan" tới lần cuối mới chen vào giữa. Phần đầu chỉ được bảo đảm là đã đúng thứ tự với nhau.
Nhanh với dãy gần đúng thứ tự
Mỗi lần chèn chỉ dịch những phần tử lớn hơn phần tử đang chèn. Nếu list gần như đã xếp, hầu hết các lần chèn dừng ngay ở phép so đầu tiên. Hàm dưới đây đếm số lần dịch trên hai list 1000 số: một list đã xếp chỉ đảo một cặp kề nhau, một list xếp ngược:
def dem_dich(ds):
ds = ds.copy()
dem = 0
for i in range(1, len(ds)):
x = ds[i]
j = i - 1
while j >= 0 and ds[j] > x:
ds[j + 1] = ds[j]
j -= 1
dem += 1
ds[j + 1] = x
return dem
gan_dung = list(range(1000))
gan_dung[500], gan_dung[501] = gan_dung[501], gan_dung[500]
print(dem_dich(gan_dung), dem_dich(list(range(1000, 0, -1))))KẾT QUẢ
1 499500Mỗi chỉ số i tốn số phép so bằng số lần dịch cộng nhiều nhất một phép so làm vòng while dừng. List gần đúng chỉ cần một lần dịch và khoảng 1000 phép so, tức O(n). List xếp ngược thì mỗi phần tử mới phải đi về tận đầu: 499500 lần dịch, O(n²) như hai thuật toán trước. Vì thế sort() của Python dùng sắp xếp chèn cho các đoạn ngắn bên trong Timsort, chuyện bài thuật toán sắp xếp kể kỹ hơn.
Chèn theo tên và giữ thứ tự cũ
Danh bạ thật lưu nhiều trường, ví dụ tuple (ten, ma) gồm tên và mã liên hệ. Để xếp theo tên, bạn so ds[j][0] với x[0]. Phép so hẳn > dừng ngay khi gặp một tên bằng tên đang chèn, nên hai người cùng tên giữ thứ tự cũ, tức sắp xếp chèn ổn định:
def xep_theo_ten(danh_ba):
ds = danh_ba.copy()
for i in range(1, len(ds)):
x = ds[i]
j = i - 1
while j >= 0 and ds[j][0] > x[0]:
ds[j + 1] = ds[j]
j -= 1
ds[j + 1] = x
return ds
danh_ba = [("Tâm", 106), ("Lan", 104), ("Tâm", 102), ("Hà", 101)]
print(xep_theo_ten(danh_ba))KẾT QUẢ
[('Hà', 101), ('Lan', 104), ('Tâm', 106), ('Tâm', 102)]Liên hệ 106 đứng trước liên hệ 102 trong danh bạ gốc và vẫn đứng trước sau khi xếp. Đổi ds[j][0] > x[0] thành ds[j][0] >= x[0] rồi chạy lại: kết quả in ('Tâm', 102), ('Tâm', 106), hai người cùng tên đã đổi chỗ. Tìm chỗ chèn còn nhanh hơn được bằng bisect của bài tìm kiếm nhị phân, nhưng số lần dịch vẫn giữ nguyên.
Kiểm tra nhanh
Hàm
insertion_sortcủa bài chạy trên[6, 2, 9, 4]. Ngay trước lần chèn số4, list là gì?[2, 6, 9, 4][2, 4, 6, 9][6, 2, 9, 4][2, 6, 4, 9]
Những điều nào đúng với sắp xếp chèn viết như bài?
- List đã xếp sẵn không phải dịch phần tử nào
- List xếp ngược 1000 số cũng chỉ cần khoảng 1000 lần dịch
- So tên bằng
>giữ thứ tự cũ của hai người cùng tên - Sau lần chèn thứ hai, ba phần tử đầu là ba số nhỏ nhất của cả list
Viết nhầm
while j > 0 and ds[j] > x:. Hàm khi đó xếp[5, 3]thành gì?[3, 5]- Báo lỗi IndexError
[5, 3], không đổi gì
Sau vòng
while, viết nhầmds[j] = x. Khixnhỏ hơn mọi phần tử đứng trước,xđược ghi vào đâu?- Ô đầu list, đúng chỗ của nó
- Ô cuối list, vì
jbằng-1 - Không ghi đâu cả, vì Python báo lỗi IndexError
Bài tập
Ghi lại từng lần chèn vào danh bạ
Danh bạ là list các tuple (ten, ma). Viết thân hàm cac_buoc_chen(danh_ba) xếp theo ten tăng dần bằng insertion sort. Với từng chỉ số i từ 1, lấy phần tử đó ra, dịch bằng vòng while các phần tử đứng trước có tên lớn hơn hẳn sang phải một ô, rồi đặt nó vào chỗ trống. Sau mỗi lần chèn, kể cả khi không phải dịch, ghi một tuple gồm bản sao của list và số ô vừa dịch. Hai người cùng tên giữ thứ tự ban đầu. Không dùng sorted(), sort(), min(), tham số key hay module bisect, và không sửa danh_ba.
Ví dụ: cac_buoc_chen([("Ngọc", 101), ("Hà", 102), ("Ngọc", 103)]) trả về [([("Hà", 102), ("Ngọc", 101), ("Ngọc", 103)], 1), ([("Hà", 102), ("Ngọc", 101), ("Ngọc", 103)], 0)].
Trả về: trạng thái của list và số ô đã dịch sau từng lần chèn, một list gồm các tuple.
def cac_buoc_chen(danh_ba):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
Sắp xếp chèn lấy từng phần tử từ chỉ số
1, dịch các phần tử lớn hơn sang phải rồi đặt nó vào chỗ trống.Vòng
whilecầnj >= 0để đi tới tận ô đầu, và chỗ trống là ôj + 1.Dãy gần đúng thứ tự chỉ cần vài lần dịch: O(n). Dãy xếp ngược cần
n * (n - 1) // 2lần dịch: O(n²).So hẳn
>giữ thứ tự cũ của phần tử bằng nhau, nên sắp xếp chèn ổn định.j = -1mà ghids[j]thì Python ghi đè phần tử cuối list, không báo lỗi.
Câu hỏi thường gặp
Thuật toán sắp xếp chèn có độ phức tạp bao nhiêu?
Trường hợp tốt, list đã xếp, mỗi lần chèn chỉ một phép so nên là O(n). Trường hợp xấu, list xếp ngược, là O(n²) phép so và lần dịch. Bộ nhớ thêm là O(1) vì thuật toán xếp tại chỗ. Ý nghĩa của O(n) và O(n²) được giải thích ở bài Big O.
Tự viết insertion sort trong Python có nhanh hơn sort() không?
Không. sort() được viết bằng C, và với đoạn ngắn nó cũng chèn, nhưng tìm chỗ bằng tìm kiếm nhị phân, và chạy nhanh hơn nhiều lần. Bạn tự viết sắp xếp chèn để hiểu thuật toán, còn trong chương trình thật thì dùng sort() hay sorted() của bài sắp xếp list.
Sắp xếp chèn khác sắp xếp chọn ở đâu?
Sắp xếp chọn đi hết phần chưa xếp để tìm số nhỏ nhất, nên luôn tốn O(n²) phép so. Sắp xếp chèn chỉ so phần đã xếp cho tới khi gặp chỗ, nên rất nhanh với dãy gần đúng thứ tự, và nó ổn định còn sắp xếp chọn thì không.
Sắp xếp chèn có hợp khi dữ liệu đến dần từng phần tử không?
Có, đó là chỗ nó mạnh: phần đã xếp luôn đúng thứ tự, nên mỗi liên hệ mới chỉ cần thêm vào cuối rồi chèn vào phần đã xếp, không phải xếp lại từ đầu. Với danh bạ lớn, bài tìm kiếm nhị phân chỉ cách tìm chỗ chèn nhanh hơn bằng bisect.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.