Способы сортировки массивов

Работа с массивами и стеком на языке ассемблера

Общие сведения о массивах

Как структура представления, массив является упорядоченным множеством элементов определенного типа. Упорядоченность массива определяется набором целых чисел, называемых индексами, которые связываются с каждым элементом массива и однозначно конкретизируют его расположение среди других элементом массива. Локализация конкретного элемента массива - ключевая задача при разработке любых алгоритмов, работающих с массивами.

Наиболее просто представляются одномерные массивы. Соответствующая им структура хранения — это вектор. Она однозначна и есть не что иное, как просто последовательное расположение элементов в памяти. Чтобы локализовать нужный элемент одномерного массива, достаточно знать его индекс. Так как ассемблер не имеет средств для работы с массивом как структурой данных, то для доступа к элементу массива необходимо вычислить его адрес.

Представление двумерных массивов немного сложнее. Здесь мы имеем случай, когда структуры хранения и представления различны. О структуре представления говорить излишне — это матрица. Структура хранения остается прежней — вектор. Но теперь его нельзя без специальных оговорок интерпретировать однозначно. Все зависит от того, как решил разработчик программы «вытянуть» массив — по строкам или по столбцам. Наиболее естествен порядок расположения элементов массива — по строкам. При этом наиболее быстро изменяется последний элемент индекса.

Вывод массива

Пример вывода массива:

;процедура вывода без знакового двухзначного элемента массива

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 элементов требует N² операций, но в среднем случае - только 2n*log₂n сравнений и еще меньшее число перестановок.

Метод быстрой сортировки:

; Процедура 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*log₂n операций, ни в худшем, ни в среднем случаях; и быстрая сортировка достаточно хорошо приближается к этому пределу в среднем случае. Сортировки, достигающие теоретического предела, тоже существуют — это сортировки турнирным выбором и сортировки вставлением в сбалансированные деревья, но для их работы требуется резервирование дополнительной памяти Так что, например, работа со сбалансированными деревьями будет происходить медленно из-за дополнительных затрат на поддержку сложных структур данных в памяти.

Примеры обработки массивов:

;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