Автор Тема: Истинная Шейкерная сортировка  (Прочитано 10835 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Истинная Шейкерная сортировка
« : ПЭТРам 28, 2009, 01:46:41 am »
 O_o

Столкнулся с проблемой. Вообщем третий день долбаюсь над Шейкерной сортировкой. (улучшенная пузырьковая).

Вообщем по интернету куча инфы, что это такое, везде говориться, что  нужно в разных направлениях просматривать массив, количество обменов не меняется, а уменьшается количество сравнений.

На мое удивлениевсе исходники, таких шейкерных сортировок, почему-то оказались медленее моей пузырьковой (оценивал по количеству сравнений). Причем рекорд побил пример в книге Шилдта (почти в 3 раза!!!). В итоге я пришел к выводу, что сам перестал после такого понимать, что такое Шейкерная сортировка,  и наверное ни я один. Когда пытаюсь проанализировать как-что работает в очередной программе, то после каждой иитерации  глаза лезут на лоб, а рука незаметно тянеться к кнопке POW :).
Насколько я понимаю, Шейкерная сортировка, это не пузырьковая в двух направления??.

Ниже выложил сбацаную прогу, там Пузырьковая сортировка, а также одна псевдо-Шейкерная (пузырьковая в двух направлениях) - моя реализациия, которая чуть хуже пузырьковой, а также  вторая почти Шейкерная сортировка, подсмотренная и в наглую скопированная с конкурирующего сайта.
Причем последняя, как и должно, быстро упорядочивает "почти" отсортированный массив, но вот упорядоченный массив, сортирует хуже пузырьковой (судя по всему баги на последних итерациях).
   
Вроде так просто, но я блин запутался..., скорее потому-что не понимаю (не осознаю) до конца алгоритма. Спасибо, кто поможет.
« Последнее редактирование: ёоЭм 05, 2009, 09:34:12 am от Alex_cs_gsp »
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн Inf-root

  • Глобальный модератор
  • Коллежский советник
  • *****
  • Сообщений: 571
  • Репутация: 21
  • Пол: Мужской
Re: Истинная Шейкерная сортировка
« Ответ #1 : ПЭТРам 28, 2009, 12:05:57 pm »
посмотри. может поможет: http://ermak.cs.nstu.ru/cprog/book2001/25-02.htm#def45
В старости нет лучшего утешения,
чем сознание того, что все силы в
молодости отданы делу, которое не
стареет.
(с) Артур Шопенгауэр (немецкий философ)

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Истинная Шейкерная сортировка
« Ответ #2 : ПЭТРам 28, 2009, 03:52:06 pm »
Да чуть помогло, вот сделал, теперь при наихудшом случае эфективность как у пузырьковой, а когда массив почти упорядоченных то количество сравнений действительно меньше. Для этого нужно не попасть лишний раз в цикл for(;;). Но только почему так происходит, для каких случаев математически, я понять не могу. Буду рад если кто сможет объяснить. Ниже скомпилированная версия, нужная ф-я SortShake 3;


void cSorty::ShakerSort3()
{
int exch=0; //number of exchange
int num_of_equal=0; //number of comparison

int k=0;
int temp=0;
int lb=0,rb=size_itsMas-1;

while(lb<rb)
{
for(int i=lb;i<rb;i++)
{
num_of_equal++;
if(itsMas[i]>itsMas[i+1])
{
temp=itsMas[i];
itsMas[i]=itsMas[i+1];
itsMas[i+1]=temp;
k=i;
exch++;
}
}
rb=k;

for(int i=rb;i>lb;i--)
{
num_of_equal++;
if(itsMas[i]<itsMas[i-1])
{
temp=itsMas[i];
itsMas[i]=itsMas[i-1];
itsMas[i-1]=temp;
k=i;
exch++;
}
}
lb=k;
}

cout << "\nК-во обменов " <<exch <<", к-во сравнений " <<num_of_equal <<endl;
}
« Последнее редактирование: ПЭТРам 28, 2009, 03:55:00 pm от Alex_cs_gsp »
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн Inf-root

  • Глобальный модератор
  • Коллежский советник
  • *****
  • Сообщений: 571
  • Репутация: 21
  • Пол: Мужской
