Сортировка массива чисел размерностью 32 байта

САБЖ
Есть массив в 100 тыс. чисел, размер которых 32 байта
Числа могут повторяться
Все числа в массиве нужно отсортировать по возрастанию (без учета знака)

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

Но алгос вышел очень медленный. Бинарник знакомого (в руки бинарь мне не попадал, иначе бы прореверсил давно. Наблюдал за его работой в гостях) справляется с задачей в несколько раз шустрее.

Вопрос:
Какой алгоритм посоветуете, и целесообразно ли в данном случае заюзать ММХ, SSE или еще что.

В общем, жду советов, как можно ускорить сортировку.

ЗЫ: код не привожу, поскольку используется классический пузырьковый алгоритм.

 

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

 

http://kolibrios.org/?p=SVN&kind=file&loc=/programs/fs/kfar/trunk/sort.inc - это heapsort на FASMе. Для сортировки по возрастанию замени все "call ebx" на "cmp esi,edi" (либо передавай в ebx указатель на функцию "cmp esi,edi/ret")

 

Magnum
Здесь реализация на MASM (на FASM и NASM переписать не сложно) сортировок: пузырьковой, шейкером, пирамидальной, прямым включением, прямым выбором, Шелла, Хоара (быстрая сортировка) на примере одного и того же массива двойных слов

 

Вопрос в тему: что быстрее, qsort или цифровая сортировка? Асимптотически, понятно, вторая быстрее, но моя реализация цифровой сортировки работала довольно медленно. Обгонит ли при хорошей реализации цифровая сортировка qsort?

 

как ты себе представляеш цифровую сортировку для 32байтных чисел(если конечно ты о этом http://en.wikipedia.org/wiki/Pigeonhole_sort)?

 

Нет, сортировка подсчётом и цифровая сортировка - совсем разные вещи
Как ни удивительно, но http://ru.wikipedia.org/wiki/Цифровая_сортировка

 

когда нужна сортировка больших массивов ничего лучше двоичной кучи не найдёшь.

 

Сортировка корзинами, а внутри каждой корзины qsort не подойдет?

 

метод сортировки зависит от объёма массива и в меньшей степени от объёма оперативной памяти.

 

Данная тема заставила меня вспомнить алго, в котором для сортировки 32 битных чисел выделяется массив в 4 ГБ. В каждый байт этого массива записывается число вхождений (ясно что более 255 одинаковых чисел в сортируемом массиве не должно быть =)
Наверное это самый быстрый метод сортировки, но вот память ....

ЗЫ. Алго этот какойто чел на олимпиаде придумал. Уж и не помню где это читал.

 

T800
4Гб - для 32х-битных неповторяющихся чисел.
Реализовал qsort
Заюзал MMX
Теперь скорость приемлимая.
Всем спс за советы.

 

T800
Это сортировка подсчетом для 32х битных числел. А ТС нужна сортировка 32х байтных. А это уже 32ГБ.

 

T800

да, это самая быстрая сортировка - сложность O(n), но, по понятным причинам, практическе неприменима.

 

UbIvItS
Можно было найти минимальное и максимальное 32-битное число и тогда уже для поиска числа вхождений отводятся cовсем не 4 ГБ

 

Mikl__
точней надо найти число с макс. кол-вом вхождений и потом делается расчёт нужной памяти.

 

А если числа распределены по всему доступному интервалу по некоему нормальному закону? Все-таки только быстрая сортировка даст детерминированное время сортировки. Все другие более хитрые алгоритмы полезну только на "своих" специфических данных.
n0name с самого начала был прав.

 

Xerx
все другие сортировки дают макс. сложность O(n*lg2(n)) и только одна даст O(n) на любом типе данных.

 

UbIvItS
Ты не прав по-мойму.
Для _любого_ типа данных лучшая сортировка может работать за O (N log N), так что в плане асимптотики qsort, heapsort и другие оптимальны.
А вот в частных случаях можно применять сортировку подсчётом, вычерпыванием, цифровую и др., которые будут работать за линейное время.
Поправьте меня, если я не прав

 

maxdiver
вот тебе сортировка:
count_arr;//кол-во элементов массива
for(i=0; i<count_arr; i++)array_els++;
лин. время на любом типе данных - только давай память) но из-за такой мелочи двоичная куча рулит)