IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Не рекурсивный метод сортировки Хоара, Что? Где? и Как?
сообщение
Сообщение #1


Гость






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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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

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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата(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.
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 23:30
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name