Поразрядная сортировка....

del..

 

Ты чего это такой нервный - написал и сразу все стер? Я вот сейчас озадачен подобной сортировкой, буду делать через массив счетчиков и его "интегрирование". Вот сразу встает вопрос - как будем дробить числа - по битам, по байтам или по словам? Это зависит от длины массива... Вернее результат конечно не зависит, скорость будет разная...

 

по идее, по разрядности регистра надо.

 

16 гигов счетчиков - не слишком ли круто будет? =)))

Лучше всего делать по байтам.
Если размер массива много больше чем 65536 можно сделать по словам, будет в два раза быстрее чем по байтам (два прохода вместо 4-х).

 

persicum
а зачем счётчики7 опиши алгос, пожалуйста. вроде, и без них можно.

 

Да в собеседовании как-то слышал, кое где дают задание такое. Решил проверить за сколько минут по памяти могу написать. Получилось вроде прикольно. Потом подумал что может кто-нибудь ещё прикольнее сочинит (наверняка). Написал сюда. Интереса сильного к теме не заметил, поэтому стёр.... да и самому уже не особо интересно

 

Для озабоченых у меня в корзине исходник остался, который вот он =)) Сортирует массив 32 разрядных чисел. В идеале оптимизируется так, что цикл работает без ветвлений (то бишь команд перехода), но в прочем и так сойдёт:

Код (Text):

1. ;#define SIZE 100
2.  
3. include 'c:\Fasm\INCLUDE\WIN32AX.INC'
4.  
5. .data
6. size=100
7. array:  rw size
8.  
9. .code
10.  
11.  
12. start:
13.     call    init
14. ; сортировка
15.     xor ecx,ecx ; lay
16.     xor edx,edx ; mask
17.     stc
18. .0: rcr edx,1
19.     mov esi,array
20.     mov edi,esi
21. .1: mov eax,[esi]
22.     xor eax,ebx
23.     test    eax,ecx
24.     cmovnz  edi,esi
25.     mov eax,[esi]
26.     cmovnz  ebx,eax
27.     test    eax,edx
28.     jnz .2
29.     xchg    eax,[edi]
30.     mov [esi],eax
31.     add edi,4
32. .2: add esi,4
33.     cmp esi,array+size*4
34.     jc  .1
35.     stc
36.     rcr ecx,1
37.     jnc .0
38.  
39.     invoke  ExitProcess,0
40.  
41. ; загрузка случайных начальных данных
42. init:   mov ebx,1
43.     mov ecx,size
44.     mov edi,array
45. .1: mov eax,ebx
46.     add eax,edx
47.     ror eax,1
48.     mov edx,ebx
49.     mov ebx,eax
50.     stosd
51.     loop    .1
52.     ret
53.  
54. .end start

по скорости, У меня 2-3 секунды на 10 милионов чисел...

 

Ну думаю от размеров данных в ячейках. и от размеров массива. т.е. от рентабельности постройки массива счётчиков (зачем он нужен, если будет использоваться меньше чем на половину). Следовательно либо по битам, либо применять всё сразу. Старшние разряды какого-нибудь много-метрового массива дробить по словам, средние по байтам, далее по битам. Тут можно даже простую само-аптацию алгоритма делать. По статистике. К тому же не надо целиком менять ячейки в частично сортированном массива, только младшие половинки ячеек..

Короче говоря не алгоритм, а красивая сказка, наворотить можно много....

 

А вы все еще сортируете числа? Сортировка строк в стандартном алгоритме построения суффиксного массива гораздо интереснее...

 

Со стандартными алгоритмами в другую тему пожалста... =)

 

Зарелизил через байты...
При достаточной длине это конечно много быстрее будет чем по битам или QuickSort...
Впечатление портит только доп. массив размером с основной...
Что делать будем? Как расставить элементы без доп. масива?

Код (Text):

