Cùng một bài, đọc bằng chữ. Nhanh hơn và tìm lại được bằng Ctrl+F.
Nhóm một: dễ hiểu, chậm khi dữ liệu lớn
| Thuật toán | Tốc độ | Điểm riêng |
|---|---|---|
| Bubble sort | n² | dừng sớm nếu đã đúng |
| Selection sort | n² | +ít phép ghi nhất |
| Insertion sort | n² | +nhanh khi gần đúng |
Nhóm hai: thư viện thật dùng nhóm này
| Thuật toán | Tốc độ | Điểm riêng |
|---|---|---|
| Merge sort | n log n | +ổn định, đoán được |
| Quick sort | n log n | -xấu nhất vẫn n² |
| Heap sort | n log n | +không cần bộ nhớ phụ |
Nhóm ba: không so sánh gì cả
Counting sort không hỏi phần tử nào lớn hơn. Nó đếm mỗi giá trị xuất hiện bao nhiêu lần, rồi rải lại theo thứ tự. Vì không so sánh, nó đi vòng qua được giới hạn n log n.
Chỉ dùng khi khoá là số nguyên trong khoảng hẹp
Thứ tự nên học
Học bubble sort trước, vì nó cho thấy rõ vòng lặp lồng nhau. Rồi selection sort và insertion sort, cùng nhóm nhưng đánh đổi khác nhau. Sau đó merge sort, quick sort, heap sort. Counting sort học cuối cùng.
Học thuật toán sắp xếp để làm gì
Ưu điểm
Hiểu big-O bằng ví dụ chạy tay được
Đọc được thư viện chuẩn đang làm gì
Dễ xếp nhóm cho thuật toán gặp sau này
Nhược điểm
Việc thật gần như không tự viết hàm 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 lúc làm việc thật
Bài sau: bubble sort từng bước
Lưu lại để đối chiếu khi đọc từng bài trong loạt này.
