Sắp xếp đếm

Sắp xếp đếm hoàn toàn không sắp xếp bằng cách so sánh các giá trị. Nếu bạn biết mọi giá trị đều là số nguyên trong khoảng, chẳng hạn, từ 1 đến 40, bạn chỉ cần đếm mỗi giá trị có bao nhiêu, rồi từ các số đếm suy ra mỗi giá trị thuộc về đâu. Với khoảng nhỏ, đó gần như là cách sắp xếp nhanh nhất có thể.

Các cột của một danh sách, một dải bộ đếm cho biết mỗi giá trị xuất hiện bao nhiêu lần, và một hàng bộ đệm nơi mỗi giá trị có đoạn riêng
Các cột của một danh sách, một dải bộ đếm cho biết mỗi giá trị xuất hiện bao nhiêu lần, và một hàng bộ đệm nơi mỗi giá trị có đoạn riêng

Đếm

Tìm giá trị nhỏ nhất và lớn nhất, rồi tạo một bộ đếm cho mỗi giá trị ở giữa, tất cả bắt đầu từ không. Đọc danh sách một lần từ đầu đến cuối và cộng một vào bộ đếm của mỗi giá trị bạn gặp. Lúc này các bộ đếm tạo thành một biểu đồ tần suất: có bao nhiêu số 1, bao nhiêu số 2, và cứ thế. Với n giá trị và k bộ đếm, việc này mất n bước.

Cộng dồn

Các giá trị bằng giá trị nhỏ nhất đứng đầu, nên đoạn của chúng bắt đầu ở vị trí 1. Đoạn của giá trị kế tiếp bắt đầu ngay sau đó, và cứ thế: mỗi đoạn bắt đầu sau tổng của tất cả các số đếm đứng trước nó. Các tổng dồn này, gọi là tổng tiền tố, biến biểu đồ tần suất thành bản đồ của danh sách đã sắp xếp. Việc này mất k bước.

Đặt vào

Đọc danh sách lần thứ hai và chuyển mọi giá trị đến chỗ trống kế tiếp trong đoạn của nó. Vì các giá trị được chuyển theo thứ tự xuất hiện, các giá trị bằng nhau giữ nguyên thứ tự ban đầu: sắp xếp đếm là ổn định. Chép bộ đệm trở lại, và danh sách đã được sắp xếp. Ứng dụng cho thấy mỗi bộ đếm giảm dần khi các giá trị của nó được đặt vào chỗ.

Một ví dụ

Lấy 4, 1, 3, 4, 2, 1, 4. Các bộ đếm cho 1 đến 4 kết thúc ở 2, 1, 1 và 3. Cộng dồn cho ra các đoạn: các số 1 ở vị trí 1 và 2, số 2 ở vị trí 3, số 3 ở vị trí 4, và các số 4 ở vị trí 5 đến 7. Đặt các giá trị theo thứ tự danh sách cho ra 1, 1, 2, 3, 4, 4, 4: 7 giá trị đã đếm, 14 lần di chuyển, 4 bộ đếm, và không có phép so sánh nào.

Khi nào nên dùng

Tổng khối lượng công việc tăng theo n + k. Khi k nhỏ so với n, như một nghìn điểm thi từ 0 đến 100, sắp xếp đếm nhanh hơn mọi thuật toán sắp xếp dựa trên so sánh, vốn cần khoảng n log₂ n phép so sánh. Khi khoảng rộng, nó lãng phí: vài giá trị trải đến một triệu cần một triệu bộ đếm. Sắp xếp theo cơ số giải quyết điều đó bằng cách chạy sắp xếp đếm một lần cho mỗi chữ số, nên mỗi lượt chỉ cần mười bộ đếm. Harold Seward đã mô tả sắp xếp đếm, cùng với sắp xếp theo cơ số, vào năm 1954.

Tự khám phá

Mở ứng dụng và nhấn Bước. Dải nằm giữa danh sách và hàng bộ đệm hiển thị một bộ đếm cho mỗi giá trị. Hãy xem các bộ đếm tăng dần khi danh sách được đọc, các đoạn xuất hiện trong bộ đệm khi các số đếm được cộng dồn, và các bộ đếm giảm lại khi các giá trị được đặt vào chỗ. Chọn ít giá trị khác nhau để thấy các đoạn lớn, hoặc nhập các số cách xa nhau để thấy một khoảng rộng cần bao nhiêu bộ đếm.

Câu hỏi thường gặp

Độ phức tạp thời gian của sắp xếp đếm là bao nhiêu?

O(n + k) với n giá trị và k giá trị có thể có, cùng O(n + k) bộ nhớ phụ cho các bộ đếm và bộ đệm.

Vì sao sắp xếp đếm không phải lúc nào cũng nhanh nhất?

Vì chi phí của nó phụ thuộc vào khoảng giá trị, không chỉ vào số lượng giá trị. Nếu khoảng lớn hơn danh sách rất nhiều, hầu hết bộ đếm vẫn ở mức không, và thời gian cùng bộ nhớ bị lãng phí.

Sắp xếp đếm có xử lý được số âm không?

Có. Các bộ đếm chạy từ giá trị nhỏ nhất đến lớn nhất, nên trừ đi giá trị nhỏ nhất sẽ được chỉ số của bộ đếm. Ứng dụng cũng làm như vậy.

Sắp xếp đếm có ổn định không?

Có, miễn là các giá trị được chuyển theo thứ tự danh sách đến chỗ trống kế tiếp trong đoạn của chúng. Sắp xếp theo cơ số dựa vào điều đó.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Thử sắp xếp đếm