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

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

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

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


Гость






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


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

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

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


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

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

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


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


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

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

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


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

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


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

 

- Текстовая версия 26.07.2025 5:23
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"