Алгоритм быстрой сортировки на Ассемблере
Алгоритм быстрой сортировки на Ассемблере
Алгоритм быстрой сортировки появился еще на заре компьютерной эпохи в 1960 году. И до сих пор он остается одним из самых быстрых универсальных алгоритмов сортировки массивов. Несмотря на некоторые недостатки в виде наличия рекурсивных вызовов, алгоритм быстрой сортировки очень прост в реализации, не требует выделения дополнительной памяти и даже может быть распараллелен между несколькими подпроцессами.
Существует несколько вариантов алгоритма быстрой сортировки, отличающихся выбором так называемого опорного элемента, разбиением массива, предварительной подготовкой сортируемых данных и т.п. Я переложил на Ассемблер классический алгоритм быстрой сортировки, по возможности оптимизировав его под особенности языка. Но, как известно, нет предела совершенству, так что можете доработать код самостоятельно.
Code (Assembler) : Убрать нумерацию
- ;----------------------------------------------------------------
- ; Функция быстрой сортировки массива DWORD
- ; by ManHunter / PCL (www.manhunter.ru)
- ;----------------------------------------------------------------
- ; Параметры:
- ; lpArray - указатель на массив DWORD
- ; dLen - количество элементов в массиве
- ;----------------------------------------------------------------
- proc quick_sort lpArray:DWORD, dLen:DWORD
- pusha
- mov ebx,[dLen]
- cmp ebx,1
- jbe @f
- dec ebx
- stdcall q_sort,[lpArray],0,ebx
- @@:
- popa
- ret
- endp
- proc q_sort lpArray:DWORD, left:DWORD, right:DWORD
- push ecx
- mov esi,[right]
- mov edi,[left]
- mov ebx,[lpArray]
- mov ecx,[ebx+edi*4]
- .q_loop:
- cmp edi,esi
- jae .q_done
- @@:
- cmp edi,esi
- jae @f
- cmp [ebx+esi*4],ecx
- jb @f
- dec esi
- jmp @b
- @@:
- cmp esi,edi
- je @f
- mov eax,[ebx+esi*4]
- mov [ebx+edi*4],eax
- inc edi
- @@:
- cmp edi,esi
- jae @f
- cmp [ebx+edi*4],ecx
- ja @f
- inc edi
- jmp @b
- @@:
- cmp esi,edi
- je @f
- mov eax,[ebx+edi*4]
- mov [ebx+esi*4],eax
- dec esi
- @@:
- jmp .q_loop
- .q_done:
- mov [ebx+edi*4],ecx
- mov ecx,edi
- mov eax,ecx
- cmp [left],eax
- jae @f
- dec eax
- stdcall q_sort,[lpArray],[left],eax
- @@:
- mov eax,ecx
- cmp [right],eax
- jbe @f
- inc eax
- stdcall q_sort,[lpArray],eax,[right]
- @@:
- pop ecx
- ret
- endp
Code (Assembler) : Убрать нумерацию
- ; array -> указатель на массив сортируемых DWORD'ов
- ; cnt = количество элементов в массиве
- stdcall quick_sort,array,cnt
В приложении пример программы с исходным текстом, которая упорядочивает по возрастанию массив DWORD'ов, используя алгоритм быстрой сортировки.
Пример программы с исходным текстом (FASM)
Просмотров: 1335 | Комментариев: 1
Метки: Assembler, полезные функции
Внимание! Статья опубликована больше года назад, информация могла устареть!
Комментарии
Отзывы посетителей сайта о статье
Добавить комментарий
Заполните форму для добавления комментария
Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Вам помог этот сайт?
Поблагодарили 34,347 раз
Поблагодарили 34,347 раз
Буду очень благодарен, если размеcтите мою кнопочку:
 |
Яндекс ИКС: 380 |
 |
 |
mov ebx,FirstElement
mov esi,LastElement
cmp ebx,esi
jae SortUseless
push esi ;for second qSort
mov eax,esi ;\pivot to edi
sub eax,ebx
shr eax,3
mov edi,[ebx+eax*4] ;/
TestDownOnBig:
cmp [ebx],edi
jge SwapNeeded
add ebx,4
jmp TestDownOnBig
TestTopOnSmall:
sub esi,4
SwapNeeded:
cmp [esi],edi
jg TestTopOnSmall
cmp ebx,esi ;\if cant'move
ja AllSwapped ;/then get out
mov eax,[esi] ;\swap
xchg eax,[ebx] ;
mov [esi],eax ;/
sub esi,4 ;next down
add ebx,4 ;next top
cmp ebx,esi ;\if nothing to move
jbe TestDownOnBig ;/
AllSwapped:
push ebx ;for second qSort
sub ebx,4 ;pivot-1
push ebx
push FirstElement
call qSort
call qSort
SortUseless:
ret
qSort endp