1. Procedure RadixSort(var S:Array of Cardinal; n:Cardinal);
2. var Curr:Cardinal; //байтовое поле
3.     CurrB:array [1..4] of byte absolute Curr;
4.     Count:array [0..255] of Cardinal; //массив счетчиков
5.     D:array of Cardinal; //вспомогательный массив размером с основной
6.     i,nb,c1,c2:Cardinal;
7. begin
8.   SetLength(D,n); //выделяем память
9.  
10.   for nb:=1 to 4 do begin //четыре прохода по числу байт
11.  
12.     for i:=0 to 255 do Count[i]:=0; //очистка счетчиков
13.  
14.     i:=0;
15.     while i<n do begin //заполнение счетчиков
16.       Curr:=S[i];
17.       inc(Count[CurrB[nb]]);
18.       inc(i);
19.     end;
20.  
21.     c1:=0; c2:=0;
22.     for i:=0 to 255 do begin //"интегрирование" счетчиков
23.       c2:=c2+c1;
24.       c1:=Count[i];
25.       Count[i]:=c2;
26.     end;
27.  
28.     i:=0;
29.     while i<n do begin //расстановка массива
30.       Curr:=S[i];
31.       D[Count[CurrB[nb]]]:=Curr;
32.       inc(Count[CurrB[nb]]);
33.       inc(i);
34.     end;
35.  
36.     i:=0;
37.     while i<n do begin //копирование частично упорядоченного массива
38.       S[i]:=D[i];
39.       inc(i);
40.     end;
41.  
42.   end;
43.  
44.   SetLength(D,0); //очистка вспомогательного массива
45. end;
46.  
47. var X:array of Cardinal; //пример сортировки
48. BEGIN
49.  Setlength(X,6);
50.  x[0]:=123456789;
51.  x[1]:=$FFFFFFFF;
52.  x[2]:=0;
53.  x[3]:=65536;
54.  x[4]:=65535;
55.  x[5]:=17;
56.  
57.  RadixSort(X,6);
58.  writeln(x[0]);
59.  writeln(x[1]);
60.  writeln(x[2]);
61.  writeln(x[3]);
62.  writeln(x[4]);
63.  writeln(x[5]);
64. END.

 

persicum
а почему бы бин. дерево не юзать7777 счётчики не нужны в итоге.

 

Дерево наверное хорошо, когда массивы становятся разрежеными (за чем можно следить в процессе работы).
А так вся прелесть истино линейного алгоритма теряется.

 

Код (Text):

1. а почему бы бин. дерево не юзать7777 счётчики не нужны в итоге.

Тятя, а что такое глобус... вернее дерево?
Точно не знаю, но наверное это структура которая содержит:
1) указатель на данные
2) указатель влево
3) указатель вправо
4) указатель назад...

Что-то шипко жирно будет иметь четыре 32-разрядных указателя на одно 32-целое без знака =)))
Экономии что-то не видно =)))
Не, не любитель я запускать в памяти таких змеев-глистов многоголовых...
Вот массивы - это по нашему, и поддерживаются на уровне ассемблера-процессора!!!
типа mov eax,[esi+ecx*4]

А 256 счетчиков много памяти не отожрут...

 

Заценил, доп.массива не нашел, рекурсии тоже не нашел...
Разве такое возможно для поразрядной сортировки? o:
В чем прикол и как развить эти идеи для байт?
Имхо байтовая должна в 8 раз быстрее работать для массивов заметно длиннее чем 256 элементов...

Код (Text):

1.  stc
2.  rcr    ecx,1
3.  jnc    .0

А это что за ковбойство и где такому учат?
почему нельзя loop или cmp ecx,32; [esi + ecx*4], что при этом теряем ?

 

Интересно. Можно в первом проходе по массиву создать 32 таблицы по 1му биту + 32 индексные таблицы, потом каждую отсортировать и потом из индексов восстановить отсортированную таблицу. Но памяти нужно немеряно!

 

ecx тут маска.. мне надо её заполнять... Притом, я дополнительно имею возможность не тратиться на счётчик....

 

А нельзя ли для сомневающихся вроде меня рассказать на словах, как это все работает.
Возможно, мне нужно по шагам пройти этот код и посмотреть, что и как он сортирует...
Как я уже сказал, у меня есть сомнения, что радикс-сорт с массивами возможна без доп массива.
Алгоритму нужна так называемая устойчивость, чтобы равные данные ни в коем случае не переставлять местами. Таких алгоритмов не много...
Если переставлять местами элементы с нулевым битом и с ненулевым, отгоняя одни в начало массива, а другие в конец, то возможно устойчивость теряется...

Насчет маски тоже не все понятно...
Получается накопление единиц 1111000 вместо одной 00001000000

 

Просто сортирует по битам, а не по байтам. А маска защищает числа с одинаковыми старшими битами от перемешивания. Сначала тоже по байтам хотел, но через пару шагов рассужедний бытро дошёл до другово кода. Надеюсь он достаточно понятный:

 

Да, спасибо, теперь все понятно.

n - опережающий индекс
m - запаздывающий индекс
mask - маска для выделения очередного бита
lay - маска для выделения старших разрядов.

Мда, круто получается, без доп памяти и рекурсии!!!
Кроме шуток, на Шнобеля тянет однозначно!

В сети я встречал только рекурсивную битовую сортировку, аналог QuickSort.

Есть у этой процедуры маленький косметический деффект - она частенько меняет элемент сам с собой, когда m=n... Некоторые реализации Swap на этом могут обламаться...

А всетаки, для 10 млн элементов вариант с 65536 счетчиками обещает в 16 раз быстрее быть...
Ну там, без учета попаданий в кеш и все такое...
Может побенчимся? =)))