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)


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

Комментарии

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

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

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

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