Blog. Just Blog

Алгоритм быстрой сортировки на Ассемблере

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
Алгоритм быстрой сортировки на Ассемблере
Алгоритм быстрой сортировки на Ассемблере

Алгоритм быстрой сортировки появился еще на заре компьютерной эпохи в 1960 году. И до сих пор он остается одним из самых быстрых универсальных алгоритмов сортировки массивов. Несмотря на некоторые недостатки в виде наличия рекурсивных вызовов, алгоритм быстрой сортировки очень прост в реализации, не требует выделения дополнительной памяти и даже может быть распараллелен между несколькими подпроцессами.

Существует несколько вариантов алгоритма быстрой сортировки, отличающихся выбором так называемого опорного элемента, разбиением массива, предварительной подготовкой сортируемых данных и т.п. А переложил на Ассемблер классический алгоритм быстрой сортировки, по возможности оптимизировав его под возможности языка. Но, как известно, нет предела совершенству, так что можете доработать код самостоятельно.
  1. ;----------------------------------------------------------------
  2. ; Функция быстрой сортировки массива DWORD
  3. ; by ManHunter / PCL (www.manhunter.ru)
  4. ;----------------------------------------------------------------
  5. ; Параметры:
  6. ;   lpArray - указатель на массив DWORD
  7. ;   dLen - количество элементов в массиве
  8. ;----------------------------------------------------------------
  9. proc quick_sort lpArray:DWORD, dLen:DWORD
  10.         pusha
  11.         mov     ebx,[dLen]
  12.         cmp     ebx,1
  13.         jbe     @f
  14.         dec     ebx
  15.         stdcall q_sort,[lpArray],0,ebx
  16. @@:
  17.         popa
  18.         ret
  19. endp
  20.  
  21. proc q_sort lpArray:DWORD, left:DWORD, right:DWORD
  22.         push    ecx
  23.  
  24.         mov     esi,[right]
  25.         mov     edi,[left]
  26.         mov     ebx,[lpArray]
  27.  
  28.         mov     ecx,[ebx+edi*4]
  29. .q_loop:
  30.         cmp     edi,esi
  31.         jae     .q_done
  32. @@:
  33.         cmp     edi,esi
  34.         jae     @f
  35.         cmp     [ebx+esi*4],ecx
  36.         jb      @f
  37.         dec     esi
  38.         jmp     @b
  39. @@:
  40.         cmp     esi,edi
  41.         je      @f
  42.         mov     eax,[ebx+esi*4]
  43.         mov     [ebx+edi*4],eax
  44.         inc     edi
  45. @@:
  46.         cmp     edi,esi
  47.         jae     @f
  48.         cmp     [ebx+edi*4],ecx
  49.         ja      @f
  50.         inc     edi
  51.         jmp     @b
  52. @@:
  53.         cmp     esi,edi
  54.         je      @f
  55.         mov     eax,[ebx+edi*4]
  56.         mov     [ebx+esi*4],eax
  57.         dec     esi
  58. @@:
  59.         jmp     .q_loop
  60. .q_done:
  61.         mov     [ebx+edi*4],ecx
  62.         mov     ecx,edi
  63.  
  64.         mov     eax,ecx
  65.         cmp     [left],eax
  66.         jae     @f
  67.         dec     eax
  68.         stdcall q_sort,[lpArray],[left],eax
  69. @@:
  70.         mov     eax,ecx
  71.         cmp     [right],eax
  72.         jbe     @f
  73.         inc     eax
  74.         stdcall q_sort,[lpArray],eax,[right]
  75. @@:
  76.         pop     ecx
  77.         ret
  78. endp
Тут используется основной рекурсивный код, а также промежуточная функция-обертка для его вызова с правильно подготовленными параметрами и обеспечения более человекопонятного обращения к самой функции сортировки.
  1.         ; array -> указатель на массив сортируемых DWORD'ов
  2.         ; cnt = количество элементов в массиве
  3.         stdcall quick_sort,array,cnt
Я потестировал алгоритм быстрой сортировки с целью выяснить, как рекурсия может повлиять на работоспособность. При многократной обработке массивов случайных данных из 200.000, 500.000 и даже миллиона записей никаких косяков не вылезло. Ну и скорость сортировки, конечно, выше всяких похвал. Алгоритм полностью оправдывает свое название.

В приложении пример программы с исходным текстом, которая упорядочивает по возрастанию массив DWORD'ов, используя алгоритм быстрой сортировки.

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

Quick.Sort.Demo.zip (1,638 bytes)


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

Комментарии

Отзывы посетителей сайта о статье
Комментариeв нет

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

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

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