Blog. Just Blog

Сортировка массива строк на Ассемблере

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
Долго откладывал написание этой функции, но теперь вот прижало. Получилась функция сортировки массива произвольных текстовых строк в формате ASCIIZ усовершенствованным методом "пузырька". Усовершенствование заключается в том, что если при очередном проходе ни одной сортировки не было выполнено, то дальнейшая обработка массива прекращается. В некоторых случаях это дает значительный выигрыш в скорости работы. Однако, алгоритм сортировки "пузырьком" в любом случае является самым медленным, поэтому для очень больших массивов эта функция не подойдет. Но мне для больших объемов ее и не надо, на массиве из нескольких сотен или даже тысяч строк скорость работы функции меня вполне устраивает.
  1. ;------------------------------------------------------------------
  2. ; Функция сортировки массива строк
  3. ; by ManHunter / PCL
  4. ; http://www.manhunter.ru
  5. ;
  6. ; Сортировка выполняется усовершенствованным методом "пузырька"
  7. ; Параметры:
  8. ; lpArray - указатель на массив адресов строк
  9. ; dFlag   - метод сортировки: TRUE - по возрастанию,
  10. ;           FALSE - по убыванию
  11. ; На выходе:
  12. ; отсортированный согласно правилу массив адресов строк
  13. ;------------------------------------------------------------------
  14. proc    SortArray lpArray:dword, dFlag:dword
  15.         pusha
  16.  
  17.         ; Указатель на массив адресов строк
  18.         mov     esi,[lpArray]
  19.  
  20.         mov     ebx,[dFlag]
  21. sa_sort_1:
  22.         ; Проверка на 0 - признак окончания массива
  23.         mov     eax,[esi]
  24.         or      eax,eax
  25.         jz      sa_stop_sort
  26.  
  27.         or      bh,bh
  28.         jnz     sa_stop_sort
  29.  
  30.         ; Сравниваем, начиная со следующего элемента
  31.         lea     edi,[esi+4]
  32.  
  33.         ; Установить флаг, что сортировка не требуется,
  34.         ; если дальнейший остаток массива уже отсортирован
  35.         mov     bh,1
  36. sa_sort_2:
  37.         ; Следующий элемент 0 - массив закончился
  38.         mov     edx,[edi]
  39.         or      edx,edx
  40.         jz      sa_next_sort
  41.  
  42.         ; Сохранить текущие значения указателей
  43.         push    esi edi
  44.  
  45.         ; Указатели на строки
  46.         mov     esi,eax
  47.         mov     edi,edx
  48. sa_compare_string:
  49.         ; Сравнить символы в строках
  50.         mov     cl,byte [edi]
  51.         mov     ch,byte [esi]
  52.         ; Если символы равны, то сравнить следующие
  53.         cmp     cl,ch
  54.         je      sa_equal
  55.  
  56.         ; Проверка больше-меньше в зависимости от флага
  57.         cmp     bl,0
  58.         jz      @f
  59.  
  60.         cmp     cl,ch
  61.         ja      ss_next_string
  62.         jmp     sa_change_offs
  63. @@:
  64.         cmp     cl,ch
  65.         jb      ss_next_string
  66.  
  67. sa_change_offs:
  68.         ; Поменять местами адреса строк
  69.         xchg    eax,edx
  70.         ; Сбросить флаг, что сортировка не требуется
  71.         xor     bh,bh
  72.         jmp     ss_next_string
  73.  
  74. sa_equal:
  75.         ; Если закончилась строка, то перейти к следующей паре
  76.         or      cl,cl
  77.         jz      ss_next_string
  78.  
  79.         ; Перейти к следующей паре символов
  80.         inc     esi
  81.         inc     edi
  82.         jmp     sa_compare_string
  83.  
  84. ss_next_string:
  85.         ; Восстановить значения указателей и записать в них
  86.         ; значения адресов строк, без разницы изменившихся или нет
  87.         pop     edi esi
  88.         mov     [esi],eax
  89.         mov     [edi],edx
  90.  
  91.         ; Перейти к следующему элементу массива
  92.         add     edi,4
  93.         jmp     sa_sort_2
  94.  
  95. sa_next_sort:
  96.         ; Перейти к следующему элементу массива
  97.         add     esi,4
  98.         jmp     sa_sort_1
  99.  
  100. sa_stop_sort:
  101.         popa
  102.         ret
  103. endp
Сортировать сами строки в памяти слишком нерационально, поэтому для сортировки нам понадобится массив DWORD'ов с указателями на строки. Параметр lpArray - указатель на такой массив. Признак окончания массива - DWORD с нулевым значением. Параметр dFlag определяет в каком порядке будет отсортирован массив: по возрастанию (значение TRUE) или по убыванию (значение FALSE). На выходе получаем отсортированный массив указателей.

В приложении два примера использования функции SortArray. Первый обрабатывает несколько предустановленных значений. Второй написан для оценки скорости работы функции сортировки, он генерирует 10000 случайных строк и затем их упорядочивает.

Примеры программ с исходными текстами (FASM)Примеры программ с исходными текстами (FASM)

SortArray.Demo.zip (7,695 bytes)


Поделиться ссылкой ВКонтакте Поделиться ссылкой на Facebook Поделиться ссылкой на LiveJournal Поделиться ссылкой в Мой Круг Добавить в Мой мир Добавить на ЛиРу (Liveinternet) Добавить в закладки Memori Добавить в закладки Google
Просмотров: 15027 | Комментариев: 7

Внимание! Статья опубликована больше года назад, информация могла устареть!

Комментарии

Отзывы посетителей сайта о статье
ManHunter (14.12.2011 в 11:30):
Я очень сомневаюсь, что у меня возникнет желание нахаляву решать чьи-то лабораторные работы. Есть фриланс, есть wasm.ru, там за денежку все напишут.
Роман (13.12.2011 в 21:38):
Я имел ввиду dos(tasm)уважаемый ManHunter,в чем отличие кода что на что поменять, огромная просьба  пояснить.
ManHunter (12.12.2011 в 21:24):
В алгоритме разницы никакой, что под DOS, что под винду. Отличие будет только в выводе результатов.
Роман (12.12.2011 в 18:41):
А где можно взять такую же только для dos?(очень надо)
Тарас (07.12.2011 в 03:34):
спасибо...
абдула (15.11.2011 в 22:19):
огромное спасибо автору
Корвус (26.05.2009 в 19:46):
спасибо, помогло. Сильно помогло.

Добавить комментарий

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2018
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.08 сек. / MySQL: 2 (0.0047 сек.) / Память: 4.75 Mb
Наверх