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

Сортировка Шелла на Ассемблере
Сегодня разберем еще один алгоритм сортировки - сортировку Шелла. Он назван в честь ученого Дональда Шелла, который в 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
Просмотров: 350 | Комментариев: 0
Метки: Assembler, полезные функции

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

Добавить комментарий
Заполните форму для добавления комментария
