quicksort

procedure SorterEtArray(var a: TableArray; n: integer);
var i, k, v: integer;
begin
  for k:=1 to n-1 do begin
    i:=k;
    v:=a[i];
    while (i>0) and (a[i-1]>v) do begin
      a[i]:=a[i-1];
      dec(i);
    end;
    a[i]:=v;
  end;
end;

dcgeek>

Det er vist ikke en QuickSort !

Tak for svaret, men det var en quicksort rutine jeg var efter dette er en bobblesort.

Mange hilsner,

Rune

{ TQuickSort }

  procedure TQuickSort.Sort(var A: array of Integer);

    procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
    var
      Lo, Hi, Mid, T: Integer;
    begin
      Lo := iLo;
      Hi := iHi;
      Mid := A[(Lo + Hi) div 2];
      repeat
        while A[Lo] < Mid do Inc(Lo);
        while A[Hi] > Mid do Dec(Hi);
        if Lo <= Hi then
        begin
          VisualSwap(A[Lo], A[Hi], Lo, Hi);
          T := A[Lo];
          A[Lo] := A[Hi];
          A[Hi] := T;
          Inc(Lo);
          Dec(Hi);
        end;
      until Lo > Hi;
      if Hi > iLo then QuickSort(A, iLo, Hi);
      if Lo < iHi then QuickSort(A, Lo, iHi);
    end;

  begin
    QuickSort(A, Low(A), High(A));
  end;

En hurtig konvertering fra C til standard Pascal:

program qstest(input,output);

type
  integer_array = array [0..10] of integer;

procedure qs(n : integer; var a: integer_array);

procedure qs_help(n1 : integer; n2 : integer; var a : integer_array);

var
  tmp,pivot : integer;
  l,r : integer;

begin
  l := n1;
  r := n2;
  pivot := a[(n1+n2) div 2];
  repeat
      while(a[l] < pivot) do l := l+1;
      while(a[r] > pivot) do r := r-1;
      if(l <=r ) then begin
        tmp := a[l];
        a[l] := a[r];
        a[r] := tmp;
        l := l+1;
        r := r-1;
      end;
  until(l>r);
  if(n1 < r) then qs_help(n1,r,a);
  if(l < n2) then qs_help(l,n2,a);
end;

begin
  qs_help(0, n-1, a);
end;

var
  a : integer_array;
  i : integer;

begin
  for i := 0 to 9 do a[i] := 10-i;
  for i:= 0 to 9 do writeln(a[i]);
  qs(10, a);
  for i:= 0 to 9 do writeln(a[i]);
end.

lidt for hurtig...

linien med VisualSwap skal fjernes...

Faktisk er der et vist overhead ved brug af rekursive kald, så på små arrays med 10-15 elementer kan det anbefales at benytte insertion sort eller bubble sort.

Så lad quicksort splitte array'sene op, og lad bubblesort om at sortere de mindste arrays.

Fantastisk -

Mange tak,

Rune