Криса, как алгоритмизатора я уважаю не слишком...
sorry за offtop.. я вот думаю.. а чего это он в статье про пакеры себя автором написал? может и здесь так?

а чего это он в статье про пакеры себя автором написал?

В какой статье?

volodya
У Криса в книге приводится диаграмма сравнения быстрой и линейной сортировки. Так вот на 2 000 000 ( а именно такие объемы в моей задаче, причем в цикле ) чисел линейная сортировка в 250 раз быстрее.!!!
А вообще мне надо приспособить все это дело под float( пока обхожусь qsort), но как это сделать без выделения гигантского объема памяти не соображу.

чисел линейная сортировка в 250 раз быстрее

Не всему, что пишут стоит верить.
Ты меня смутил. Сейчас смотрю Кнута...
А по этому поводу что скажешь:
http://www.ee.technion.ac.il/courses/044268/lectures/06_LinearSort.pdf

Кроме того, опять путаница в терминах.
Упоминают:

Линейная сортировка(сортировка отбором).

Идея линейной сортировки заключается в том, чтобы , последовательно просматривая весь массив, отыскать наибольшее число и поместить его на первую позицию, обменяв его с элементом, который ранее занимал первую позицию. Затем просматриваются все остальные элементы массива и выполняется аналогичная операция по отбору из рассматриваемой части массива максимального элемента и обмену местами этого элемента и первого в рассматриваемой части и т.д.


Так это что - сортировка выбором? Если да - так она медленне пузырька и время неустойчиво... Словом, пните меня, я окончательно запутался :(((

volodya
т.е., в худшем случае это O(n*2)?
AFAIK, O(n*2) тоже считается O(n).

HeDiN
Линейная сортировка быстрее только если среди сортируемых элементов очень много повторяющихся. А то что у Криса линейная сортировка оказалась в 250 раз быстрее означает лишь что он сортировал word'ы, которые могут иметь всего 65536 различных значений. Вообще у Кнута она называется "сортировка подсчетом".
volodya
Пнуть нужно тех кто ее так назвал и не сказал почему. Комичество обменов в ней действительно линейно зависит от числа элементов, но вот сравнений n^2/2. Если обмен более дорогая операция чем сравнение, то эта сортировка будет быстрее пузырьковой.

volodya
Ну сами же линк даванли. Которую он у f0dder'а "перевел".

Извиняюсь что врезаюсь по середине, но...
LinearSort есть не что иное как BucketSort, который
в свою очередь проходит эволюцию и преврощяетса
в RadixSort.
Все три вида базируютса на одном веселом принципе
который катет очен круто с целыми числами. Но как
только нецелые числа входят в игру всё очен усложняетса.
Имплементациа становитса очен (дажэ слишком) сложной.

Насчёт того что алгоритм эфективен только когда числа
повторяютса то эта не совсем правильно. Он эфективен когда
значения находятса в определёном диапазоне.

А вот насчёт пузырьков. Хммм.... Что можэт быть медленей пузырька? :)

Мой совет будет оставатса с надёжным QuickSort-ом, или реализовать
более сложный HeapSort (который можэт сработает быстрей).
Если найдутса силы реализовать RadixSort с нецелыми, будет
очень интересно взглянут на это дело.

HeDiN
описывается очень "соблазнительный" алгоритм

Каспер ГОНИТ... :)

Мои собственные эксперименты показали как раз обратный результат...
В отличие от всех остальных замеров в этой книге, здесь отсутствуют
всякие упоминания об использованной реализации quicksort...
Так что очень вероятно, что 250 - высосано из пальца :)
Скорее всего, он написал этот отрывок чтобы "попонтоваться":
"этот велосипед я изобрел еще в школе"... :))

Quantum
AFAIK, O(n*2) тоже считается O(n).

Это volodya так обозначает N в квадрате.
И это подвело его в другом топике... :)

Black_mirror
означает лишь что он сортировал word'ы

вот-вот. отсутствие описания условий тестирования означает,
что результат был известен заранее :)

Вообще у Кнута она называется "сортировка подсчетом"

У Кнута так называется квадратичный алгоритм
подсчета числа меньших ключей...

merlin
Что можэт быть медленей пузырька? :)

Может кое-что... :)
У Кнута описан кубический алгоритм, для которого
самая короткая программа (оптимизация по размеру, однако :)

А еще есть т.н. StoogeSort.
Это рекурсивный алгоритм. Идея проста.
Если число сортируемых элементов больше двух, то отсортировать:
сначала первые 2/3 массива, потом вторые 2/3, и снова первые 2/3.
Алгоритм очень похож на quicksort, только делает три рекурсивных вызова.
Зато за счет того что разбиение делается таким образом,
глубина рекурсивных вызовов заведомо ограничена логарифмом от N.

Наверное, Крис воспользовался штатной функцией qsort из "stdlib.h".
А вообще среди участников форума пробегала инфа, что кто-то имеет контакты с Крисом. Может спросить у самого автора?

Мои 2 копейки: :)

"Сортировка подсчетом" я пользоваль для сортировки байтов и от действительно работает очень быстро. И написать его на ассемблере достаточно просто. Например можно подумать изпользовать его для сортировки текста... (но ето я не делал)
А вот и мoя реализация quicksort-а из дистрибуции Fresh. Он написан чтобы сортировать произвольные статические масивы:

_854035926__qsort.rar

@captain_cobalt
Было бы интересно посмотреть на этот кубический
алгоритм. Ведь то пузирьки занимают всего несколько
строк в С (что можэт быть короче?).

А этот StoogeSort это специализированый случай Quick-а,
что доказывает что быстрее чем O(n*logn) он работать не сможэт,
вообщем как и любой другой "сравнивающий" алгоритм, но
помедленей сможэт! Полное доказателство можно увидет на
линке который дал Володя.

Чтобы преодолеть баръер O(n*logn) нужно использовать
"несравнивающий" алгоритм, типа Radix-a, который начинает
жирать память (и не всегда применим), но зато скорость достигает O(n).

merlin
Было бы интересно посмотреть на этот кубический
алгоритм. Ведь то пузирьки занимают всего несколько
строк в С (что можэт быть короче?).

Алгоритм такой:

	->x

Начинаем в начале массива.
Сравниваем два соседних элемента.
Если по порядку - продвигаемся на один элемент вперед.
Иначе меняем их местами и сдвигаемся на шаг назад.
Повторяем пока не доберемся до конца массива.

Весит 8 команд MIX-ового ассемблера...

А этот StoogeSort это специализированый случай Quick-а...

Рекомендую помедитировать над ним,
если не понятно в чем прикол :)))

HeDiN
сортировки... 2 000 000 ( а именно такие объемы в моей задаче, причем в цикле )

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

То есть реализовать HeapSort. :)

HeDiN

Крис в нашей группе. Разумеется, я могу у него спросить все, что посчитаю нужным.

S_T_A_S_

Ох, ты прав. Кстати, меня на "ты", а не на "вы". Извини.

captain cobalt
Black_mirror
merlin

Спасибо!