Sắp xếp đếm phân phối

Sắp xếp đếm phân phối là một phương pháp sắp xếp có độ phức tạp tuyến tính. Nó dựa trên giả thiết rằng, các khoá cần sắp xếp là các số tự nhiên giới hạn trong một khoảng nào đó, chẳng hạn từ 1 đến N.

Giải thuật sắp xếp đếm phân phối

Để đơn giản ta giả sử các phần tử của danh sách a[1..n] nhận các giá trị tự nhiên trong khoảng [1..M].

Sắp xếp đếm phân phối đầu tiên đếm các phần tử thuộc danh sách nhận giá trị k với 1 <= k <= M. Các giá trị đếm được ghi vào mảng Counter[1..M]. Sau đó khi duyệt theo k từ 1 đến M, ta lần lượt xếp Counter(k) phần tử của k vào danh sách a[1..n].

Cải tiến thuật toán sắp xếp đếm phân phối để có thể làm việc được với cả số âm (bằng cách xác định giá trị MIN của mảng cần sắp xếp, rồi trừ tất cả phần tử đi MIN trước khi vào "xử lý đếm vào mảng tạm", khi chép ngược từ mảng tạm vào mảng cần sắp, ta chỉ việc cộng thêm MIN vào khóa k (k=0 -> k->M, do viết trên ngôn ngữ pascal, nên chỉ số đầu của mảng là 0). Hàm viết bằng C++ như sau:

// min, max lần lượt là GTLN và GTNN của mảng arr[] cần sắp xếp
void CountingSort(int arr[], int n, int mi, int mx) 
{ 
    int d = 0, cs = mx - mi; 
    
    // Mảng lưu kết quả đếm
    int count[cs + 1]; 
    
    // Khởi tạo giá trị của mỗi phần tử trong mảng đếm là 0
    for(int i = 0; i <= cs; i++) 
        count[i] = 0;
    
    // Xét số lần xuất hiện của các số trong mảng chính và gán vào mảng đếm    
    for(int i = 0; i < n; i++) 
        count[arr[i] - mi]++;
        
    // Gán các giá trị của mảng đếm vào mảng chính, ở đây mảng chính đã được xét xong 
    // nên ta có thể viết đè được
    for(int i = 0; i <= cs; i++) 
        if(count[i] > 0) 
            for(int j = 1; j <= count[i]; j++) 
                arr[d++] = i + mi; 
}