Cùng một bài, đọc bằng chữ. Nhanh hơn và tìm lại được bằng Ctrl+F.
Đếm, rồi rải lại
Có 1000 sinh viên, điểm từ 0 đến 10. Đi một lượt đếm mỗi mức điểm có bao nhiêu người, rồi rải lại theo thứ tự điểm. Không có phép so sánh nào giữa hai sinh viên.
1000 phần tử, 11 ô đếm. Một lượt đếm, một lượt rải.
Vì sao nó vượt được giới hạn
Định lý n log n nói về thuật toán chỉ hỏi được một câu: a có trước b không. Counting sort nhìn thẳng vào giá trị và dùng nó làm chỉ số mảng, nên định lý không áp cho nó.
k là độ rộng, không phải n
k bằng giá trị lớn nhất trừ nhỏ nhất cộng một. Điểm 0 đến 10 thì k bằng 11, dù có một triệu sinh viên. Chi phí là O(n + k), nên k nhỏ mới là chỗ nó thắng.
Khi nào đừng dùng
Khoá là ID người dùng chạy tới hàng tỉ: k lớn hơn n hàng nghìn lần, và bạn cấp phát một mảng đếm khổng lồ gần như rỗng. k xấp xỉ n thì vẫn tốt.
Nó là nền của radix sort
Radix sort sắp theo từng chữ số, mỗi vòng gọi counting sort trên đúng một chữ số. Vòng nào cũng phải ổn định, nếu không thứ tự các vòng trước bị phá mất.
Counting sort: được gì, mất gì
Ưu điểm
O(n + k), thắng khi khoảng giá trị hẹp
Ổn định nếu cài đúng, dùng được cho radix
Không đệ quy, code ngắn và đọc thẳng
Nhược điểm
Chỉ dùng được khi khoá là số nguyên
Tốn bộ nhớ O(k), khoảng rộng là hỏng
Không sắp được theo thứ tự tự định nghĩa
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.
