Сортировка Шелла на Ассемблере
Сортировка Шелла на Ассемблере
Сегодня разберем еще один алгоритм сортировки - сортировку Шелла. Он назван в честь ученого Дональда Шелла, который в 1959 году опубликовал этот алгоритм. Сортировка Шелла представляет собой нечто среднее между классической пузырьковой сортировкой и сортировкой вставками, легко реализуется на разных языках программирования, при этом показывает хорошую скорость работы и не требует выделения дополнительной памяти.
Суть алгоритма сортировки Шелла заключается в сравнении элементов последовательности, разделенных на группы и находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N - общее число элементов сортируемого массива. На первом шаге каждая группа включает в себя два элемента, расположенных друг от друга на расстоянии N/2. Они сравниваются между собой, и, в зависимости от направления сортировки, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, а количество групп, соответственно, уменьшается. Постепенно расстояние между сравниваемыми элементами уменьшается, и на d=1 проход по массиву происходит в последний раз. Вот как это выглядит на Ассемблере:
Code (Assembler) : Убрать нумерацию
- ;----------------------------------------------------------------
- ; Функция сортировки массива DWORD по алгоритму Шелла
- ; by ManHunter / PCL (www.manhunter.ru)
- ;----------------------------------------------------------------
- ; Параметры:
- ; lpArray - указатель на массив DWORD
- ; dLen - количество элементов в массиве
- ;----------------------------------------------------------------
- proc shell_sort lpArray:DWORD, dLen:DWORD
- pusha
- mov esi,[lpArray]
- mov ecx,[dLen]
- ; Разделить на 2 с округлением в большую сторону
- shr ecx,1
- jnc .loc_loop_1
- inc ecx
- .loc_loop_1:
- or ecx,ecx
- jz .loc_ret
- mov edi,ecx
- .loc_loop_2:
- mov edx,edi
- sub edx,ecx
- .loc_loop_3:
- or edx,edx
- js @f
- mov eax,edx
- add eax,ecx
- mov ebx,[esi+eax*4]
- mov eax,[esi+edx*4]
- cmp eax,ebx
- ; Для сортировки массива по убыванию замените
- ; условный переход JBE на JAE
- jae @f
- ; Поменять местами элементы
- mov [esi+edx*4],ebx
- mov ebx,edx
- add ebx,ecx
- mov [esi+ebx*4],eax
- sub edx,ecx
- jmp .loc_loop_3
- @@:
- inc edi
- cmp edi,[dLen]
- jb .loc_loop_2
- shr ecx,1
- jmp .loc_loop_1
- .loc_ret:
- popa
- ret
- endp
Пример программы с исходным текстом (FASM)
Просмотров: 532 | Комментариев: 5
Метки: Assembler, полезные функции
Комментарии
Отзывы посетителей сайта о статье
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
@@:
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сек. (норм)
Смотрите,У меня есть точно такая же сортировка 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 падаюшиго на рекурсии и тормозящего при отсортированном массиве.
Добавить комментарий
Заполните форму для добавления комментария
Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Вам помог этот сайт?
Поблагодарили 33,197 раз
Поблагодарили 33,197 раз
Буду очень благодарен, если размеcтите мою кнопочку:
 |
Яндекс ИКС: 400 |
 |
 |