Re: Истинная Шейкерная сортировка
« Ответ #3 : ПЭТРам 28, 2009, 05:26:07 pm »
Ну математически это к Кнуту :)
В старости нет лучшего утешения,
чем сознание того, что все силы в
молодости отданы делу, которое не
стареет.
(с) Артур Шопенгауэр (немецкий философ)

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Истинная Шейкерная сортировка
« Ответ #4 : ПЭТРам 28, 2009, 09:04:16 pm »
Такой математики не учили...
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн Inf-root

  • Глобальный модератор
  • Коллежский советник
  • *****
  • Сообщений: 571
  • Репутация: 21
  • Пол: Мужской
Re: Истинная Шейкерная сортировка
« Ответ #5 : ПЭТРам 28, 2009, 09:25:50 pm »
Вообще-то я имел ввиду Дональд Кнут. Искусство программирования
В старости нет лучшего утешения,
чем сознание того, что все силы в
молодости отданы делу, которое не
стареет.
(с) Артур Шопенгауэр (немецкий философ)

Оффлайн Адамантэус

  • Коллежский советник
  • *****
  • Сообщений: 725
  • Репутация: 24
  • Пол: Мужской
  • Телезритель
Re: Истинная Шейкерная сортировка
« Ответ #6 : ПЭТРам 30, 2009, 01:40:20 pm »
Не знаю как выкладки у Кнута, но протестировав реализацию своей программой могу констатировть, что она просто не работает. А эффективность приведённой здесь http://ermak.cs.nstu.ru/cprog/book2001/25-02.htm#def45  просто равна пузырьковой, Простая вставка и "Быстрая" сортировка - содержат алгоритмическую ошибку :
Код: (C) [Выделить]
//Истинная Шейкерная сортировка
void ShellSort (dat& array) {
int i, k = 0;
int lb = 0, rb = array.cnt() - 1;

while(lb < rb)
{
for(i = lb; i < rb; i++)
{
if(array.comp(i, i + 1) > 0)
{
datswap(array, i, i + 1);
k = i;
}
}
rb = k;

for(i = rb; i > lb; i--)
if(array.comp(i, i + 1) < 0)
{
datswap(array, i, i - 1);
k = i;
}
lb = k;
}
};

//------ Однонаправленная Шейкер-сортировка
void ShellSort1 (dat& array) {
 int i, b, b1; // b граница отсортированной части
 for (b = array.cnt() - 1; b != 0; b = b1) { // Пока граница не сместится к правому краю
b1 = 0; // b1 место последней перестановки
for (i = 0; i<b; i++) // Просмотр массива
if (array.comp(i, i + 1) > 0) { // Перестановка с запоминанием места
datswap(array, i, i + 1);
b1 = i;
}
 }
}
« Последнее редактирование: ДХТаРЫм 04, 2009, 05:22:59 pm от Адамантэус »

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Истинная Шейкерная сортировка
« Ответ #7 : ПЭТРам 30, 2009, 03:27:54 pm »
Цитировать
Не знаю как выкладки у Кнута, но протестировав реализацию своей программой могу констатировть, что она просто не работает. А эффективность приведённой здесь http://ermak.cs.nstu.ru/cprog/book2001/25-02.htm#def45  просто равна пузырьковой :

Может там и равна, но вообще нет.

Пузырь                         Шейкер
1 5 7 2 3 6 9 11 4          1 5 7 2 3 6 9 11 4
1 5 2 3 6 7 9 4 11          1 5 2 3 6 7 9 4 11
1 2 3 5 6 4 7 9 11          1 2 5 3 4 6 7 9 11
1 2 3 5 4 6 7 9 11          1 2 3 4 5 6 7 9 11
1 2 3 4 5 6 7 9 11

обменов 10,                  обменов10,
сравнений 33                сравн 21

(если в другую
сторону то сравне
ний 30)

