Assembler - язык неограниченных возможностей
Сортировки
Еще одна часто встречающаяся задача при программировании — сортировка данных. Все существующие алгоритмы сортировки можно разделить на сортировки перестановкой, в которых на каждом шаге алгоритма меняется местами пара чисел; сортировки выбором, в которых на каждом шаге выбирается наименьший элемент и дописывается в отсортированный массив; и сортировки вставлением, в которых элементы массива рассматривают последовательно и каждый вставляют на подходящее место в отсортированном массиве. Самая простая сортировка перестановкой — пузырьковая, в которой более легкие элементы «всплывают» к началу массива. Сначала второй элемент сравнивается с первым и, если нужно, меняется с ним местами. Затем третий элемент сравнивается со вторым и только в том случае, когда они переставляются, сравнивается с первым, и т.д. Этот алгоритм также является и самой медленной сортировкой — в худшем случае для сортировки массива N чисел потребуется N2/2 сравнений и перестановок, а в среднем — N2/4.
; Процедура bubble_sort ; сортирует массив слов методом пузырьковой сортировки ; ввод: DS:DI = адрес массива ; DX = размер массива (в словах) bubble_sort proc near pusha cld cmp dx,1 jbe sort_exit ; выйти, если сортировать нечего dec dx sb_loop1: mov cx,dx ; установить длину цикла xor bx,bx ; BX будет флагом обмена mov si,di ; SI будет указателем на ; текущий элемент sn_loop2: lodsw ; прочитать следующее слово cmp ax,word ptr [si] jbe no_swap ; если элементы не ; в порядке, xchg ax,word ptr [si] ; поменять их местами mov word ptr [si-2],ax inc bx ; и установить флаг в 1, no_swap: loop sn_loop2 cmp bx,0 ; если сортировка не закончилась, jne sn_loop1 ; перейти к следующему элементу sort_exit: popa ret bubble_sort endp
Пузырьковая сортировка осуществляется так медленно потому, что сравнения выполняются лишь между соседними элементами. Чтобы получить более быстрый метод сортировки перестановкой, следует выполнять сравнение и перестановку элементов, отстоящих далеко друг от друга. На этой идее основан алгоритм, который называется «быстрая сортировка». Он работает следующим образом: делается предположение, что первый элемент является средним по отношению к остальным. На основе такого предположения все элементы разбиваются на две группы — больше и меньше предполагаемого среднего. Затем обе группы отдельно сортируются таким же методом. В худшем случае быстрая сортировка массива из N элементов требует N2 операций, но в среднем случае — только 2n*log2n сравнений и еще меньшее число перестановок.
; Процедура quick_sort ; сортирует массив слов методом быстрой сортировки ; ввод: DS:BX = адрес массива ; DX = число элементов массива quicksort proc near cmp dx,1 ; Если число элементов 1 или 0, jle qsort_done ; то сортировка уже закончилась xor di,di ; индекс для просмотра сверху (DI = 0) mov si,dx ; индекс для просмотра снизу (SI = DX) dec si ; SI = DX-1, так как элементы нумеруются с нуля, shl si,1 ; и умножить на 2, так как это массив слов mov ax,word ptr [bx] ; AX = элемент X1, объявленный средним step_2: ; просмотр массива снизу, пока не встретится ; элемент, меньший или равный Х1
cmp word ptr [bx][si],ax ; сравнить XDI и Х1
jle step_3 ; если XSI больше, sub si,2 ; перейти к следующему снизу элементу jmp short step_2 ; и продолжить просмотр step_3: ; просмотр массива сверху, пока не встретится ; элемент меньше Х1 или оба просмотра не придут ; в одну точку cmp si,di ; если просмотры встретились, je step_5 ; перейти к шагу 5, add di,2 ; иначе: перейти ; к следующему сверху элементу, cmp word ptr [bx][di],ax ; если он меньше Х1, jl step_3 ; продолжить шаг 3 steр_4: ; DI указывает на элемент, который не должен быть ; в верхней части, SI указывает на элемент, ; который не должен быть в нижней. Поменять их местами mov cx,word ptr [bx][di] ; CX = XDI
xchg cx,word ptr [bx][si] ; CX = XSI, XSI = XDI
mov word ptr [bx][di],cx ; XDI = CX jmp short step_2 step_5: ; Просмотры встретились. Все элементы в нижней ; группе больше X1, все элементы в верхней группе ; и текущий - меньше или равны Х1 Осталось ; поменять местами Х1 и текущий элемент: xchg ах,word ptr [bx][di] ; АХ = XDI, XDI = X1
mov word ptr [bx],ax ; X1 = AX ; теперь можно отсортировать каждую из полученных групп push dx push di push bx
mov dx,di ; длина массива X1...XDI-1
shr dx,1 ; в DX call quick_sort ; сортировка
pop bx pop di pop dx
add bx,di ; начало массива XDI+1...XN
add bx,2 ; в BX shr di,1 ; длина массива XDI+1...XN
inc di sub dx,di ; в DX call quicksort ; сортировка qsort_done: ret quicksort endp
Кроме того, что быстрая сортировка — самый известный пример алгоритма, использующего рекурсию, то есть вызывающего самого себя, это еще и самая быстрая из сортировок «на месте», то есть сортировка, использующая только ту память, в которой хранятся элементы сортируемого массива. Можно доказать, что сортировку нельзя выполнить быстрее, чем за n*log2n операций, ни в худшем, ни в среднем случаях, и быстрая сортировка достаточно хорошо приближается к этому пределу в среднем случае. Сортировки, достигающие теоретического предела, тоже существуют — это сортировки турнирным выбором и сортировки вставлением в сбалансированные деревья, но для их работы требуется резервирование дополнительной памяти, так что, например, работа со сбалансированными деревьями будет происходить медленно из-за дополнительных затрат на поддержку сложных структур данных в памяти.
Рассмотрим в качестве примера самый простой вариант сортировки вставлением, использующий линейный поиск и затрачивающий порядка n2/2 операций. Ее так же просто реализовать, как и пузырьковую сортировку, и она тоже имеет возможность выполняться «на месте». Кроме того, из-за высокой оптимальности кода этой процедуры она может оказываться даже быстрее рассмотренной нами «быстрой» сортировки на подходящих массивах.
; Процедура linear_selection_sort ; сортирует массив слов методом сортировки линейным выбором ; Ввод: DS:SI (и ES:SI) = адрес массива ; DX = число элементов в массиве
do_swap: lea bx,word ptr [di-2] mov ax, word ptr [bx] ; новое минимальное число dec cx ; если поиск минимального закончился, jcxz tail ; перейти к концу loop1: scasw ; сравнить минимальное в АХ ; со следующим элементом массива ja do_swap ; если найденный элемент ; еще меньше - выбрать ; его как минимальный loop loop1 ; продолжить сравнения ; с минимальным в АХ tail:. xchg ax,word ptr [si-2] ; обменять минимальный элемент mov word ptr [bx],ax ; с элементом, находящимся в начале ; массива linear_selection_sort proc near ; точка входа в процедуру mov bx,si ; BX содержит адрес ; минимального элемента lodsw ; пусть элемент, адрес ; которого был в SI, минимальный, mov di,si ; DI - адрес элемента, сравниваемого ; с минимальным dec dx ; надо проверить DX-1 элементов массива mov cx,dx jg loop1 ; переход на проверку, если DX > 1 ret linear_selection_sort endp
