Работа 3.6 Упр.29 ГДЗ Семакин 10 класс (Информатика)

Задача

Рассмотрим вариант решения задания из учебника Семакин, Хеннер, Шеина 10 класс, Бином: 29. Шейкер-сортировка. Алгоритм «пузырьковой» сортировки легко улучшить. Разумно запомнить, производился ли на данном проходе какой-либо обмен. Если нет, то алгоритм можно закончить. Еще одно улучшение заключается в том, что периодически меняется направление сортировки, которое борется с некоторой асимметрией «пузырькового» метода. Написать программу, реализующую данный улучшенный алгоритм. *Цитирирование задания со ссылкой на учебник производится исключительно в учебных целях для лучшего понимания разбора решения задания. 10 semakin10 pract/3-6/29 98

Подробный ответ

Реализуем шейкер-сортировку — улучшенный вариант пузырьковой сортировки. Сначала просматриваем массив слева направо и «всплывающие» большие элементы перемещаем вправо. Затем просматриваем массив справа налево и перемещаем меньшие элементы влево. После каждого прохода границы области сортировки сужаются.

Если за проход не было ни одного обмена, сортировку можно завершить раньше.

const nmax=100;
var
  a: array[1..nmax] of integer;
  n,i,tmp,l,r: integer;
  swapped: boolean;
begin
  randomize;
  write(‘n: ‘);
  readln(n);
  writeln(‘:’);
  for i:=1 to n do
  begin
    a[i]:=random(99)+1;
    write(a[i]:3);
  end;
  writeln;
  l:=2;
  r:=n;
  while l<=r do
  begin
    swapped:=false;
    for i:=l to r do
      if a[i]<a[i-1] then
      begin
        tmp:=a[i];
        a[i]:=a[i-1];
        a[i-1]:=tmp;
        swapped:=true;
      end;
    r:=r-1;
    if not swapped then break;
    swapped:=false;
    for i:=r downto l do
      if a[i]<a[i-1] then
      begin
        tmp:=a[i];
        a[i]:=a[i-1];
        a[i-1]:=tmp;
        swapped:=true;
      end;
    l:=l+1;
    if not swapped then break;
  end;
  writeln(‘:’);
  for i:=1 to n do write(a[i]:3);
  readln;
end.