Метод челнока

[kuraga]

Добрый вечер!
Задали написать написать прогу сортировки методом челнока и отразить число сравнений и перемещений.
Сказал, что неверное число.
Вопрос: как этот метод правильно называется? Сколько сравнений и перемещений он делает при обработке обратно упорядоченного массива?
Спасибо.

[p51x]

Так вы хотя бы кратко основные идеи озвучьте...

[kuraga]

Нашел еще одно названия - метод пузырька с просеиванием.
Это пузырек, только после нахождения первой неупорядоченной пар идет движение обратно. Потом снова вперед, потом назад. И т.д.
Код такой:

Используется синтаксис Pascal

{ gt - "больше?", exch - обменять }
p:=1;
r:=n-1;
q:=n-1;
repeat
   for i:=r downto p do
       if gt(items[i-1],items[i],comp) then
                      begin exch(items,i-1,i,trans); q:=i; end;
   p:=q+1;
   for i:=p to r do
                   if gt(items[i-1],items[i],comp) then
                      begin exch(items,i-1,i,trans); q:=i; end;
   r:=q-1;
until q>r;
 

[kuraga]

Понял. Это сортировка перемешиванием, шейкерная сортировка, сортировка просеиванием, сортировка челноком. Вот сколько названий!

Но сколько все же сравнений и перемещений для обратно упорядоченного массива? А для общего случая? Где посмотреть?

[kuraga]

Ну пожалуйста, помогите!

[Maslov]

Сколько у Вас получается сравнений и перемещений и почему?
Для проверки можно вставить в Вашу программу два счетчика (один увеличивать при каждом сравнени, другой -- при каждом перемещении) и вывести их значения при завершении сортировки.
Ну а про общий случай почитайте у Кнута (Т.3): http://goo.gl/peu9

[kuraga]

Для упорядоченного массива $\frac{n^2}{2}$ сравнений. В чем дело?

Используется синтаксис Pascal

var l, r, j, t: Integer;
begin
comp:=0;
trans:=0;
l:= 1;
r:= n-1;

while l <= r do
      begin

      for j:=l to r do
          if gt(items[j-1],items[j],comp) then
                         exch(items,j-1,j,trans);
      dec(r);

      for j:=r downto l do
          if gt(items[j-1],items[j],comp)then
                         exch(items,j-1,j,trans);
      inc(l);

      end;
 

[venco]

Чтобы было меньше, надо уменьшать границы сканирования не на единицу, а до последнего свопа.

[kuraga]

Используется синтаксис Pascal

comp:=0;
trans:=0;

l:=1;
r:=n-1;
p:=n-1;

while l<=r
      begin
      for i:=l to r do
          if gt(items[i-1],items[i],comp) then
                         begin exch(items,i-1,i,trans); p:=i; end;
      r:=p-1;

      for i:=r downto l do
          if gt(items[i-1],items[i],comp)then
                         begin exch(items,i-1,i,trans); p:=i; end;
      l:=p+1;
      end;
 

Что-то можно улучшить? Для упорядоченного массива теперь 97 сравнений при длине в 50. Норм?

[venco]

Перед каждым из внутренних циклов присваивать переменной $p$ такое значение, чтобы если обменов не было совсем, то диапазон занулился.
По идее для упорядоченного массива достаточно $length-1$ сравнений.

[kuraga]

Сделал так. Оптимально?

Используется синтаксис Pascal

comp:=0;
trans:=0;

l:=1;
r:=n-1;

while l<=r
      begin
      p:=1;
      for i:=l to r do
          if gt(items[i-1],items[i],comp) then
                         begin exch(items,i-1,i,trans); p:=i; end;
      r:=p-1;

      p:=n-1;
      for i:=r downto l do
          if gt(items[i-1],items[i],comp)then
                         begin exch(items,i-1,i,trans); p:=i; end;
      l:=p+1;
      end;