(fasm) Подскажите алго сортировки unicode строк

выбор алго зависит от:
1. объёма начальных данных;
2. упорядоченности начальных данных;
3. частоты добавления и удаления строк;
4. методов добавления и удаления строк в контексте методов организации списка/массива в памяти.

 

wsd
Сортирую двойные слова
Пузырьковая

Код (Text):

1. .data
2. R dd n-1;количество неотсортированных элементов минус один
3. array  dd 10,450,320,120,180,600,50,230,340,460,550,500,130
4.       dd 80,390,410,20,800,670,60,730,610,310,0,360,200
5. n = ($-array)/4
6. .code
7.     mov esi,offset array    ;позиционируемся на массив
8. a2: mov ecx,R  
9.     xor ebx,ebx     ;флаг – были/не были перестановки в проходе
10. a3: mov eax,[esi+ecx*4-4]   ;получаем значение очередного элемента   
11.     cmp [esi+ecx*4],eax ;сравниваем со значением соседнего элемента
12.     jnb a4  ;если больше или равен - идем к следующему элементу
13.     setna bl    ;была перестановка - взводим флаг
14.     xchg eax,[esi+ecx*4]    ;меняем значение элементов местами
15.     mov [esi+ecx*4-4],eax
16. a4: loop a3 ;двигаемся вверх до границы массива
17.     add esi,4   ;сдвигаем границу отсортированного массива
18.     dec ebx ;проверяем были ли перестановки
19.     jnz exit    ;если перестановок не было - заканчиваем сортировку
20.     dec R       ;уменьшаем количество неотсортированных элементов
21.     jnz a2;если есть еще неотсортированные элементы - начинаем новый проход
22. exit:

При упорядочении массива из n элементов произойдет в лучшем случае, если массив отсортирован — n-1 сравнений. В худшем случае, если массив отсортирован в обратном порядке — при сортировке произойдет n*(n-1)/2 сравнений. (для n=26 элементов лучший случай — 25, средний — 289, худший — 325)
Шейкер

Код (Text):

1. .data
2. H dd 0  ;верхняя граница неотсортированного массива
3. L dd n-1    ;нижняя граница неотсортированного массива
4. .code
5.     xor esi,esi     ;нижняя граница неотсортированного массива
6.     xor ebx,ebx     ;флаг - были/не были перестановки в проходе
7.     mov ecx,L;количество неотсортированных элементов снизу минус один
8. a4: inc esi
9.       call Compare_and_Swapping ;сравнение и обмен значений элементов
10.     loop a4             ;двигаемся вниз до границы массива
11.     dec ebx             ;проверяем были ли перестановки
12.     jnz exit        ;если перестановок не было - сортировка закончена
13.     dec L       ;уменьшаем количество неотсортированных элементов снизу
14.     jz exit ;достигли границы массива
15.     dec esi     ;esi=L
16.     mov ecx,esi
17.     sub ecx,H;количество неотсортированных элементов сверху минус один
18.     jecxz exit  ;если граница снизу равна границе сверху - выходим
19. a2: call Compare_Swapping       ;сравнение и обмен значений элементов
20.     dec esi
21.     loop a2             ;двигаемся вверх до границы массива
22.     dec ebx             ;проверяем были ли перестановки
23.     jnz exit    ;если перестановок не было - заканчиваем сортировку
24.     inc H   ;уменьшаем количество неотсортированных элементов сверху
25.     inc esi     ;esi=H
26.     mov ecx,L  
27.     sub ecx,esi ;если граница снизу больше, чем граница сверху – значит
28.     ja a4;есть еще неотсортированные элементы - начинаем новый проход
29. exit:   . . .
30. Compare_Swapping proc;сравнение и обмен значений соседних элементов
31.     mov eax,array[esi*4]    ;получаем значение очередного элемента
32.     cmp array[esi*4-4],eax  ;сравниваем его с соседним элементом
33.     jna a3  ;если меньше или равен - идем к следующему элементу
34.     seta bl ;если была перестановка - взводим флаг
35.     xchg eax,array[esi*4-4]     ;меняем значения элементов местами
36.     mov array[esi*4],eax
37. a3: ret
38. Compare_Swapping endp

n=26 элементов лучший случай — 25, средний — 259 (лучше пузырьковой сортировки на 20%), худший — 325
Пирамидальная

Код (Text):

