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

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

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Истинная Шейкерная сортировка
« Ответ #15 : ДХТаРЫм 05, 2009, 08:13:59 am »
Цитировать
Для запуска нужен .Net Framework 2.0
Для консоли уже нужен Net Framework 2.0??

Я говорил что у меня не Шейкерная сортировка получилась быстрее Быстрой, а сортировка Шелла.
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн Inf-root

  • Глобальный модератор
  • Коллежский советник
  • *****
  • Сообщений: 571
  • Репутация: 21
  • Пол: Мужской
Re: Истинная Шейкерная сортировка
« Ответ #16 : ДХТаРЫм 05, 2009, 11:00:26 am »
Цитировать
Для консоли уже нужен Net Framework 2.0??
Ээээ... Ну Net Framework это не только WinForms и WPF.

Цитировать
Я говорил что у меня не Шейкерная сортировка получилась быстрее Быстрой, а сортировка Шелла.
   
Что-то я тупанул.
В старости нет лучшего утешения,
чем сознание того, что все силы в
молодости отданы делу, которое не
стареет.
(с) Артур Шопенгауэр (немецкий философ)

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

  • Коллежский советник
  • *****
  • Сообщений: 725
  • Репутация: 24
  • Пол: Мужской
  • Телезритель
Re: Истинная Шейкерная сортировка
« Ответ #17 : ДХТаРЫм 05, 2009, 03:39:15 pm »
Код в последнем архиве SortDemo.zip

Оффлайн Inf-root

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

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

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Истинная Шейкерная сортировка
« Ответ #19 : ДХТаРЫм 05, 2009, 09:45:58 pm »
Цитировать
Ну вот что у меня получилось. Для запуска нужен .Net Framework 2.0

Для массива 25;24;23;22;21;20;19;18;17;16;15;14;13;12;11;10;9;8;7;6;5;4;3;2;1; у меня на шейкере результаты такие-же (хотя эта сортировка должна проверяться для среднего случая - только так можно найти ошибку, на чем я собственно и попался). А быстрая сортировка у меня 12 обменов, 74 сравнения. Шелла 40 обменов, 41 сравнение, вот так.
Либо у меня кривой алгоритм, либо есть другой алгоритм, либо я не правильно подсчитываю обмены и сравнения, или у быстрой сортировки просто авторитет но не более, или все вместе.
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн Inf-root

  • Глобальный модератор
  • Коллежский советник
  • *****
  • Сообщений: 571
  • Репутация: 21
  • Пол: Мужской
Re: Истинная Шейкерная сортировка
« Ответ #20 : ДХТаРЫм 05, 2009, 09:54:46 pm »
Блин. Классическая быстрая сортировка плохо себя ведет на упорядоченных данных. Есть еще улучшенная быстрая сортировка, которое это дело поправляет. Но не совсем. Я выложил классический. Сравнений 300 перестановок 12.

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

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Истинная Шейкерная сортировка
« Ответ #21 : ДХТаРЫм 05, 2009, 11:48:16 pm »
Цитировать
Блин. Классическая быстрая сортировка плохо себя ведет на упорядоченных данных. Есть еще улучшенная быстрая сортировка, которое это дело поправляет. Но не совсем. Я выложил классический. Сравнений 300 перестановок 12.
-А, я понял. Ты берешь в качестве компаранда первый элемент.
            А надпись, мне просто понравилась прога Адаментэуса.
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн Inf-root

  • Глобальный модератор
  • Коллежский советник
  • *****
  • Сообщений: 571
  • Репутация: 21
  • Пол: Мужской
Re: Истинная Шейкерная сортировка
« Ответ #22 : ДХТаРЫм 06, 2009, 08:18:15 am »
Цитировать
-А, я понял. Ты берешь в качестве компаранда первый элемент.
Именно, а потом стягиваю концы в зависимости была перестановка или нет. Код на шарпе, но думаю после плюсов с легкостью поймешь
//Метод рекурсивной быстрой сортировки
protected void RecFunc(int left, int right)
{

if(left>=right)
return;
int lp=left,rp=right;
int mode = 1;
while(lp<rp)
{
QuickRecSort._CompareCnt++;
if(_Array[lp]>_Array[rp])
{
QuickRecSort._SwapCnt++;
int tmp = _Array[lp];
_Array[lp] = _Array[rp];
_Array[rp] = tmp;
mode=-mode;
}
if(mode>0)  rp--; else lp++;
}
RecFunc(left,lp-1);
RecFunc(lp+1,right);
}
В старости нет лучшего утешения,
чем сознание того, что все силы в
молодости отданы делу, которое не
стареет.
(с) Артур Шопенгауэр (немецкий философ)

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Истинная Шейкерная сортировка
« Ответ #23 : °ЯаХЫм 07, 2009, 11:02:29 pm »
У меня в  подсчете количества сравнений, для сортировке вставками, допущена ашипка  :fool:

Если подсчитывать количество сравнений (num_of_equal) в условии цикла, следующим образом

for(j=i-1 ; ++num_of_equal && j>=0 && temp<itsMas[j] ; j--)
то вроде все хорошо, но если написать,

for(j=i-1 ; j>=0 && temp<itsMas[j] && ++num_of_equal ; j--)
то, если ложь в первом условии, то нет смысла проверять остальные, и добрая половина сравнений не учитывается.
« Последнее редактирование: °ЯаХЫм 27, 2009, 03:57:19 pm от Alex_cs_gsp »
Когда вы с собой разговариваете, вы получаете информацию?