combsort.pas
Bài toán
Sắp xếp dãy số bằng thuạt toán Comb Sort.
Độ phức tạp
O(n log n)
Code này của Nguyễn Tiến Trung Kiên
{$mode objfpc}
uses math;
var
a: array [1..100000] of integer;
n: integer;
function can_swap(var a, b: integer): boolean;
var
c: integer;
begin
if a<=b then exit(false);
c:=a; a:=b; b:=c;
exit(true);
end;
procedure combsort(a: PInteger; n: integer);
var
i, g: integer;
swapped: boolean;
begin
g := n;
repeat
g := max(g * 10 div 13, 1);
swapped := false;
for i := 1 to n-g do
if can_swap(a[i], a[i+g]) then
swapped := true;
until (g=1) and (not swapped);
end;
var
i: integer;
begin
readln(n);
for i := 1 to n do
read(a[i]);
combsort(@a[0], n);
for i := 1 to n do
write(a[i], ' ');
writeln;
end.
Nhận xét