Не рекурсивный метод сортировки Хоара, Что? Где? и Как? Опции

[-Студент-]

Требуется помошью в написании алгоритма не рекурсивной сортировки Хоара на паскале. Если у кого есть уже свои наработки с использованием данного метода то не могли бы вы ими поделится. Препод когда давал задание сказал что данный метод описан в Вирте но нечего такого я там не нашел. В инете нашел лищь одно упоминание что есть 2 способа реализации сортировки Хоара рекурсивный и не рекурсивный с использованием стека(который мне нужен). Но негде описания этого метода нет. Буду благодарен за любую помошью.

[klem4]

Методы сортировок

Убрать рекурсию думаю вполне можно.

[volvo]

Убрать рекурсию думаю вполне можно.

Конечно, можно... Убрать рекурсию можно даже в функции Аккермана... Весь вопрос - КАК...

Если за основу брать процедуру HoarFirst из нашего FAQ-а, то ее итеративный вариант может выглядеть, скажем, вот так (вместе с тестовой программой):

const n = 20;
Type
  arrType = Array[1 .. n] Of Integer;

function _inc(var X: integer): integer;
begin
  inc(X);
  _inc := X;
end;
function dec_(var X: integer): integer;
begin
  dec_ := X;
  dec(X);
end;

var
  stack_ix: integer;
  stack: array[1 .. n] of integer;

procedure push(L, R: integer);
begin
  stack[_inc(stack_ix)] := L;
  stack[_inc(stack_ix)] := R;
end;
procedure pop(var L, R: integer);
begin
  R := stack[dec_(stack_ix)];
  L := stack[dec_(stack_ix)];
end;

procedure iterative_hoar(var ar: arrType; left, right: integer);
var
  finished: boolean;
  X, T, pos_i, pos_j: integer;
begin

  if left < right then begin

    Push(-1, -1);
    Push(left, right);

    finished := false;
    while not finished do begin

      Pop(left, right);

      if (left = -1) and (right = -1) then begin
        finished := true
      end
      else begin

        pos_i := left; pos_j := right;
        x := ar[(left + right) div 2];
        Repeat

          While ar[pos_i] < x Do Inc(pos_i);
          While ar[pos_j] > x Do Dec(pos_j);
          If pos_i <= pos_j Then
            Begin
              T := ar[pos_i]; ar[pos_i] := ar[pos_j]; ar[pos_j] := T;
              Inc(pos_i); Dec(pos_j)
            End

        Until pos_i > pos_j;
        If left < pos_j Then push(left, pos_j);
        If pos_i < right Then push(pos_i, right);

      end;

    end;

  end;
end;


const
  a: arrType = (44, 55, 12, 42, 94, 18, 36, 67, 44, 55,
                12, 42, 94, 18,  6, 67, 94, 55, 72, 62);
var i: integer;

begin
  writeln('start hoar iterative sort:');
  iterative_hoar(a, 1, n);

  for i := 1 to n do write(a[i]:3);
  writeln;
end.