Thuật toán sắp xếp bằng đếm phân phối

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCSAPXEP/

1. Đề bài sắp xếp bằng đếm phân phối

Sắp xếp dãy tăng dần.

Input

– Dòng đầu chứa số n ( số phần tử của dãy 1<=n<=1000)

– n dòng sau, mỗi dòng là 1 phần tử của dãy (giá trị tuyệt đối không quá 1000)

Output

Mỗi phần tử của dãy in trên 1 dòng, theo thứ tự tăng dần.

Lưu ý:

Đây là bài sắp xếp cơ bản. Bạn nên sử dụng nhiều thuật toán sắp xếp khác nhau để submit: Sắp xếp chọn, nổi bọt, chèn, quicksort, heapsort, hàm sort trong STL algorithm,….

Example

Input:
3
3
2
1

Output:
1
2
3

2. Code Sắp xếp bằng thuật toán đếm phân phối pascal

xem kỹ hơn về thuật toán: https://kienthuc24h.com/tim-hieu-va-cai-dat-thuat-toan-counting-sort/

var
        DD:array[-1000..1000] of word;
        n,j:word;
        tam,i:integer;

begin
        readln(n);
        fillchar(dd,sizeof(dd),0);
        for i:=1 to n do
                begin
                        readln(tam);
                        inc(dd[tam]);
                end;

        for i:=-1000 to 1000 do
                for j:=1 to dd[i] do
                        writeln(i);
end.

độ phức tạp O(n).

BCSAPXEP spoj PTIT