Способы сортировки массивов
Работа с массивами и стеком на языке ассемблера
Общие сведения о массивах
Как структура представления, массив является упорядоченным множеством элементов определенного типа. Упорядоченность массива определяется набором целых чисел, называемых индексами, которые связываются с каждым элементом массива и однозначно конкретизируют его расположение среди других элементом массива. Локализация конкретного элемента массива - ключевая задача при разработке любых алгоритмов, работающих с массивами.
Наиболее просто представляются одномерные массивы. Соответствующая им структура хранения — это вектор. Она однозначна и есть не что иное, как просто последовательное расположение элементов в памяти. Чтобы локализовать нужный элемент одномерного массива, достаточно знать его индекс. Так как ассемблер не имеет средств для работы с массивом как структурой данных, то для доступа к элементу массива необходимо вычислить его адрес.
Представление двумерных массивов немного сложнее. Здесь мы имеем случай, когда структуры хранения и представления различны. О структуре представления говорить излишне — это матрица. Структура хранения остается прежней — вектор. Но теперь его нельзя без специальных оговорок интерпретировать однозначно. Все зависит от того, как решил разработчик программы «вытянуть» массив — по строкам или по столбцам. Наиболее естествен порядок расположения элементов массива — по строкам. При этом наиболее быстро изменяется последний элемент индекса.
Вывод массива
Пример вывода массива:
;процедура вывода без знакового двухзначного элемента массива
out_elem proc far; AX – входной параметр, т.е. элемент массива
pusha ;помещаем основные регистры в стек
div ten ; после деления первая цифра в AL, а вторая в AH
mov dx,ax; сохраним первую и вторую цифры
mov ah,0Eh
mov bh,00h ; обнулим регистр
mov al,dl ; первую цифру отправляем в AL
add al,'0' ; получаем ASCII символ цифры
int 10h; вывод цифры на экран, вызовом соответствующего прерывания
mov al,dh
add al,'0'
int 10h; вывод второй цифры
popa
ret
out_ elem endp
…
;вызов процедуры в цикле для вывода всех значений массива
xor si,si ;обнуляем счетчик
mov cx,n ; n – размерность массива
out_massiv:
xor ax,ax
mov AL,Z[si]; Z – исходный массив
call out_elem ;
inc si
loop massiv
…
Способы сортировки массивов.
Метод пузырька
Процедура 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 on_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 операций, ни в худшем, ни в среднем случаях; и быстрая сортировка достаточно хорошо приближается к этому пределу в среднем случае. Сортировки, достигающие теоретического предела, тоже существуют — это сортировки турнирным выбором и сортировки вставлением в сбалансированные деревья, но для их работы требуется резервирование дополнительной памяти Так что, например, работа со сбалансированными деревьями будет происходить медленно из-за дополнительных затрат на поддержку сложных структур данных в памяти.
Примеры обработки массивов:
;1) Переменной Max присвоить значение максимального элемента одномерного массива.
.model small ; задание модели памяти
.stack 200h ; задание сегмента стека размером 512 байт
.data ; начало сегмента данных
; выделение 10 байт под массив из 5 элементов (по 2 байта
; каждый) с начальной инициализацией
A dw 5 dup (5,2,8,3,1)
Max dw ? ; выделение 2 байт под переменную
MaxStr dw ? ; значение Max в символьном виде
db ‘$’ ; символ конца строки
.code ; начало сегмента кода
Begin:
mov ax, @Data ; настройка регистра сегмента данных
mov ds, ax
mov ax, A
mov Max, ax
; в регистр si заносится смещение элемента массива относительно
; базового адреса массива(т.к. один элемент массива занимает
; 2 байта, то для второго элемента смещение равно 2 байтам,
; для третьего элемента - 4 байтам и т.д.)
mov si, 2
; команда цикла loop работает с регистром сх, в который
; заносится необходимое количество итераций
mov cx, 4
for_cycle: mov ax, A[si] ; команде дано символическое имя - метка for_cycle
cmp ax, Max
jle do_else
mov Max, ax
do_else: add si, 2
loop for_cycle
;вывод значения переменной Max на экран (для примера считаем
;Max числом, состоящим из одного знака)
add ax, 48 ; получаем код символа значения Max
mov MaxStr, ax
mov dx, offset MaxStr
mov ax, 09h
int 21h
mov ax, 4C00h ; корректное завершение программы
int 21h
end Begin
;2) Задан массив A[N] из элементов типа Byte (целое 8-разрядное без знака).
; Составить программу нахождения максимального и минимального элемента.
; Разместить индексы минимального и максимального элемента в отдельных ячейках
; памяти. Подсчитать среднее арифметическое минимума и максимума.
; Индекс максимального элемента разместим в ячейке IndMax, а индекс ;минимального элемента разместим в ячейке IndMin.
;Среднее арифметическое минимума и
; максимума разместим в ячейке Mean.
.model small
.386
.stack 100h
.data
N dw 10 ; Размерность массива.
A db 3, 120, 2, 6, 11, 5, 4, 34, 15, 10
IndMax dw ? ; Номер максимального элемента в A.
IndMin dw ? ; Номер минимального элемента в A.
Mean db ? ; Среднее арифметическое минимума и максимума.
.code
;процедура очистки экрана
cls_all proc;
pusha
mov ax,0003h;устанавливаем графический режим 03h (80х25)
int 10h; вызываем соответствующее прерывание
popa
ret
cls_all endp
Start:
mov ax, @data
mov ds, ax
mov si, 0 ; Инициализируем счётчик цикла.
mov ch, -128 ; Инициализируем максимальное значение массива.
mov cl, 127 ; Инициализируем минимальное значение массива.
M1: mov al, A[si]
cmp al, ch ; Поиск максимума.
jle M2
mov ch, al ; Текущий элемент больше максимума.
mov IndMax, si ; Запоминаем его номер.
inc IndMax ; Корректировка номера, т.к. si=i-1.
M2: cmp al, cl ; Поиск минимума.
jge M3
mov cl, al ; Текущий элемент меньше минимума.
mov IndMin, si ; Запоминаем его номер.
inc IndMin ; Корректировка номера, т.к. si=i-1.
M3: inc si ; Команды завершения тела цикла.
cmp si, N
jb M1
; Ищем среднее арифметическое минимума(CL) и максимума(CH).
mov al, cl ; AL = Min
add al, ch ; AL = Min+Max
shr al, 1 ; AL = AL / 2 среднее арифметическое.
mov Mean, al ; Записываем результат.
mov ax, 4c00h
int 21h
end Start