1. .data
2. L dd n/2-1  ;левая граница неотсортированного массива
3. R dd n-1        ;правая граница неотсортированного массива
4. .code
5. ;массив преобразуется в отображение пирамиды – вызвать процедуру
6. ;down_heap n/2 раз для преобразования массива  в пирамиду
7. b0:     call down_heap
8.         dec L       ;while ( L > 0 ) L--;
9.         jnz short b0
10. ;собственно пирамидальная сортировка
11.        dec L        ;L=0
12.        dec R        ;R=n-2
13. b1:     mov edx,R   ;отправляем значение максимального
14.        mov eax,array    ;элемента в конец массива
15.         xchg eax,array[edx*4+4] ; array[0] <--> array[R];
16.         mov array,eax
17.         call down_heap   ;восстанавливаем пирамиду - на ее
18. ;вершине появляется новое максимальное значение      
19.         dec R       ;уменьшаем индекс последнего элемента
20.         jnz short b1    ;while ( R > 0 ) R--;
21. b2:     ...
22. ;-----------------------------------------------------
23. down_heap proc; процедура вставки элемента на свое место в пирамиду
24.         mov eax,L
25.         mov ebx,eax         ;i = L;
26.         shl eax,1           ;j = 2*L;
27.         mov esi,array[eax*2]    ;item = array[L];
28.         cmp eax,R   ;if( j<R && array[j] < array[j+1]) j++;
29.         jnb short a0
30.         mov edx,array[eax*4]
31.         cmp edx,array[eax*4+4]  ;array[j] < array[j+1] ?
32.         jnb short a0
33. ; условие j<R && array[j]<array[j+1] выполнилось
34.         inc eax             ;j++
35. a0:     cmp eax,R           ;while( j<=R && item < array[j])
36.         ja short a1
37.         mov edi,array[eax*4]
38.         cmp esi,edi     ;item < array[j] ?
39.         jnb short a1
40. ; условие j<=R && item < array[j] выполнилось
41.        mov array[ebx*4],edi ;array[i] = array[j];
42.         mov ebx,eax     ;i = j;                                    
43.         shl eax,1           ;j = 2*j;
44.         cmp eax,R
45.         jnb short a0;if( j<R && array[j] < array[j+1]) j++;
46.         mov edx,array[eax*4]
47.         cmp edx,array[eax*4+4]
48.         jnb short a0
49. ; условие j<R && array[j] < array[j+1] выполнилось
50.         inc eax         ;j++
51.        jmp short a0
52. a1:    mov array[ebx*4],esi ;array[i] = item;
53.         retn
54. down_heap endp

n=26 элементов средний случай— 109 (лучше пузырьковой сортировки почти в 3 раза)

 

сортировка прямым включением

Код (Text):

1. mov esi,4       ;i=1
2. a4: push esi
3. a3: mov eax,array[esi-4]
4.      cmp eax,array[esi]
5.     jb a2
6.     xchg eax,array[esi]
7.     sub esi,4   ;двигаемся к началу массива
8.     mov array[esi],eax
9.     jnz a3
10. a2: pop esi
11.      add esi,4       ;двигаемся к концу массива
12.     cmp esi,n*4     ;просмотрели весь массив?
13.     jb a4

n=26 элементов лучший случай — 25, средний — 172 (лучше пузырьковой сортировки на 40%), худший — 325
Алгоритм можно улучшить пользуясь тем, что готовая последовательность уже упорядочена. Место вставки нового элемента можно найти значительно быстрее, если применить бинарный поиск, исследовав сперва средний элемент упорядоченной последовательности и продолжая деление пополам, пока не будет найдено место вставки. Для n=26 элементов лучший случай — 25, средний и худший — 106 (лучше пузырьковой сортировки почти в 3 раза)

Код (Text):

1. mov ebx,1  ;ebx - граница неотсортированного массива
2. b1: mov edi,ebx
3.     mov edx,edi;edi индекс первого элемента отсортированного массива
4.     xor esi,esi;esi индекс последнего элемента отсортированного массива
5.     mov eax,array[ebx*4]
6.     cmp eax,array[ebx*4-4]
7.     jnb b2
8. b6: cmp esi,edi        ;проверка esi>edi на завершение поиска
9.     jg b5    ;проверены все элементы, вставляем новый элемент
10.     shr edx,1 ;индекс центрального элемента равен (edi+esi)/2
11.     cmp array[edx*4],eax;сравниваем с искомым значением
12.     ja b3               ;array[edx*4]<eax
13.     jz b5               ;array[edx*4]=eax
14.      inc edx        ;учтем только что проверенное значение
15.     mov esi,edx ;изменяем нижнюю границу поиска
16.     add edx,edi ;создаем индекс центрального элемента
17.     jmp short b6    ;переходим к следующему элементу
18. b3: dec edx     ;учтем только что проверенное значение
19.     mov edi,edx ;изменяем верхнюю границу поиска
20.     add edx,esi ;создаем индекс центрального элемента
21.     jmp b6      ;переходим к следующему элементу
22. b5: mov ecx,ebx    ;сдвигаем отсортированные элементы, чтобы
23.     sub ecx,esi    ;освободить место для нового элемента
24.     shl esi,2; esi=esi*4
25.     push eax
26. b7: mov eax,array[esi+ecx*4-4];сдвиг отсортированных элементов
27.     mov array[esi+ecx*4],eax
28.     loop b7
29.     pop eax
30.     mov array[esi],eax;вставляем новый элемент
31. b2:  inc ebx
32.     cmp ebx,n
33.     jb b1

