Counting Sort – Thuật toán sắp xếp đếm phân phối

Counting sort là một thuật toán sắp xếp cực nhanh một mảng các phần tử mà mỗi phần tử là các số nguyên không âm; Hoặc là một danh sách các ký tự được ánh xạ về dạng số để sort theo bảng chữ cái. Counting sort là một thuật toán sắp xếp các con số nguyên không âm, không dựa vào so sánh. Trong khi các thuật toán sắp xếp tối ưu sử dụng so sánh có độ phức tạp O(nlogn) thì Counting sort chỉ cần O(n) nếu độ dài của danh sách không quá nhỏ so với phần tử có giá trị lớn nhất.

Ý tưởng của Counting sort

Hình ảnh dưới đây cho chúng ta thấy cách hoạt động của thuật toán sắp xếp này.

Bước 1:

Trong bước đầu tiên, chúng tôi đếm số lần xuất hiện của từng phần tử trong mảng cần sắp xếp A. Kết quả được lưu vào mảng C.

Counting Sort

Mình xin 5 phút quảng cáo nha =))

Bước 2: Ở bước này, chúng ta cần xem xét sửa đổi giá trị của C. C[i] thể hiện giới hạn trên của chỉ số của phần tử i sau khi sắp xếp.

Counting Sort

Bước 3: Duyệt qua từng phần tử của A và đặt nó vào đúng chỉ số của mảng chứa các giá trị đã sắp xếp B dựa vào C.

Counting Sort

Cài đặt thuật toán Counting Sort

Code C:

Code C++:

 

Code Python:

Các source code cài đặt trên đây được tham khảo tại Github.

avatar
  Subscribe  
Notify of