Cùng một bài, đọc bằng chữ. Nhanh hơn và tìm lại được bằng Ctrl+F.
Ba nhóm, không phải bảy cái rời
Sáu thuật toán đầu chỉ hỏi được một câu: a có trước b không. Nhóm này không thể nhanh hơn n log n. Counting sort không hỏi câu đó, nên đi vòng qua được giới hạn.
n² dễ hiểu · n log n dùng thật · không so sánh đi đường vòng
Nhóm n²: dễ hiểu, chậm
| Thuật toán | Trung bình | Ổn định |
|---|---|---|
| Bubble | -n² | +có |
| Selection | -n² | -không |
| Insertion | -n² | +có |
Nhóm n log n: dùng thật
| Thuật toán | Trung bình | Ổn định |
|---|---|---|
| Merge | +n log n | +có |
| Quick | +n log n | -không |
| Heap | +n log n | -không |
Counting sort đứng ngoài bảng
Nó không so sánh, nó đếm. Chi phí O(n + k), với k là độ rộng khoảng giá trị. Khoảng hẹp như tuổi hay điểm số thì nhanh hơn cả sáu cái trên.
Thứ tự nên học
Bubble trước, để thấy vòng lặp lồng nhau đang làm gì. Rồi selection và insertion. Sau đó merge, quick, heap. Counting sort chốt lại, vì nó phá giả định của cả sáu cái trên.
Học sort: được gì, mất gì
Ưu điểm
Hiểu big-O bằng ví dụ chạy được
Đọc được thư viện chuẩn đang làm gì
Khung để xếp mọi thuật toán gặp sau
Nhược điểm
Việc thật gần như không tự viết sort
Học thuộc bảng mà không chạy tay thì quên
Phỏng vấn hỏi nhiều hơn công việc dùng
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.