сортировка прямым выбором
На массиве из n элементов время выполнения в худшем, среднем и лучшем случае n*(n-1)/2

Код (Text):

1. mov edi,offset array    ;edi = указатель на массив
2.     mov ecx,N           ;ecx = количество элементов
3. a0: lea ebx,[edi+ecx*4] ;ebx = максимальный индекс в проходе+1
4.      mov eax,[edi]  ;eax=min=величина первого элемента в проходе
5. a1:     sub ebx,4       ;двигаемся по проходу вверх
6.      cmp eax,[ebx]
7.      jbe a2     ;min > array[ebx] ?
8.      xchg eax,[ebx] ;swap(array[ebx],min)
9. a2:     cmp ebx,edi
10.      jnz a1     ;проход закончился?
11.      stosd ;mov [edi],eax edi=+4 на первой позиции минимальный элемент
12.      loop a0

сортировка Шелла
Среднее время работы алгоритма зависит от длин промежутков, на которых будут находится сортируемые элементы исходного списка на каждом шаге алгоритма
при выборе последовательности значений d1=n/2, d2=d1/2,...,1 в худшем случае алгоритм выполнит O(n2) — сравнений 140
Table dd 32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1
все значения (3^j−1)/2 < n, такая последовательность шагов приводит к алгоритму класса O(n^(3/2)) — сравнений 108
Table dd 797161,265720,88573,29524,9841,3280,1093,364,121,40,13,4,1
последовательности вида N=2*N+1 — сравнений 118
Table dd 32767,16383,8191,4095,2047,1023,511,255,127,63,31,15,7,3,1
последовательность Дж.Инсерпи и Р.Седгевика — сравнений 115:
Table dd 198768,86961,33936,13776,4592,1968,861,336,112,48,21,7,3,1

Код (Text):