К-во сравнений не очевидно, зависит от к-ва (вероятности) подряд идущих элементов.
Скоро я выложу програмку с наиболее известными алгоритмами сортировки, где показан каждый шаг, к-во сравнений и обменов.
« Последнее редактирование: ПЭТРам 30, 2009, 10:16:52 pm от Alex_cs_gsp »
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн Адамантэус

  • Коллежский советник
  • *****
  • Сообщений: 725
  • Репутация: 24
  • Пол: Мужской
  • Телезритель
Re: Истинная Шейкерная сортировка
« Ответ #8 : ПЭТРам 31, 2009, 01:02:23 pm »
 Выкладывай, как я понимаю это будет аналог моей, по такому случаю даже навёл в ней марафет - так что учти что всё проверю, а то в рунете похоже полный завал с сортировками  :fool:
« Последнее редактирование: ПЭТРам 31, 2009, 01:40:33 pm от Адамантэус »

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Истинная Шейкерная сортировка
« Ответ #9 : ДХТаРЫм 02, 2009, 11:43:05 pm »
Вот доработанная версия, на пирамидальную не хватило сил, а так вроде все основные.
« Последнее редактирование: ДХТаРЫм 04, 2009, 07:36:47 pm от Alex_cs_gsp »
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн Адамантэус

  • Коллежский советник
  • *****
  • Сообщений: 725
  • Репутация: 24
  • Пол: Мужской
  • Телезритель
Re: Истинная Шейкерная сортировка
« Ответ #10 : ДХТаРЫм 04, 2009, 04:27:37 pm »
  :good: В общем есть результаты, но относительно моей программы :
 Пузырьковая производит на 5.3 % больше операций сравнения
 Шейкеровская производит на 28.3 % меньше операций сравнения и на 4.4 % быстрее чем у меня пузырьковая
 SelectSort показала наилучние результаты, быстрее однородной у меня на 13%
 Простая вставка и Вставка погружением одинаковые
 Первая сортировка всплыванием 64% мендленне чем аналогичная у меня
 Вторая сортировка всплыванием 13% мендленне чем аналогичная у меня
 Рекурсивным разделением на 14% мендленне чем аналогичная у меня

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Истинная Шейкерная сортировка
« Ответ #11 : ДХТаРЫм 04, 2009, 07:23:02 pm »
Да где-то так оно возможно и есть.
Цитировать
Первая сортировка всплыванием 64% мендленне чем аналогичная у меня
 Вторая сортировка всплыванием 13% мендленне чем аналогичная у меня
 Рекурсивным разделением на 14% мендленне чем аналогичная у меня
Неплохо бы на код посмотреть (намек).

Странно относительно быстрой сортировки, она у меня намного хуже Шелла. Как написать нерекурсивную версию я не додумался, а везде где видял, там целая куча операторов goto, и ничего непонятно. Наверно сделаю себе шаблончик Шелловской и буду использовать ее.
« Последнее редактирование: ДХТаРЫм 05, 2009, 12:33:15 am от Alex_cs_gsp »
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн Inf-root

  • Глобальный модератор
  • Коллежский советник
  • *****
  • Сообщений: 571
  • Репутация: 21
  • Пол: Мужской
Re: Истинная Шейкерная сортировка
« Ответ #12 : ДХТаРЫм 04, 2009, 10:21:40 pm »
Цитировать
Только странно относительно быстрой сортировки, она у меня намного хуже Шелла.

Да ну! Не верю. Выкладывай код.
В старости нет лучшего утешения,
чем сознание того, что все силы в
молодости отданы делу, которое не
стареет.
(с) Артур Шопенгауэр (немецкий философ)

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Истинная Шейкерная сортировка
« Ответ #13 : ДХТаРЫм 05, 2009, 12:29:20 am »
Код в последнем архиве Sorty.rar
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн Inf-root

  • Глобальный модератор
  • Коллежский советник
  • *****
  • Сообщений: 571
  • Репутация: 21
  • Пол: Мужской
Re: Истинная Шейкерная сортировка
« Ответ #14 : ДХТаРЫм 05, 2009, 06:20:10 am »
Ну вот что у меня получилось. Для запуска нужен .Net Framework 2.0
В старости нет лучшего утешения,
чем сознание того, что все силы в
молодости отданы делу, которое не
стареет.
(с) Артур Шопенгауэр (немецкий философ)