|
Быстрая сортировка
Алгоритм предложен Чарльзом Хоаром в 1960 году. Эффективность O(n log n) обменов при сортировке n элементов. Сначала определяется опорное значение, относительно которого и будет производится сортировка. Опорное значение может быть рассчитано, например, как среднее арифметическое крайних левого и правого элементов. Далее все элементы со значениями, большими опорного, перемещаются в правую часть массива, со значениями, меньшими опорного - перемещаются в левую часть массива. Получают два подмассива, каждый из которых сортируют таким же методом. Сортировки продолжают, пока в подмассивах не окажется по одному или по два элемента. Известным недостатком алгоритма является его рекурсивность, которая вызывает необходимость расходования памяти компьютера на запись адресов возврата из процедур сортировки каждого из подмассивов. Зависимость величины дополнительной памяти от числа элементов в исходном массиве характеризуется величиной n - 1.
.386
.model flat, stdcall
option casemap :none
include <\masm32\include\kernel32.inc>
includelib <\masm32\lib\kernel32.lib>
.data
massiv dword 10000 dup (9,6,3,8,5,2,7,4,1,0) ; массив 100 000 чисел
.code
;=========================================================
;=========================================================
; БЫСТРАЯ СОРТИРОВКА
; сортируются по возрастанию четырехбайтовые
; (dword) числа в диапазоне адресов массива от min до max;
; min - указатель на крайнее левое число;
; max - указатель на крайнее правое число
qsort proc public uses EAX EBX EDX EDI ESI, \
min: ptr dword, max: ptr dword
local dwDiv2: dword ; объявляем локальную переменную
mov dwDiv2, 2 ; присваиваем ей значение "2"
mov EDI, min ; в EDI - адрес левого
mov ESI, max ; в ESI - адрес правого
mov EAX, [EDI] ; в EAX - значение (не адрес) левого
add EAX, [ESI] ; складываем EAX со значением правого
mov EDX, 0 ; обнуляем EDX (подготавливаем для деления)
div dwDiv2 ; делим EAX на "2"
mov EBX, EAX ; в EBX - среднее значение левого и правого
.WHILE EDI < ESI ; повторяем, пока адрес левого < адреса правого
.WHILE [EDI] < EBX ; повторяем, пока значение левого < среднего значения
add EDI, 4 ; увеличиваем адрес левого на 4 байта
.ENDW
.WHILE [ESI] > EBX ; повторяем, пока значение правого > среднего значения
sub ESI, 4 ; уменьшаем адрес правого на 4 байта
.ENDW
.IF EDI <= ESI ; если адрес левого <= адреса правого
push [EDI] ; тогда обмен значений через стек
push [ESI]
pop [EDI]
pop [ESI]
add EDI, 4 ; увеличиваем адрес левого на 4 байта
sub ESI, 4 ; уменьшаем адрес правого на 4 байта
.ENDIF
.ENDW
.IF min < ESI ; рекурсии влево
invoke qsort, min, ESI
.ENDIF
.IF EDI < max ; рекурсии вправо
invoke qsort, EDI, max
.ENDIF
ret ; возврат из процедуры
qsort endp
;============================================================
;============================================================
start:
; сортировка массива в диапазоне индексов 1000 - 2000
invoke qsort, addr massiv[1000*4], addr massiv[2000*4]
; сортировка массива в диапазоне индексов 0 - 99999
;invoke qsort, addr massiv[0], addr massiv[99999*4]
invoke ExitProcess, 0
end start
При реализации алгоритмов на ассемблере сортировка расческой может быть в полтора-два раза быстрее быстрой сортировки. Однако, при попадании сортировки расческой в область неудачных обменов ее временной результат начинает существенно проигрывать результату быстрой сортировки.
Таблица. Время работы быстрой сортировки и сортировки расческой
Добавить комментарий
Ассемблер MASM32
Простейшая программа на ассемблере (beeper)
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| © Max Petrov | При использовании материалов ссылка на sadda.ru обязательна |