Sắp xếp đếm phân phối
Bách khoa toàn thư mở Wikipedia
[sửa] 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.
[sửa] 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 đươ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 vào danh sách a[1..n].
Từ đó có thể viết mã giả đơn giản như sau:
[sửa] Giả mã
Procedure Counter_Sort(list a[1..n],1,M){
Var list Counter[1..M], int i,k
For k=1 to M do Counter(k):=0
For k=1 to n do Counter(a[k]):=Counter(a[k])+1
i:=0
For k=1 to M do{
While Counter(k)>0 do{
i:=i+1
a[i]:=k
counter[k]:=counter[k]-1
}
}
}