[Назад] [Далее] Электронные издания на русском языке

5.7.2. Сортировки

Еще одна часто встречающаяся задача при программировании — сортировка данных. Все существующие алгоритмы сортировки можно разделить на сортировки перестановкой, в которых на каждом шаге алгоритма меняется местами пара чисел; сортировки выбором, в которых на каждом шаге выбирается наименьший элемент и дописывается в отсортированный массив; и сортировки вставлением, в которых элементы массива рассматривают последовательно и каждый вставляют на подходящее место в отсортированном массиве. Самая простая сортировка перестановкой — пузырьковая, в которой более легкие элементы «всплывают» к началу массива. Сначала второй элемент сравнивается с первым и, если нужно, меняется с ним местами. Затем третий элемент сравнивается со вторым и только в том случае, когда они переставляются, сравнивается с первым, и т.д. Этот алгоритм также является и самой медленной сортировкой — в худшем случае для сортировки массива 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