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

сабж

 

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

 

Я в гугле смотрел в первую очередь, кроме такихhttp://www.softpanorama.org/Bulletin/Contents/contents045.txt сайтов ничего больше не находит.

 

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

 

nim
В аттаче пример быстрой сортироки из MASM32

Адоптировать его к fasm и унистрингам думаю будет не сложнее
чем сделать Ваш вывод:

 

на основе функции lstrcmpiW, это можно, и достаточно просто, реальзовать!

 

Я делал так:

Код (Text):

1. A – адрес самой маленькая строка (в начале пустая) (строка меньше которой не добавляем)
2. B – найденная  маленькая строка
3. C – номер проверяемой строки
4. D – максимальное количество строк
5. E – массив в котором будут отсортированные строки
6. For i = 1 to d
7.     for C = 1 to d
8.     If  str (C) > A and str (C) < b then B = str (C) ;если строка на которую указывает С  больше минимальной строки и меньше найденной , тогда делаем её найденной
9.     Next C
10.     A=B     ;увеличиваем минимальный предел
11.     E (i) =  B      ;добавление в массив E номер элемента i строку B
12. Next i
13.  
14. В массиве E имеем отсортированные строки

 

в qsort в качестве функции сравнения подсовывай lstrcmpiW и не парь моск

 

Алгоритмов сортировки строк множество, и выбор алгоритма не зависит от кодировки текста. Другое дело - алгоритм сравнения строк, зависящий от кодировки:

UTF-8 (корректный!): рассматриваем строки, как массивы беззнаковых байтов; алгоритм сравнения очевиден;
UCS-2 / UCS-4 (aka UTF-32): массивы беззнаковых слов/двойных слов; если используется big-endian порядок байтов, то требуется обращение этого порядка (BSWAP r16/r32);
UTF-16 (то, что обычно и подразумевается под Юникодом): если используются только коды U+0000 - U+FFFF (без суррогатных пар), то алгоритм сравнения такой же, как и для UCS-2; если используются суррогатные пары (для представления кодов U+10000 и выше), то алгоритм сравнения уже сложнее; следуй совету KiNDeR и Noble Ghost.

 

Noble Ghost
разве lstrcmpiW __cdecl использует?

 

причем тут cdecl?
реализуешь функцию любой сортировки на любом языке, но чтобы в качестве параметра умела принимать функцию. и радуешься =)

 

про qsort() из CRT подумал

 

с сортировкой понятно, а вот как с алфавитом? если в строках будут символы, например, украинские или хотя бы "Ё" - как, интересно, lstrcmpiW себя поведет?

 

Для правильной сортировки с учётом языка нужно использовать CompareString или LCMapString.
Ещё рекомендую почитать вот эти посты:
http://blogs.msdn.com/michkap/archive/2005/05/08/415522.aspx
http://blogs.msdn.com/michkap/archive/2005/05/05/414845.aspx
http://blogs.msdn.com/michkap/archive/2005/06/24/432121.aspx

 

nim
1) Выбери максимально длинную строку, остальные строки до максимальной длины дополни нулями
2) сравнивай первые два байта (размер wchar) и сортируешь (хоть пузырьком) строки
3) если первый юникод-символ совпадает - сравниваем второй wchar и т.д.
если время критично - используй qsort, сортировку Шелла, пирамидальную сортировку, блочную сортировку

 

Mikl__
и кем его(страждуещещего) будут считать после пузырьковой??????
а 2 и 3 пункт реализованы в

 

wsd
наверное ТС хотел бы готовый сорц на фасме
Я предлагал стандартный путь разобратся с алгоритмом в порядке усложнения: 1) пузырковая 2) шейкерная 3) вставками 4) пирамидальная 5) Шелла 6) Хоора (quick) на примере байтового массива. Потом усложняем до сортировки слов. Далее доходим до сортировки юникод-строк. В конце концов, для вполне упорядоченного списка пузырьком сортируется за время почти O(n) - все дело в объеме сортируемого материала! Если сортировка носит вообще одноразовый характер, можно отсортировать в командной строке "sort unsort.txt > sort.txt" или копировать unicode-строки в Excell и сортировать там. А кем будут считать страждущего это его личное дело...

 

Mikl__

это Вы всё таки над ним постустались

это умный-модифик пузырька с флагом отсутствия замен
а клссический n*n

 

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

 

Mikl__
n*n это я для устрашения
и это кол-во сравнений
а ещё перестановок
3/4(n*n-n) средний
3/2(n*n-n) худший