Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Не рекурсивный метод сортировки Хоара

Автор: -Студент- 17.11.2006 12:05

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

Автор: lapp 17.11.2006 12:08

Цитата(-Студент- @ 17.11.2006 9:05) *

... Хоара на паскале. blum.gif Если у кого есть ...

А при чем тут язык??.. blink.gif Я имею в виду красный во рту, а не программирования в задании...

Автор: klem4 17.11.2006 12:20

http://forum.pascal.net.ru/index.php?showtopic=3065

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

Автор: volvo 17.11.2006 15:18

Цитата(klem4 @ 17.11.2006 7:20)
Убрать рекурсию думаю вполне можно.

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

Если за основу брать процедуру 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.