02/10/2018, 14:16
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 ...
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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
