Quick Sort iteracyjny / nierekurencyjny

Witam
Czy ma ktoś może implementacje w Delphi/PASCALU quicksort iteracyjnego, nierekurencyjnego dla tablicy integerów ?

link
Na dole artu masz przykładowe kody.

pzdr.

Ale to jest chyba zwyczajny quicksort, a ja szukam nie rekurencyjnego = to jest o ile się nie mylę jakiś ze stosem

W linku powyżej masz opis algorytmu...postępuj z nim...to napiszesz kod, o który Ci chodzi.

pzdr.

Tablica pomocnicza, do niej odkładasz /w sumie robi za stros/ klamoty z pierwszego wywołania, drugie przekszatałcasz na ogonowe - nie ma nic do roboty.

Myślałem że może ktoś ma gotowy algorytm bo moje zdolności programistyczne na razie są marne. Rozumiem że pierwsze wywołanie algorytmu ma elementy podzielone na dwa podzbiory odłożyć do innej tablicy ?? A co to są te ogonowe ?

program Quick_Sort_dziel_i_zwyciezaj;

const N = 20; // Liczebność zbioru.

var
  d : array[1..N] of integer;

// Procedura sortowania szybkiego
//-------------------------------

procedure Sortuj_szybko(lewy, prawy : integer);
var
  i,j,piwot,x : integer;
begin
  i := (lewy + prawy) div 2;
  piwot := d[i]; d[i] := d[prawy];
  j := lewy;
  for i := lewy to prawy - 1 do
    if d[i] < piwot then
    begin
      x := d[i]; d[i] := d[j]; d[j] := x;
      inc(j);
    end;
  d[prawy] := d[j]; d[j] := piwot;
  if lewy < j - 1  then Sortuj_szybko(lewy, j - 1);
  if j + 1 < prawy then Sortuj_szybko(j + 1, prawy);
end;

// Program główny
//---------------

var
  i : integer;
begin
// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
// a następnie wyświetlamy jej zawartość

  randomize;
  for i := 1 to N do d[i] := random(100);
  writeln('Przed sortowaniem:'); writeln;
  for i := 1 to N do write(d[i] : 4);
  writeln;

// Sortujemy

  Sortuj_szybko(1,N);

// Wyświetlamy wynik sortowania

  writeln('Po sortowaniu:'); writeln;
  for i := 1 to N do write(d[i] : 4);
  writeln;
  writeln('Nacisnij Enter...');
  readln;
end.

<sory blad kopiowania .... z pliku, sadzilem ze wkleilo calosc... a tu zonk :(>

Bardzo śmieszne :-D

sortman napisał(a)

Bardzo śmieszne :-D

sory maly blad kopiowania ... nie skopiowalo mni wszystkiego ... teraz powinno smigac :P
algorytm jest oparty o metode dziel i zwyciezaj ... u mnie dziala bez problemu ;)
pozdroi mi skuzi za blad tech .
zlosliwosc urzadzen martwych :P

// a widział ktoś urządzenia żywe? (dop. deus)
// a w temacie jest, że nierekurencyjny... - Ł

Hmmm no fajnie tylko ten algorytm jest rekurencyjny = zwyczajny quick sort, a ja szukam nierekurencyjnego (iterative quicksort)

nie wiem czy to tak ma być bo pascala dawno nie używałem, poza tym przydałoby się usuwanie starych elementów ale to jest zarys (niesprawdzany) jak to ma wyglądać:

program Quick_Sort_dziel_i_przegrywaj;

const N = 20; // Liczebność zbioru.

var
  d : array[1..N] of integer;

// Procedura sortowania szybkiego
//-------------------------------

procedure Sortuj_wolno();
var lewe, prawe: array of byte;
  lewy, prawy, i, j, k, piwot, x: integer;
begin
  SetLength(lewe, 1);
  SetLength(prawe, 1);

  lewe[0] := 1; // czy lewe[1] ?
  prawe[0] := N;

  k := 0;
  while k < Length(lewe) do begin
    lewy := lewe[k];
    prawy := prawe[k];

    i := (lewy + prawy) div 2;
    piwot := d[i]; d[i] := d[prawy];
    j := lewy;
    for i := lewy to prawy - 1 do
      if d[i] < piwot then
      begin
        x := d[i]; d[i] := d[j]; d[j] := x;
        Inc(j);
      end;
    d[prawy] := d[j]; d[j] := piwot;
    if (lewy < j - 1) or (j + 1 < prawy) then begin
      i := Length(lewe);
      SetLength(lewe, i + 1);
      SetLength(prawe, i + 1);

      if lewy < j - 1 then begin
        lewe[i] := lewy;
        prawe[i] := j - 1;
      end;
      if j + 1 < prawy then begin
        lewe[i] := j + 1;
        prawe[i] := prawy;
      end;
    end;
    Inc(k);
  end;
end;

// Program główny
//---------------

var
  i : integer;
begin
// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
// a następnie wyświetlamy jej zawartość

  randomize;
  for i := 1 to N do d[i] := random(100);
  writeln('Przed sortowaniem:'); writeln;
  for i := 1 to N do write(d[i] : 4);
  writeln;

// Sortujemy

  Sortuj_wolno();

// Wyświetlamy wynik sortowania

  writeln('Po sortowaniu:'); writeln;
  for i := 1 to N do write(d[i] : 4);
  writeln;
  writeln('Nacisnij Spacebar...');
  readkey;
  writeln('Haha, żartowałem - Enter');
  readln;
end.

To trzeba zrobić jakoś ze stosem = znalazłem coś takiego :

//QUICKSORT - ITERACYJNY

  PROCEDURE _QUICKSORT;
  const m=12;
  var j,i,l,p: index;
      x,w: object;
      s: 0..m;
      stack: array[1..m] of
            record
            l,p: index
            end;
BEGIN
s:=1;
stack[1].l:= 1;
stack[1].p:= n;
repeat {wez rzadanie z wierzchołka stosu}
l:= stack[s].l;
p:= stack[s].p;
s:= s-1;
repeat {dziel a[l]..a[p]}
  i:= l;
  j:= p;
  x:= a[(l+p) div 2];
  repeat
    while (a[i].key < x.key) do
      i:= i+1;
    while (x.key < a[j].key) do
      j:= j-1;
    if (i<=j) then
      begin
        w:=a[i]; a[i]:=a[j]; a[j]:=w;
        i:= i+1;
        j:= j-1;
      end
until (i>j);
if (i<p) then
  begin {zadanie posortowania prawej czesci}
  s:= s+1;
  stack[s].l:= i;
  stack[s].p:= p;
end;
p:=j
until (l>=p)
until (s=0)
END {_QUICKSORT}

Tylko nie wiem co to jest index i co to jest to key np a[j].key
Chyba trzeba tu jeszcze zadeklarować tą tablice a oraz co to jest index

i to key też trzeba zadeklarować jakoś

Powracając do tematu = ma ktoś może jakiś sprawdzony algorytm quicksort nierekurencyjny ???