1. .data
2. Table dd 797161,265720,88573,29524,9841,3280,1093,364,121,40,13,4,1
3. .code
4. mov ecx,-14;в таблице приращений 13 элементов
5. entry: inc ecx
6. jz exit; если последний элемент в таблице - выход из программы
7. cmp [Table+ecx*4+13*4],n; ищем максимальное приращение (gap),
8. jge entry;соответствующее размеру нашего массива
9. a6: mov edx,[Table+ecx*4+13*4];получаем очередное приращение из таблицы
10. shl edx,2;выбрали интервал,у нас двойные слова,поэтому edx=edx*4
11. a2: mov ebx,edx;i=gap
12. a3: mov esi,ebx
13. sub esi,edx;j=i-gap
14. a4: mov eax,array[esi];for(i=gap;i<dim;i++)/*проход массива*/
15.     cmp eax,array[esi+edx];сравнение пар,отстоящих
16. jbe a5;на gap друг от друга
17. xchg eax,array[esi+edx];swap(a[j],a[j+gap])
18. mov array[esi],eax
19. sub esi,edx  ;j-=gap
20. jge a4
21. a5: add ebx,4    ;i++
22. cmp ebx,n*4  ;i < dim
23. jb a3        ;for(j=i-gap; j>=0 && a[j] > a[j+gap]
24. inc ecx
25. jnz a6
26. exit:

сортировка Хоара (быстрая сортировка)
Сортировка даёт в среднем O(n log n) сравнений

Код (Text):

1. push    offset array+n*4-4;указатель на последний элемент
2.         push    offset array;указатель на первый элемент массива
3.         call    quick_sort      ; quicksort (data, data+n-1)
4. ;-----------------------------------------------------
5. partition proc  Lb:dword,   Ub:dword
6. ; функция partition возвращает адрес pivot
7.         mov edx,Ub
8.        sub edx,eax           ;eax=Lb
9.        shr edx,3             ;(Ub-Lb)/2
10. ; После завершения этого цикла все значения слева от элемента pivot
11. ; будут меньше значения элемента pivot, а все значения справа от
12. ; элемента pivot будут больше, чем значение элемента pivot
13.         mov edi,[eax+edx*4]   ;получаем указатель на pivot
14. ;pivot = *(Lb+(Ub-Lb)/2)
15.         cmp eax,Ub       ;eax=Lb
16.         ja short b0          ;return Lb;
17. ; Поиск значения, большего чем pivot, в нижней части массива
18. b1:     mov eax,Lb     
19.         cmp [eax],edi       ;edi=pivot
20.         jnl short b3        ;while (*Lb < pivot)
21.        add Lb,4         ;Lb++;  
22.        jmp short b1
23. ; Поиск значения, меньшего чем pivot, в верхней части массива
24. b4:     sub Ub,4       
25. b3:     mov eax,Ub
26.         cmp [eax],edi       ;while (*Ub > pivot)
27.         jg short b4          ;Ub--
28.         mov ecx,Lb
29.        cmp ecx,eax           ;eax=Ub
30.         ja short b5           ;if(Lb <= Ub)
31.         sub Ub,4        ;swap( Lb++, Ub-- )
32.         add Lb,4       
33.         mov edx,[eax]       ;eax=Ub
34.         xchg edx,[ecx]      ;ecx=Lb
35.         mov [eax],edx       ;*Ub<-->*Lb;
36. b5:     mov eax,Lb
37.         cmp eax,Ub
38.         jbe short b1        ;while (*Lb < pivot)
39. b0:     pop ebp
40.         retn 8
41. partition endp
42. ;------------------------------------------------------------
43. quick_sort proc Lb:dword, Ub:dword
44.          mov eax,Lb
45.          cmp eax,Ub ; if (Lb >= Ub)
46.          jnb short exit1    ;сортировать нечего
47.          push Ub
48.          push eax       ;eax=Lb
49.          call partition  
50.         mov edi,eax     ;eax=pivot_ptr
51.          sub eax,4      ;pivot_ptr-1
52.          push eax
53.          push Lb    
54.          call quick_sort ;отсортируем то, что слева от pivot
55.          push Ub
56.          push edi       ;edi=pivot_ptr
57.          call quick_sort ; и то, что справа от pivot
58. exit1:   pop ebp
59.          retn 8
60. quick_sort endp

 

Mikl__
мне понравилось
t00x

3. Так добавлять то надо в нужное место ,а не куда пепел ляжет
Ведь сортируют не только для вывода но и для быстрой меткой вставки.

4.структура данных и определяет метод.
Слышал мельком Дядька КНУТ что супер интересную структуру в своих последних трудах
придумал, но всё ни как до него не доберусь

 

wsd
пункты 3. и 4. неразрывно связаны и зависят от пунктов 1. и 2.

P.S. а вообще, постановка задачи неполная.

 

nim
Немного подумав, а зачем собственно сортировать юникод-строки, возможно что ТС работает с каким-нибудь экзотическим словарем (русско-китайский, корейский, японский, хинди)? Тогда имеет смысл сортировать не сам словарь, после вставки/удаления каждого нового слова придется сортировать словарь заново, а сортировать ссылки на юникод строки, т.е создается структура вида: array[0], 21; array[21],10; array[31],15;... адрес юникод-строки и ее длина. При сортировке сортируются элементы этой структуры - а при выводе на экран сам словарь не трогается - выводятся элементы словаря согласно отсортированного списка. Если мое предположение правильное, то на экран из единственного словаря можно выводить рассортированные списки русско-китайский, китайско-русский, выборка по темам (только глаголы, только географические названия и т.п.). Новые словарные статьи добавляются в конец существующей базы, а при удалении словарных статей происходит удаление ссылки и ссылки пересортировываются...

 

сортировку лучше делать универсальной чтоб уж если сортировать то все что угодно а не только строки
для этого сортировщику помимо остального передаются функции сравнения и обмена местами

 

Все прекрасно, кроме реализации.

 

Сори за оффтоп.
Можно ли доработать ваши алгосы так, чтобы кроме самих строк учитывались и числа.
К примеру:

Код (Text):

1. hello world 2
2. hello world 1
3. hello world 10
4. hello world 20

-------------------------

Ваши методы после сортировки дают такой результат

Код (Text):

1. hello world 1
2. hello world 10
3. hello world 2
4. hello world 20

а это неправильно.

Как при сортировке учесть числа?

 

google natural sort algorithm