Blog. Just Blog

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

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
Сортировка перемешиванием, она же шейкерная или двунаправленная сортировка - оптимизированная разновидность алгоритма пузырьковой сортировки. В процессе сортировки выполняется многократный проход по массиву, соседние элементы сравниваются и, в случае необходимости, меняются местами. Массив просматривается поочередно справа налево и слева направо, из-за этого алгоритм получил свое название. В результате каждого прогона крупные и мелкие элементы массива поочередно перемещаются в конец и начало массива соответственно. Границы рабочей части массива, то есть той части массива, где происходит движение, устанавливаются в месте последнего обмена на каждой итерации.
  1. ;----------------------------------------------------------------
  2. ; Функция сортировки массива DWORD перемешиванием
  3. ; by ManHunter / PCL (www.manhunter.ru)
  4. ;----------------------------------------------------------------
  5. ; Параметры:
  6. ;   lpArray - указатель на массив DWORD
  7. ;   dLen - количество элементов в массиве
  8. ;----------------------------------------------------------------
  9. proc shaker_sort lpArray:DWORD, dLen:DWORD
  10.         pusha
  11.  
  12.         mov     esi,[lpArray]
  13.         ; left
  14.         mov     eax,1
  15.         ; right
  16.         mov     ebx,[dLen]
  17.         cmp     ebx,2
  18.         jb      .loc_ret
  19.  
  20.         dec     ebx
  21.  
  22. .loc_loop_main:
  23.         ; swap_flag = false
  24.         xor     edi,edi
  25.  
  26.         mov     ecx,eax
  27. .loc_loop_1:
  28.         cmp     ecx,ebx
  29.         ja      .loc_done_1
  30.  
  31.         mov     edx,dword [esi+ecx*4-4]
  32.         cmp     dword [esi+ecx*4],edx
  33.         ; Для сортировки по возрастанию заменить на ja
  34.         jna     @f
  35.  
  36.         push    dword [esi+ecx*4-4]
  37.         push    dword [esi+ecx*4]
  38.         pop     dword [esi+ecx*4-4]
  39.         pop     dword [esi+ecx*4]
  40.  
  41.         ; swap_flag = true
  42.         inc     edi
  43. @@:
  44.         inc     ecx
  45.         jmp     .loc_loop_1
  46. .loc_done_1:
  47.         dec     ebx
  48.  
  49.         mov     ecx,ebx
  50. .loc_loop_2:
  51.         cmp     ecx,eax
  52.         jb      .loc_done_2
  53.  
  54.         mov     edx,dword [esi+ecx*4]
  55.         cmp     dword [esi+ecx*4-4],edx
  56.         ; Для сортировки по возрастанию заменить на jb
  57.         jnb     @f
  58.  
  59.         push    dword [esi+ecx*4-4]
  60.         push    dword [esi+ecx*4]
  61.         pop     dword [esi+ecx*4-4]
  62.         pop     dword [esi+ecx*4]
  63.  
  64.         ; swap_flag = true
  65.         inc     edi
  66. @@:
  67.         dec     ecx
  68.         jmp     .loc_loop_2
  69. .loc_done_2:
  70.         inc     eax
  71.  
  72.         or      edi,edi
  73.         jnz     .loc_loop_main
  74.  
  75. .loc_ret:
  76.         popa
  77.         ret
  78. endp
Как и с любыми другими разновидностями пузырьковой сортировки, время выполнения сильно зависит от упорядоченности исходного массива и от количества элементов в нем. Но в любом случае при сортировке перемешиванием сумма сравнений одинакова с пузырьковой сортировкой, а сумма обменов меньше.

В приложении пример программы с исходным текстом, которая сортирует массив DWORD'ов методом перемешивания.

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

Shaker.Sort.Demo.zip (1,653 bytes)


Поделиться ссылкой ВКонтакте
Просмотров: 183 | Комментариев: 7

Комментарии

Отзывы посетителей сайта о статье
user (16.06.2024 в 20:02):
Да уж :( Многие только в вебархиве и остались, ещё порою приходится использовать поисковик по олдскульным сайтам: https://wiby.me
А на хабре сейчас в основном свои телеграм-каналы рекламируют.
ManHunter (16.06.2024 в 18:52):
Где бы их еще взять :((( Особенно русскоязычных. Да и зарубежные публикуются или раз в год, или уже мертвые блоги.
user (16.06.2024 в 01:02):
А можете порекомендовать подобных вам блогеров?

Я имею в виду из русскоязычных. Из англоязычных мне понравился вот этот товарищ - https://blog.demofox.org/ тоже интересный затейник и экспериментатор.
ManHunter (16.06.2024 в 00:41):
Так у меня весь блог именно для этого. От души и для души.
user (16.06.2024 в 00:31):
А, ну тогда похвально! Это называется программирование для души :) В наше время программистов, которые экспериментируют/придумывают/изобретают - исчезающе мало.
ManHunter (15.06.2024 в 17:01):
Ну такими рассуждениями можно быстро добраться до того, что всё для всего уже написано и больше ничего делать не надо. Бери готовые, простигосспадя, фреймворки и библиотеки и не придумывай ничего своего.

QS более чем устраивает, но если в природе есть еще что-то интересное, то почему бы его не покрутить и не повертеть? Хотя бы просто для разминки мозгов.
user (15.06.2024 в 08:39):
А чем Quicksort не устраивает? Рекурсия? Мне для бизнес задач вполне хватает, в экзотических случаях можно подшаманить с размером стека.

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

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

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