Помощь - Поиск - Пользователи - Календарь
Полная версия: Всё те же сортировки
Форум «Всё о Паскале» > Pascal, Object Pascal > Теоретические вопросы
Vardes
Есть у нас лаборант, которой мы сдаём наши проги. Сегодня пытался отчитаться по сортирове методом Шелла.Бегло прочитал я теорию и сделал вот что: пока шаг в сортировке был >1 я сортировал элементы пузырьковым методом,ну а потом напоследок сортировал методом вставок,когда шаг=1.
Ну а лаборант наш-это не лектор, что в методичке написано вначале,так оно и должно быть, а там в течение всех шагов массив сортируется методом вставок(ещё и иллюстрация есть).Хотя в конце есть пометка на то,что в качестве базового алгоритма сортировки может использоваться любой другой.
Вот я и хотел у народа спросить, имею ли я право на любой алгоритм сортировки.И могу ли я доказать преподу,что я прав wacko.gif

(Уже впринципе неважно)
Vardes
У меня теперь такой вопрос к знатокам.Сортировка Шелла как я правильно понимаю заключается в том,что мы из массива вытаскиваем подмассив с определённым шагом, его сортируем и опять заносим в основной массив.Так?
Вот в инете нашёл алгоритм сортировки, якобы Шелла как говорят:
Код

Procedure Sort( var a : seq);
Var d, i, t : integer;
   k : boolean; { пpизнак пеpестановки }
  begin
  d:=N div 2;  { начальное значение интеpвала }

  while d>0 do begin { цикл с yменьшением интеpвала до 1 }

    { пyзыpьковая соpтиpовка с интеpвалом d }
    k:=true;
    while k do begin  { цикл, пока есть пеpестановки }
      k:=false; i:=1;
      for i:=1 to N-d do begin
        { сpавнение эл-тов на интеpвале d }
        if a[i]>a[i+d] then begin
          t:=a[i]; a[i]:=a[i+d]; a[i+d]:=t; { пеpестановка }
          k:=true;  { пpизнак пеpестановки }
          end; { if ... }
        end; { for ... }
      end; { while k }
    d:=d div 2;  { yменьшение интеpвала }
    end;  { while d>0 }
end;

Но если тут присмотреться, то на самом деле мы просто попарно сравниваем элементы отстоящие др. от др. на определённый шаг.Но это же не сортировка Шелла,или я ошибаюсь? nea.gif
volvo
Чем же это не сортировка Шелла по-твоему? Реализовано несколько необычно, но по всем признакам очень похоже на ShellSort...
Vardes
Дело то в том,что мы просто попарно сравниваем эл-ты отстоящие др. от др. на определённый шаг и всё. А как мне помнится, мы должны из массива вытащить подмассив, его отсортировать и загнать опять в основной массив.
К примеру:
3 2 1 4 7 2 3 6 18 11 9 5 3 - отсоритрованный массив после шага 6
Берём шаг равный 3 и вытаскиваем подмассив:
3 4 3 11 3
Его сортируем и получаем:
3 3 3 4 11
Заносим в основной массив:
3 2 1 3 7 3 6 18 4 9 5 11
(потом переходим к следущему эл-ту(в нашем случае он равен 2) и опять вытаскиваем подмассив)
Вот правильный алгоритм сортировки.
red_alex
По-моему не обязательно вытаскивать подмассив и сортировать его отдельно, кому как больше нравится. Я вот делал эту сортировку и тоже сравнивал элементы отстоящие др от др.
Vardes
Я может с вами и соглашусь, тока вот преподы со мной согласиться ну никак не хотят.Поэтому может есть у кого-нить процедура правильной сортировки?
volvo
Вот реализация ShellSort:
Сортировка массива методом Шелла
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.