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




Начало  Назад  Вперед