Cùng một bài, đọc bằng chữ. Nhanh hơn và tìm lại được bằng Ctrl+F.
Xếp bài trên tay
- Trên tay3 7 — hai lá đã đúng thứ tự
- Rút lá 5So từ phải sang: 7 lớn hơn 5, dịch 7 sang phải
- Dừng ở 33 nhỏ hơn 5, đặt 5 vào ngay sau 3
- Kết quả3 5 7. Lặp lại đúng vậy với lá tiếp theo
Số thật trong thư viện chuẩn
JDK 8 chuyển sang insertion sort khi đoạn còn dưới 47 phần tử, JDK 17 dưới 44. Go đặt ngưỡng 12. Python trộn từng đoạn 32 đến 64 phần tử. Ở cỡ đó nó thắng cả quick sort.
Vì sao nó thắng ở mảng nhỏ
Big-O nói về xu hướng khi n lớn, không nói về mảng 20 phần tử. Ở cỡ đó, chi phí chia mảng và gọi đệ quy của quick sort còn đắt hơn việc dịch vài phần tử.
Mảng gần đúng thì gần như O(n)
Mỗi phần tử chỉ dịch vài bước nên tổng công việc gần tuyến tính. Đây là nhanh thật, không phải nhanh trên lý thuyết, và là lý do Timsort đi tìm sẵn các đoạn đã đúng thứ tự.
Insertion sort: được gì, mất gì
Ưu điểm
Mảng gần đúng thứ tự chạy gần như O(n)
Ổn định, và sắp xếp tại chỗ
Chèn được dữ liệu đến dần, không chạy lại
Nhược điểm
Mảng ngẫu nhiên tốn khoảng n²/4 phép dịch
Dịch nhiều nên tốn khi phép ghi đắt
Chỉ hợp mảng nhỏ, luôn là bước phụ
Lưu lại để chạy tay sau
Loạt bài thuật toán sắp xếp cho dev Việt Nam.
