Blog. Just Blog

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

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

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

Суть алгоритма сортировки Шелла заключается в сравнении элементов последовательности, разделенных на группы и находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N - общее число элементов сортируемого массива. На первом шаге каждая группа включает в себя два элемента, расположенных друг от друга на расстоянии N/2. Они сравниваются между собой, и, в зависимости от направления сортировки, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, а количество групп, соответственно, уменьшается. Постепенно расстояние между сравниваемыми элементами уменьшается, и на d=1 проход по массиву происходит в последний раз. Вот как это выглядит на Ассемблере:
Code (Assembler) : Убрать нумерацию
  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)


Поделиться ссылкой ВКонтакте
Просмотров: 707 | Комментариев: 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 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Это я :-)
Если программист в девять утра уже на работе, значит он там же и ночевал
Главная страница Web-мастеру и не только Образ мышления: Assembler Мои программы Software Темная сторона Силы Обзоры техники А еще я туда ем! Жизнь в оффлайне Всякая всячина
Карта сайта Ссылки Обратная связь Правила сайта Настройки сайта RSS-канал
Ограничение по возрасту 16+ Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Метки статей
.NET (27), AJAX (5), Assembler (349), COM (39), CSS (39), Exif (15), FASM (8), Firefox (7), HDD (17), Hello Teddy (9), HTML (48), iconBIT (4), JavaScript (68), MySQL (13), Nikon (19), PDF (9), PHP (119), Samsung (6), SEO (12), Sublime Text (9), TintonLife (4), UGREEN (4), Windows 7 (66), аккумуляторы (22), аксессуары (12), анализаторы файлов (8), архиваторы (5), аттракционы (7), безопасность (55), браузеры (16), бытовая техника (19), варенье (18), ВВЦ (9), ВДНХ (14), видео (20), Воробьевы горы (9), вторые блюда (120), выпечка (27), выставки (116), генератор ПСЧ (10), графика (118), десерты (31), Египет (8), заготовки на зиму (45), закуска (21), закуска к пиву (24), зарядные устройства (23), защита (15), зоопарки (10), игры (36), иконки (22), интерфейс (26), исследование защиты (306), каша (4), клавиатура (7), Коломенское (37), консоль (7), концерты (52), Кузьминки (4), куклы (27), ледяные скульптуры (6), мои программы (68), мониторы (6), музеи (72), мультимедиа (70), мясо (59), напитки (14), ноутбуки (8), обфускация (7), окна (69), оформление сайта (47), парки Москвы (7), песчаные скульптуры (13), плееры (10), подводная съемка (4), поздравления (127), полезные функции (39), прохождения (4), процессы (25), птица (20), путешествия (25), распаковка (22), реверсинг (51), рыба (34), салаты (18), сброс триала (4), сеть (36), система (177), Сокольники (8), соусы (14), супы (14), телефоны (8), Тунис (6), умный дом (12), файлы справки (6), фаст-фуд (18), фестиваль цветов (5), флешки (5), фото (23), хеши (16), числа (8), юмор (12), яйца (17), Яндекс (10)
Вам помог этот сайт?
Сказать спасибо! Поблагодарили 34,343 раза
<< 2024 - АПРЕЛЬ >>
Пн Вт Ср Чт Пт Сб Вс
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30          
Всемирный день настольного тенниса
Нашли на сайте орфографическую ошибку? Выделите ее мышкой и нажмите
Ctrl
+
Enter
Буду очень благодарен, если размеcтите мою кнопочку:
Личный блог ManHunter'а
Valid CSS Valid XHTML 1.0 Transitional Valid mobileOK Basic Valid RSS
Яндекс тИЦ: {YANDEX_TIC} Яндекс ИКС: 380
Сейчас я слушаю
---
Имя:

Сообщение:

Осталось символов: 200

   
-
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2024
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.11 сек. / MySQL: 2 (0.0097 сек.) / Память: 4.5 Mb
Наверх