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