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/

Nội dung bài viết

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

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.

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