Blog. Just Blog

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

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

Сегодня разберем еще один алгоритм сортировки - сортировку Шелла. Он назван в честь ученого Дональда Шелла, который в 1959 году опубликовал этот алгоритм. Сортировка Шелла представляет собой нечто среднее между классической пузырьковой сортировкой и сортировкой вставками, легко реализуется на разных языках программирования, при этом показывает хорошую скорость работы и не требует выделения дополнительной памяти.

Суть алгоритма сортировки Шелла заключается в сравнении элементов последовательности, разделенных на группы и находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N - общее число элементов сортируемого массива. На первом шаге каждая группа включает в себя два элемента, расположенных друг от друга на расстоянии N/2. Они сравниваются между собой, и, в зависимости от направления сортировки, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, а количество групп, соответственно, уменьшается. Постепенно расстояние между сравниваемыми элементами уменьшается, и на d=1 проход по массиву происходит в последний раз. Вот как это выглядит на Ассемблере:
  1. ;----------------------------------------------------------------
  2. ; Функция сортировки массива DWORD по алгоритму Шелла
  3. ; by ManHunter / PCL (www.manhunter.ru)
  4. ;----------------------------------------------------------------
  5. ; Параметры:
  6. ;   lpArray - указатель на массив DWORD
  7. ;   dLen - количество элементов в массиве
  8. ;----------------------------------------------------------------
  9. proc shell_sort lpArray:DWORD, dLen:DWORD
  10.         pusha
  11.  
  12.         mov     esi,[lpArray]
  13.  
  14.         mov     ecx,[dLen]
  15.         ; Разделить на 2 с округлением в большую сторону
  16.         shr     ecx,1
  17.         jnc     .loc_loop_1
  18.         inc     ecx
  19. .loc_loop_1:
  20.         or      ecx,ecx
  21.         jz      .loc_ret
  22.  
  23.         mov     edi,ecx
  24. .loc_loop_2:
  25.         mov     edx,edi
  26.         sub     edx,ecx
  27. .loc_loop_3:
  28.         or      edx,edx
  29.         js      @f
  30.  
  31.         mov     eax,edx
  32.         add     eax,ecx
  33.         mov     ebx,[esi+eax*4]
  34.         mov     eax,[esi+edx*4]
  35.         cmp     eax,ebx
  36.         ; Для сортировки массива по убыванию замените
  37.         ; условный переход JBE на JAE
  38.         jae     @f
  39.  
  40.         ; Поменять местами элементы
  41.         mov     [esi+edx*4],ebx
  42.         mov     ebx,edx
  43.         add     ebx,ecx
  44.         mov     [esi+ebx*4],eax
  45.  
  46.         sub     edx,ecx
  47.         jmp     .loc_loop_3
  48. @@:
  49.         inc     edi
  50.         cmp     edi,[dLen]
  51.         jb      .loc_loop_2
  52.  
  53.         shr     ecx,1
  54.         jmp     .loc_loop_1
  55. .loc_ret:
  56.         popa
  57.         ret
  58. endp
В приложении пример программы с исходным текстом, которая сортирует массив по алгоритму Шелла.

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

Shell.Sort.Demo.zip (1,673 bytes)


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

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

Комментарии

Отзывы посетителей сайта о статье
ManHunter (28.04.2023 в 20:31):
Ну если при этом правильно работает, то хорошо
darkz (28.04.2023 в 19:59):
Rar архив на максимальном сжатие. Вроде разобрался должно быть,не ?       
shr ecx,1
.loc_loop_1:
        or ecx,ecx
        jz .loc_ret
        dec ecx
        jne   @f
        inc    ecx
@@:
ManHunter (27.04.2023 в 19:30):
Файл какой-то особый или просто 26 214 400 рандомных dword ?
darkz (27.04.2023 в 19:06):
Mahnunter. Я могу конечно ошибаться но по-моему в вашем сортировке присутствует небольшой  баг.
Смотрите,У меня есть точно такая же сортировка pascalshellsort и я провел небольшие тесты на скорость межу вашей вашей сортировкой и своей.И Выяснилось что если мы берём фаил размером в 100mb.rar/4  (26 214 400 dword) то происходит залагивания. Тоже самое происходит при файле 10mb.rar/4 (2 621 440dword)

При любом другом размере файла все норм

Тесты:
10mb.rar/4 pascalshellsort=2 сек
10mb.rar/4 shell_sort=8 сек (баг)

100mb.rar/4 pascalshellsort=28 сек
100mb.rar/4 shell_sort=3мин40сек (баг)

300mb.rar/4 pascalshellsort=2.30мин
300mb.rar/4 shell_sort=2.40сек. (норм)
Darkz (10.04.2023 в 21:54):
Thanks you это самая нормальная сортировка под fasm.              Я как-то находил в интернете эту сортировку переписанную на fasm с Паскаля и она в разы быстрей qsort падаюшиго на рекурсии и тормозящего при отсортированном массиве.

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

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

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