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

Еще одначасто встречающаяся задача при программировании—сортировкадан-ных. Все существующие алгоритмы сортировки можно разделить на сортировки перестановкой, в которых на каждом шаге алгоритма меняется местами пара чисел; сортировки выбором, в которых на каждом шаге выбирается наименьший элемент и дописывается в отсортированный массив; и сортировки вставлением, в которых элементы массива рассматривают последовательно и каждый вставляют на подхо­дящее место в отсортированном массиве. Самая простая сортировка перестанов­кой - пузырьковая, в которой более легкие элементы «всплывают» к началу масси­ва: сначала второй элемент сравнивается с первым и, если нужно, меняется с ним местами; затем третий элемент сравнивается со вторым и только в том ког­да они переставляются, сравнивается с первым, и т. д. Этот алгоритм также явля­ется и самой медленной сортировкой - в худшем случае для сортировки массивам чисел потребуется №/2 сравнений и перестановок, а в среднем - №/4.

; Процедура ЬиЬЫе_зоП.

;  Сортирует массив слов методом пузырьковой сортировки.

; Вход: DS: DI

= адрес массива

 

;           DX =

эазмер массива (в

словах)

bubble_sort

proc near

 

pusha

 

 

eld

 

 

cmp

dx,1

 

jbe

so'rt exit

;   Выйти,  если сортировать

dec

dx

 

sb_loop1:mov

cx, dx

; Установить длину цикла.

xor

bx, bx

;  ВХ будет флагом обмена.

mov

si, di

;  SI будет указателем на

текущий элемент.

ЗП_1оор2:^Зи 4       ;   Прочитать следующее слово.

cmp

ax, word

ptr [si]

 

jbe

noswap

;

Если элементы не в порядке,

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 элементов требует № операций, но в среднем случае - только 2nlog2n срав­нений и еще меньшее число перестановок.

;   Процедура си1ск_зог1:.

; Сортирует массив слов методом быстрой сортировки. ;  Вход:  DS:BX - адрес массива

;

DX

число элементов массива

quicksort cmp jle хог mov

dec

shX

proc near dx,1

qsort_done

di.di

si,dx

si

Si,1

ptr [bx]

Если число элементов 1 или О,

то сортировка уже закончилась.

Индекс для просмотра сверху   ^ = 0).

Индекс для просмотра снизу (Б1 = ОХ).

SI = ОХ-1, так как элементы

нумеруются с нуля,

и умножить'на 2, так как

это массив слов.

АХ = элемент X.   объявленный средним.

step_2:   ; Просмотр массива снизу,   пока не  встретится элемент,

step_3:

; меньший или равный X .

cmp       word ptr [bx][si],ax

jle step_3

sub       si, 2

jmp        short step_2

; Просмотр массива сверху, пока ; меньше Х1 или оба просмотра не cmp       si, di je step_5 ■

add di,2

cmp      word ptr [bx][di],ax jl step_3 ; Сравнить Хи и X.. ; Если Х51 больше, 'перейти ; к следующему снизу элементу и продолжить просмотр.

не встретится элемент придут в одну точку.

Если просмотры встретились, перейти к шагу В. Иначе: перейти

к следующему сверху элементу. Если он меньше X , продолжить шаг 3.

step_4:

; DI указывает на элемент, который

; SI указывает на элемент, который ;  Поменять их иестами.

mov cx.word ptr [bx][di]

xchg cx.word ptr [bx] [si] ;

mov word ptr [bx][di],cx       ; X0]

jmp short step_2

должен быть должен быть

верхней части, нижней части.

CX = CX =

CX

step_5:

Просмотры встретилисв.   Все элементы в нижней  группе болвше X,, все элементы в верхней группе и текущий - меньше или равны Осталось поменять местами      и текущий элемент:

xchg ptr [bx][di]

mov       word ptr [bx],ax

;

АХ

AX

=

Теперь можно отсортировать каждую из полученных групп.

 

push

dx

 

push

di

 

push

bx

 

mov

dx, di

Длина массива Х1...ХИ_]

shr

dx, 1

в DX.

call

quicksort •

Сортировка.

pop

bx

 

pop

di

 

pop

dx

 

add

bx, di

;  Начало массива Х0М...Хн

add

bx,2

■    ;   в ВХ.

shr

di, 1

;  Длина массива Х№1...ХВ

inc

di

sub

dx, di

;   в ' DX.

call

quick_sort

; Сортировка.

qsort_done:ret quicksort

endp

Помимо того, что быстрая сортировка - самый известный пример алгоритма, использующего рекурсию, то есть вызывающего самого себя, это еще и самая бы­страя из сортировок «на месте», то есть сортировка, применяющая только ту па­мять, в которой хранятся элементы сортируемого массива. Можно доказать, что сортировку нельзя выполнить быстрее, чем за nlog2n операций, ни в худшем, ни в среднем случаях, и быстрая сортировка хорошими темпами приближается к это­му пределу в среднем случае. Сортировки, достигающие теоретического предела, тоже существуют - это сортировки турнирным выбором и сортировки вставлени­ем в сбалансированные деревья, но для их работы требуется резервирование до­полнительной памяти, так что, например, работа со сбалансированными деревья­ми будет происходить медленно из-за дополнительных затрат на поддержку сложных структур данных в

Приведем в качестве примера самый простой вариант сортировки вставлени­ем, использующей линейный поиск и затрачивающей порядка п2/2 операций. Ее так же просто реализовать, как и пузырьковую сортировку, и она тоже имеет воз­можность выполняться «на месте». Кроме того, из-за высокой оптимальности кода этой процедуры она может оказаться даже быстрее рассмотренной нами «быстрой» сортировки на подходящих массивах.

; Процедура linear_selection_sort.

; Сортирует массив слов методом сортировки линейным выбором.

; Вход: DS:SI (и ES:SI) = адрес массива • ; DX = число элементов в массиве

do_swapplea bx, word ptr [di-2]

mov ax, word ptr [bx]           ;  Новое минималвное число,

dec        cx ;  Если поиск минимального закончился,

jcxz tail ;  перейти к концу.

loopl: scasw

ja

loop

tail:

xchg mov do_swap

loopl

ax,word ptr [si-2] word ptr [bx],ax ;

Сравнить минималвное в АХ

со следующим элементом массива.

Если найденный элемент еще меньше -

выбрать его как минимальный.

Продолжить сравнения

с минимальным элементом в АХ.

;   Обменять минимальный элемент ' с элементом, находящимся

;  в начале массива.

linear selection sort

proc

mov lodsw

mov

dec

mov 19

ret

si

di, si

dx

cx.dx

loopl

near       ;  Точка входа в процедуру.

ВХ содержит адрес минимального элемента. Пусть элемент, адрес

которого был в SI, минимальный,

DI - адрес элемента, сравниваемого с минимальным.

Надо проверить DX-1 элементов массива. Переход на проверку,  если DX > 1.

linear_selection _sort endp