ГЛАВА 14
МАССИВЫ
Хотя ассемблер позволяет проверять и обрабатывать биты, но, как правило, программы предназначены для обработки и хранения данных и взаимодействуют с ячейками памяти, кратным байтам (байты, слова, двойные слова, учетверенные слова, параграфы и т.д.).
Рассмотрим составные объекты данных — совокупности простых объектов, объединенных под одним именем. Иногда с такими составными объектами работают как с неделимыми, но иногда могут потребоваться и их отдельные компоненты. Составные объекты данных можно разбить на два класса в соответствии с методом определения компонент.
Массивы — это такие совокупности, в которых компоненты определяются по их положению внутри совокупности.
Структуры — это совокупности, в которых компоненты определяются по именам.
Из этого следует, что все компоненты массивов должны иметь одинаковый тип, в то время как компоненты структуры могут быть разных типов. Значением массива является набор значений его компонент, а значением структуры — набор ссылок на ее компоненты. Основные операции,
которые можно применять к массивам, как к множествам — объединение, пересечение, дополнение, разность, слияние, декартово произведение.
Основные операции, которые можно применять к элементам массивов — вставка, удаление, сортировка, поиск элемента по заданному ключу, поиск подмассива в массиве и т.д.
Массивы предназначены для хранения данных одного типа и для удобного доступа к содержимому этих данных. Элемент массива определяется своей позицией. Позиция — это отсчет смещения от начала массива. Элементы некоторого массива сами могут быть массивами — тогда позиция элементов будет определяться в координатной системе более чем одного
измерения. Элемент многомерного массива будет определяться несколькими индексами, например, в
-мерном массиве
элементы определяются индексами
. Число индексов
, требуемых для определения элемента массива, называется размерностью массива.
Одномерный массив напоминает очередь, в которой все люди обезличены, но у каждого на ладони написан порядковый номер, соответствующий расположению этого человека в очереди. Массивы отличаются от одиночных переменных одинакового типа тем, что каждая отдельная переменная имеет индивидуальное имя, а все элементы массива имеют групповое имя и различаются между собой, как люди в очереди, порядковыми номерами или индексами.
Описание массива и его инициализация
(задание начальных значений элементам массива)
Вместо десяти переменных величиной в слово:
| Assembler |
1
2
3
4
| X1 DW 10
X2 DW 9
…
X10 DW 1 |
|
можно использовать одномерный массив:
| Assembler |
1
| X DW 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 |
|
перечислив элементы массива после директивы описания данных. При этом в переменной
хранится не одно значение, а последовательность из 10 значений типа WORD. К каждому из них можно обращаться, указывая его номер (индекс), который может быть не только числовой константой, но и любым допустимым выражением, возвращающим значение типа WORD. Элементы массива располагаются в памяти строго последовательно, друг за другом, при компиляции все упоминания переменной
заменяются на физический адрес первого элемента этого массива в оперативной памяти, а все обращения к элементам массива заменяются на машинные команды сложения адреса
с индексом — смещением соответствующего элемента относительно начала этой последовательности. Такое смещение для первого элемента будет 0. Для второго — 1 и т.д. Структура хранения, соответствующая одномерному массиву — вектор. Для вычисления адреса
-ого элемента вектора
используют следующую формулу:
Адрес(X[i])=Адрес(X)+(type X)*i
где Адрес
— положение в памяти первого элемента вектора,
— размер элемента вектора в байтах. Система команд микропроцессоров семейства x86 позволяет работать с массивами размерностью 1, 2, 4 и 8 байтов. Перечисление элементов массива через запятую удобно в том случае, если таких элементов не очень много (не более двадцати). Для большого количества элементов, в том случае, если они имеют одно и тоже значение, или массив не инициализирован, используют директиву DUP. В этом случае синтаксис описания массивов в ассемблере таков:
<имя массива> D< тип> <число элементов>DUP (<значение>)
Например, директива:
отводит в памяти 40 байт под неинициализированный массив слов X. Конструкция DUP допускает вложенность. Директива:
| Assembler |
1
| A DB 20 DUP (1,2,3,0Eh,0Fh) |
|
отводит в памяти место под массив A из ста байт. В этом массиве элементы будут заполнены 20 раз повторяющимися значениями 1,2,3,0Eh,0Fh.
Если массив должен быть проинициализирован элементами, которые имеют характер арифметической/геометрической прогрессии, тогда можно воспользоваться директивами REPT и =
| До макрогенерации | После макрогенерации | В теле программы |
|---|
X DB 0 K=0REPT 999 K=K+1DB K ENDM | X DB 0 K=0K=K+1 DB K. . .999 таких пар K=K+1DB K | X DB 0,1,2, ...,998,999 |
Для инициализации значений элементов массива в процессе выполнения программы используют цикл.
Одиночная переменная выбирается из массива переменных при помощи указания индекса: a[2], a[i+1], a[0], a[i*j], причем индекс должен находится внутри границ диапазона.
Такая индексированная переменная для объектов определенного типа может употребляться повсюду, где могли бы находится простые переменные того же типа: 2*a[2], (a[i+1])
2, sin(a[i*j]). С индексом также можно производить все допустимые выражения, которые возвращают целочисленные значения (например, после деления необходимо округлять результат вычисления) a[
].
Все скалярные операции над массивами сводятся к скалярным поэлементным операциям.
Структура хранения соответствующая двухмерному массиву — матрица. Пусть имеется матрица Y, в которой N строк и M столбцов и все элементы матрицы — двойные слова:
Поскольку реальная память компьютера — это одномерный массив, массивы размещаются в непрерывной области памяти, для обращения к элементу массива, имеющему несколько индексов, в позиции одномерной памяти назначают соответствие между последовательными ячейками памяти и элементами массива. Такое соответствие называется
функцией отображения. Зависимость адреса элемента матрицы Y[i,j], расположенного в линейной памяти компьютера от индексов элемента i и j, можно выразить вот так:
Адрес(Y[i,j])=Адрес(Y)+M*(type Y)*i+(type Y)*j=Адрес(Y)+(type Y)*(M*i+j),
где Адрес(Y) — положение в памяти первого элемента матрицы, type Y=4 — размер элемента матрицы в байтах, а M — ширина строки. Или вот так:
Адрес(Y[i,j])=Адрес(Y)+(type Y)*i+N´(type Y)*j=Адрес(Y)+(type Y)*(i+N*j),
где N — высота столбца.
Аналогично осуществляется локализация элементов в массивах большей размерности. Например, трехмерный массив
, все элементы которого байты, размерностью
:
| Assembler |
1
| Z DB N DUP (M DUP (K DUP (?))) |
|
Рассмотрим расположение в памяти трехмерного массива байтов A размером
относительно первого элемента массива A[0,0,0]:
| элемент | позиция | элемент | позиция | элемент | позиция | элемент | позиция |
|---|
| A[0,0,0] | 0 | A[0,1,0] | 3 | A[0,0,1] | 6 | A[0,1,1] | 9 |
| A[1,0,0] | 1 | A[1,1,0] | 4 | A[1,0,1] | 7 | A[1,1,1] | 10 |
| A[2,0,0] | 2 | A[2,1,0] | 5 | A[2,0,1] | 8 | A[2,1,1] | 11 |
Если трехмерный массив байтов A имеет размерность
, тогда адресация элемента A[i,j,k] (где
,
,
) этого массива в одномерную память осуществляется с помощью следующей функции отображения:
Адрес(A[i,j,k])=Адрес(A)+i+I*j+I*J*k=Адрес(A)+i+I*(j+J *k)
В общем случае функция отображения для многомерного массива байтов A размером
, где
,
,
,...,
,
:
Адрес(A[i,j,k,...,m,n])=Адрес(A)+i+I*(j+J*(k+K*(...(m+M*n)...) ))
Доступ к элементам массива
Для указания элемента массива требуется имя массива и индексы. Нумерация элементов массива начинается с нуля. В общем случае, для получения адреса элемента необходимо начальный (базовый) адрес массива сложить с произведением индекса (номер элемента) этого элемента на размер элемента массива:
база + (индекс*размер элемента)
Для доступа к элементам одномерного массива используют индексную адресацию со смещением (смещение — адрес нулевого элемента массива и индекс, который находится в индексном регистре).
Для доступа к элементам двухмерного массива используют базово-индексную адресацию со смещением (смещение — адрес нулевого элемента массива, произведение ширины строки на номер столбца в базовом регистре и индекс в строке, который находится в индексном регистре).
По мере увеличения размерности массива возрастает сложность вычисления адреса. Даже для трехмерного байтового массива вычисление индекса требует трех умножений. Для упрощения вычисления адреса массива постараемся уменьшить количество операций умножения.
Во-первых, при заполнении элементов массива одинаковым значением, или для получения суммы/произведения значения всех элементов массива, или для поиска минимального/максимального элемента массива, вычислять индекс каждого элемента ни к чему. Для этих задач подходит и одномерное представление нашего массива.
| Assembler |
1
2
3
4
5
6
7
| ;получить в edx:eax сумму значений элементов массива A[N][M][Q]
xor eax,eax ;eax=0
cdq ;edx=0
mov ecx,N*M*Q ;ecx = количество элементов массива A
a0: add eax,A[ecx*4-4]
adc edx,0
loop a0 |
|
Во-вторых, если действительно необходим доступ к элементам
-мерного массива
— создадим блок описания нашего массива
| Assembler |
1
2
3
4
5
6
| ;номер индекса содержимое
index_1 equ I
index_2 equ I*J
index_3 equ I*J*K
... ...
index_m equ I*J*K*...*M |
|
Значение произведений index_2=I*J, ..., index_m=I*J*K*...*M будет вычисляться заранее, еще во время трансляции нашей программы, и в процессе выполнения программы мы не будем затрачивать на это время. При обращении к элементу массива адресный полином
Адрес(A)+i+I*(j+J*(k+K*(...(m+M*n)...)))
будет заменен на сумму произведений
Адрес(A)+i+index_1*j+index_2*k+...+index _m*n
В-третьих, умножение в некоторых случаях можно заменять на комбинацию из сдвигов вправо и сложения, либо на команду LEA, а также использовать возможность умножения внутри команд на 2, 4 или 8.
Модификация адресов
До сих пор рассматривались команды, в которых для операндов из памяти указывались их точные адреса (имена), например:
MOV ECX,[A]
Если исполнительный адрес берется непосредственно из 8-, 16-или 32-разрядного поля смещения в коде конкретной команды, такая адресация называется
прямой.
Однако в общем случае в команде вместе с адресом может быть указан в квадратных скобках некоторый регистр, например:
MOV ECX,A[EBX]
Тогда команда будет работать не с указанным в ней адресом A, а с адресом A
исп, который вычисляется по следующей формуле:
Aисп=(A + [EBX]) mod 232
где [EBX] обозначает содержимое регистра EBX. Прежде чем выполнить команду, процессор прибавит к адресу A, указанному в команде, текущее содержимое регистра EBX, получит некоторый новый адрес A
исп и именно из ячейки с этим новым адресом возьмет новый операнд. Если в результате сложения получилась слишком большая сумма, то от нее возьмут только последние 32 бита (на это указывает операция mod в приведенной формуле).
Замена адреса A на A
исп называется модификацией адреса, а регистр, участвующий в модификации, называется
регистром-модификатором.
В качестве модификатора для микропроцессоров ниже i386 можно было использовать только один из четырех регистров: BX, BP, SI или DI. Для микропроцессоров i386 и выше можно использовать любой 32-битный РОН (
регистр общего назначения).
В команде ADD A[ESI],5 в роли модификатора выступает регистр ESI. Пусть в регистре ESI находится число 100. Тогда A
исп=A+[ESI]=A+100. Значит, по данной команде к числу из ячейки с адресом A +100 будет прибавлено 5.
Если исполнительный адрес вычисляется как сумма некоторого заданного смещения и содержимого индексного регистра, то такой способ адресации называется индексной адресацией. Индексная адресация часто используется для для организации доступа к элементам массивов. Если исполнительный адрес вычисляется как сумма некоторого заданного смещения и содержимого базового регистра, то такой способ адресации называется относительной адресацией.
Индексирование
Пусть имеется массив
и в регистр EAX требуется записать сумму его элементов. Для нахождения суммы делаем EAX равным 0, а затем в цикле выполним операцию EAX=EAX+X[i] при
изменяющимся от 0 до 99. Поскольку адрес элемента X[i] равен X+4*i, то команда, соответствующая этой операции, должна быть следующей ADD EAX,[X+4*i], но вот досада, транслятор не может напрямую закодировать такую команду.
Наш адрес меняется вместе с изменением индекса
. Разобьем переменный адрес X+4*i на постоянную составляющую X и переменную 4*i.
Постоянную составляющую запишем в команду, а переменную составляющую
поместим в регистр-модификатор (например, в ECX) и название этого регистра записываем в команду в качестве модификатора
ADD EAX,X [ECX*4-4]
Фрагмент программы нахождения суммы элементов массива X:
| Assembler |
1
2
3
4
| XOR EAX,EAX ;начальное значение суммы EAX=0
MOV ECX,100 ;счетчик цикла и индекс массива
L: ADD EAX,X[ECX*4-4] ;EAX=EAX+X[i]
LOOP L ;цикл 100 раз |
|
Косвенные ссылки
Пусть имеется некоторая ячейка размером в слово, адрес которой не известен, но известно, что этот адрес находится в регистре EBX, и необходимо записать в эту ячейку число 300. Если бы адрес X этой ячейки был бы известен, то использовалась бы команда
Команды могут работать с исполнительными адресами, возьмем такой адрес и такой модификатор, чтобы в сумме они дали этот заранее неизвестный адрес — в данном случае это нулевой адрес и регистр EBX.
A
исп=0+[EBX]=0+X=X. Задача решается командой
Особенность используемого способа модификации в том, что адрес представлен в виде суммы двух слагаемых, одно из которых записано в команду, а другое в регистр-модификатор. Но если ранее оба слагаемых были ненулевые, то теперь одно из слагаемых, которое помещалось в команду, нулевое, и поэтому весь адрес упрятан в регистр.
В команде указывается лишь место (регистр), где находится адрес.
Способ задания адреса через промежуточное звено называется
косвенной ссылкой или
косвенной адресацией.
При косвенной ссылке обычно приходится уточнять размер ячейки, на которую она указывает. Если в ячейку, адрес которой находится в регистре EBX, надо записать 0, тогда использовать для этого команду mov[ebx],0 нельзя, так как в ней непонятны размеры операндов: 0 может
быть как байтом или словом, так и двойным словом, адрес из EBX также может быть адресом как байта или слова, так и двойного слова. А вот число 300000 в регистре EBX может быть только двойным словом и неоднозначности не возникает. Поэтому с помощью оператора PTR надо указать, операнды какого размера имеются в виду:
| Assembler |
1
2
3
| mov byte ptr[ebx],0 ;пересылка байта
mov word ptr[ebx],0 ;пересылка слова
mov dword ptr[ebx],0;пересылка двойного слова |
|
Модификация по нескольким регистрам
Идея модификации обобщается на случай нескольких регистров-модификаторов. Для этого в командах указывается вместе с адресом несколько регистров-модификаторов. Максимальное количество модификаторов — два, причем для микропроцессоров ниже i386 один из них обязательно должен быть регистром BX или BP, а другой обязательно SI или DI.
Например: mov ax,A[bx][si]. Для микропроцессоров i386 и выше для модификации по двум регистрам в качестве базового регистра можно использовать любой из 32-разрядных РОН'ов, а в качестве индексного регистра — любой из 32-разрядных РОН'ов, кроме регистра ESP.
Индексный регистр можно также умножить на коэффициент scale равный 1, 2, 4 или 8.
Для 16-битного режима исполнительный адрес вычисляется по формуле:
A
исп = (A + [BX] + [SI]) mod 2
16.
Для 32-битного режима исполнительный адрес вычисляется по формуле:
A
исп = (A + [РОН
1] + [РОН
2]*scale) mod 2
32.
Модификация по двум регистрам обычно используется при работе с двумерными массивами. Например, в матрицу
размером
требуется записать в регистр AL количество таких строк этой матрицы, в которых начальный элемент строки встречается в ней еще раз.
| Assembler |
1
| A DB 10 DUP (20 DUP (?)) |
|
При расположении элементов матрицы в линейной модели памяти адрес элемента A[i, j] равен A+20*i+j. Для хранения величины 20*i отведем регистр EBX. Для хранения величины j отведем регистр ESI.
A[EBX] — начальный адрес i-ой строки, A[EBX+ESI] — адрес j-го элемента этой строки.
| Assembler |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| MOV AL,0 ;Количество искомых строк
;Внешний цикл по строкам
MOV ECX,10 ;Счетчик внешнего цикла
XOR EBX,EBX ;Смещение от A до начала строки 20*i
L: MOV AH,A[EBX] ;Начальный элемент строки
PUSH ECX ;Сохранить счетчик внешнего цикла
;Внутренний цикл по столбцам
MOV ECX,19 ;Счетчик внутреннего цикла
XOR ESI,ESI ;Индекс элемента внутри строки j
L1: INC ESI ;j=j+1
CMP A[EBX+ESI],AH ;A[i,j]=AH?
LOOPNE L1;Цикл,пока A[i,j]<>AH, но не более 19 раз
JNE L2 ;AH не повторился перейти на L2
INC AL ;Учет строки
;Конец внутреннего цикла
L2: POP ECX ;Восстановить счетчик внешнего цикла
ADD EBX,20 ;На начало следующей строки
LOOP L ;Цикл 10 раз |
|
Если исполнительный адрес вычисляется как сумма некоторого заданного смещения, содержимого регистра базы и индексного регистра, такой способ адресации называется относительной индексной адресацией. В ходе выполнения программы могут меняться два компонента адреса.
Запись модифицированных адресов
Предположим, что мы работаем в 16-битном режиме. Пусть A обозначает адресное выражение, а E — любое выражение (адресное или константное), тогда в языке ассемблера допустимы следующие три основные формы записи адресов в командах, которые задают следующие исполнительные адреса:
A: A
исп = A
E[M]: A
исп = (E+[M]) mod 2
16 M: BX, BP, SI, DI
Модификация по одному регистру: в качестве модификатора можно использовать только один из четырех регистров: BX, BP, SI или DI.
E[M1][M2]: A
исп=(E+[M1]+[M2])mod 2
16 M1: BX или BP; M2: SI или DI
Модификация по двум регистрам: один из них обязательно должен быть регистром BX или BP, а другой обязательно SI или DI.
Если E=0, то 0 можно опустить: 0[M]=M.
Модификация не меняет тип адреса. Если X — имя байтовой переменной, то TYPE X[SI] = BYTE. Если перед модификатором указано константное выражение (1[BX]), то тип такого адреса считается неопределенным.
Кроме трех указанных способов записи адресов допускаются и другие, являющиеся производными от трех основных.
Для 32-разрядного режима:
- модификация по одному регистру
Aисп = (E+[РОН]*scale) mod 232
- модификация по двум регистрам
Aисп = (E+[РОН1]+[РОН2]*scale) mod 232
Соглашение об использовании квадратных скобок при записи операторов команд:
- Запись в квадратных скобках имени регистра-модификатора (в 16-битном режиме BX, BP, SI или DI; в 32-битном режиме все 32-разрядные РОН'ы) эквивалентна выписыванию содержимого
этого регистра (имя регистра без квадратных скобок обозначает сам регистр).
- Любое выражение можно заключить в квадратные скобки, от этого смысл не изменится, но снятие квадратных скобок может изменить смысл.
MOV ECX,[2]
MOV ECX,[A]
MOV ECX,[A+2[EBX]]
Выписывание рядом двух выражений в квадратных скобках означает сумму этих выражений.
[X][Y]=[X]+[Y]=[X+Y]
Используя эти соглашения вместе со свойством коммутативности сложения и отталкиваясь от трех основных способов записи адресов в командах, можно получить новые варианты записи адресов.
Эквивалентные формы записи одного и того же адреса:
A+1, [A+1], [A]+[1], [A][1], A[1], 1[A], [A]+1, …
Сортировка элементов массива
Оценка алгоритма сортировкиДля типичного алгоритма хорошее поведение — это
и плохое поведение — это
. Идеальное поведение для упорядочения —
.
— это количество записей, которые необходимо упорядочить. Для всех случаев рассматривается последовательность из 26 элементов-двойных слов:
| Assembler |
1
2
| array dd 10,450,320,120,180,600,50,230,340,460,550,500,130
dd 80,390,410,20,800,670,60,730,610,310,0,360,200 |
|
Блочная сортировка
(Корзиночная сортировка, Bucket sort)
Сортируемые элементы делятся на конечное число отдельных блоков (корзин). Каждый блок затем сортируется отдельно. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения
; требуется дополнительная память-массив до сортировки.
массив после сортировки
3 9 21 25 29 37 43 49
Пузырьковая сортировкаЭто простейший алгоритм сортировки с точки зрения понимания и реализации, но эффективен лишь для небольших массивов. Лучший случай при упорядочении массива из
элементов — если массив отсортирован за
сравнений. В худшем случае — если массив отсортирован в обратном порядке — при сортировке произойдет
сравнение. (Для
элементов лучший случай — 25, средний — 289, худший — 325.)
Сортировка состоит из повторяющихся проходов по сортируемому массиву. В каждом проходе элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. За первый проход просматривают все n элементов. Во втором проходе сравнивают
элементов, начиная со второго, так как первый элемент находится уже на своем месте. В третьем проходе — начинают со третьего элемента и т.д. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны — массив полностью рассортирован. В каждом проходе элемент, стоящий не на своём месте, «всплывает» до нужной позиции, как пузырёк в воде.
| Assembler |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| .data
R dd n-1;количество неотсортированных элементов минус один
.code
mov esi,offset array ;позиционируемся на массив
a2: mov ecx,R
xor ebx,ebx ;флаг - были/не были перестановки в проходе
a3: mov eax,[esi+ecx*4-4] ;получаем значение очередного элемента
cmp [esi+ecx*4],eax ;сравниваем со значением соседнего элемента
jnb a4 ;если больше или равен - идем к следующему элементу
setna bl ;была перестановка - взводим флаг
xchg eax,[esi+ecx*4] ;меняем значение элементов местами
mov [esi+ecx*4-4],eax
a4: loop a3 ;двигаемся вверх до границы массива
add esi,4 ;сдвигаем границу отсортированного массива
dec ebx ;проверяем, были ли перестановки
jnz exit ;если перестановок не было - заканчиваем сортировку
dec R ;уменьшаем количество неотсортированных элементов
jnz a2;если есть еще неотсортированные элементы - начинаем новый проход
exit: |
|
Сортировка перемешиванием
(сортировка коктейлем, шейкер-сортировка, bidirectional bubble sort)
Разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а меньшие — к началу. (Для
элементов лучший случай — 25, средний — 259 (лучше пузырьковой сортировки на 20 %), худший — 325.)
| Assembler |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| .data
H dd 0 ;верхняя граница неотсортированного массива
L dd n-1 ;нижняя граница неотсортированного массива
.code
xor esi,esi ;нижняя граница неотсортированного массива
xor ebx,ebx ;флаг - были/не были перестановки в проходе
mov ecx,L;количество неотсортированных элементов снизу минус один
a4: inc esi
call Compare_and_Swapping ;сравнение и обмен значений элементов
loop a4 ;двигаемся вниз до границы массива
dec ebx ;проверяем, были ли перестановки
jnz exit ;если перестановок не было - сортировка закончена
dec L ;уменьшаем количество неотсортированных элементов снизу
jz exit ;достигли границы массива
dec esi ;esi=L
mov ecx,esi
sub ecx,H;количество неотсортированных элементов сверху минус один
jecxz exit ;если граница снизу равна границе сверху - выходим
a2: call Compare_Swapping ;сравнение и обмен значений элементов
dec esi
loop a2 ;двигаемся вверх до границы массива
dec ebx ;проверяем, были ли перестановки
jnz exit ;если перестановок не было - заканчиваем сортировку
inc H ;уменьшаем количество неотсортированных элементов сверху
inc esi ;esi=H
mov ecx,L
sub ecx,esi ;если граница снизу больше, чем граница сверху - значит
ja a4;есть еще неотсортированные элементы - начинаем новый проход
exit: . . .
Compare_Swapping proc;сравнение и обмен значений соседних элементов
mov eax,array[esi*4] ;получаем значение очередного элемента
cmp array[esi*4-4],eax ;сравниваем его с соседним элементом
jna a3 ;если меньше или равен - идем к следующему элементу
seta bl ;если была перестановка - взводим флаг
xchg eax,array[esi*4-4] ;меняем значения элементов местами
mov array[esi*4],eax
a3: ret
Compare_Swapping endp |
|
Пирамидальная сортировка
(Сортировка кучи, Heap sort)
Список превращается в кучу, берется наибольший элемент и добавляется в конец списка. Алгоритм сортировки делает в худшем, в среднем и в лучшем случае (т.е. гарантированно)
операций при сортировке
элементов. Можно рассматривать как усовершенствованную пузырьковую сортировку, в которой min-heap элемент всплывает/max-heap тонет по многим путям.
Структура данных для хранения сортирующего дерева
Пример сортирующего дерева Сортировка пирамидой использует сортирующее дерево высоты
, у которого выполнены условия:
- Все узлы имеют высоту или
— дерево сбалансированое.
- При этом уровень полностью заполнен, а уровень заполнен слева направо, то есть пирамида имеет вид:
- Выполняется «свойство пирамиды»: каждый элемент меньше, либо равен родителю.
- Удобная структура данных для сортирующего дерева — такой массив A, где A[i] — элемент-предок, а элементы-потомки — это
![https://www.cyberforum.ru/cgi-bin/latex.cgi?A[2\cdot i]](https://www.cyberforum.ru/cgi-bin/latex.cgi?A%26%2391%3B2%5Ccdot%20i%26%2393%3B)
и ![https://www.cyberforum.ru/cgi-bin/latex.cgi?A[2\cdot i+1]](https://www.cyberforum.ru/cgi-bin/latex.cgi?A%26%2391%3B2%5Ccdot%20i%2B1%26%2393%3B)
, то есть каждый элемент-предок находится слева от своих элементов-потомков
Алгоритм состоит из двух основных фаз:
- элементы массива выстраиваются в виде сортирующего дерева:
Эта фаза требует операций.
- Корневые элементы удаляются по одному и каждый раз дерево перестраивается. На первом шаге элементы A[1] и A[n] обмениваются значениями, а процедура heap_sort преобразует элементы от A[1] до A[n-1] в сортирующее дерево. Затем переставляют A[1] и A[n-1], элементы от A[1] до A[n-2] снова преобразуются в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется ни одного элемента. Тогда элементы от A[1] до A[n] — это упорядоченная последовательность.
Эта фаза требует 
операций.
| Assembler |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| .data
L dd n/2-1 ;левая граница неотсортированного массива
R dd n-1 ;правая граница неотсортированного массива
.code
;массив преобразуется в отображение пирамиды - вызвать процедуру
;down_heap n/2 раз для преобразования массива в пирамиду
b0: call down_heap
dec L ;while ( L > 0 ) L--;
jnz short b0
;собственно пирамидальная сортировка
dec L ;L=0
dec R ;R=n-2
b1: mov edx,R ;отправляем значение максимального
mov eax,array ;элемента в конец массива
xchg eax,array[edx*4+4] ; array[0] <--> array[R];
mov array,eax
call down_heap ;восстанавливаем пирамиду - на ее
;вершине появляется новое максимальное значение
dec R ;уменьшаем индекс последнего элемента
jnz short b1 ;while ( R > 0 ) R--;
b2: ...
;-----------------------------------------------------
down_heap proc; процедура вставки элемента на свое место в пирамиду
mov eax,L
mov ebx,eax ;i = L;
shl eax,1 ;j = 2*L;
mov esi,array[eax*2] ;item = array[L];
cmp eax,R ;if( j<R && array[j] < array[j+1]) j++;
jnb short a0
mov edx,array[eax*4]
cmp edx,array[eax*4+4] ;array[j] < array[j+1] ?
jnb short a0
; условие j<R && array[j]<array[j+1] выполнилось
inc eax ;j++
a0: cmp eax,R ;while( j£R && item < array[j])
ja short a1
mov edi,array[eax*4]
cmp esi,edi ;item < array[j] ?
jnb short a1
; условие j<=R && item < array[j] выполнилось
mov array[ebx*4],edi ;array[i] = array[j];
mov ebx,eax ;i = j;
shl eax,1 ;j = 2*j;
cmp eax,R
jnb short a0;if( j<R && array[j] < array[j+1]) j++;
mov edx,array[eax*4]
cmp edx,array[eax*4+4]
jnb short a0
; условие j<R && array[j] < array[j+1] выполнилось
inc eax ;j++
jmp short a0
a1: mov array[ebx*4],esi ;array[i] = item;
retn
down_heap endp |
|
Для
элементов лучший случай — 25, средний — 109 (лучше пузырьковой сортировки почти в 3 раза), худший — 325.
Сортировка прямым включением
Сортировка вставками (
Insertion sort) — Сложность алгоритма:
; преимущества:
- простота реализации;
- эффективен на небольших наборах данных;
- эффективен на наборах данных, которые уже частично отсортированы;
- сортировка не меняет порядок элементов, которые уже отсортированы;
- можно сортировать список по мере его получения.
На каждом шаге алгоритма выбирается один из элементов входных данных, начиная со второго, и вставляется на нужную позицию в уже отсортированной левой части списка до тех пор пока набор входных данных не будет исчерпан. Выбор очередного элемента, выбираемого из исходного массива — произволен, можно использовать практически любой алгоритм выбора. Для
элементов лучший случай — 25, средний — 172 (лучше пузырьковой сортировки на 40% ), худший — 325.
| Assembler |
1
2
3
4
5
6
7
8
9
10
11
12
13
| mov esi,4 ;i=1
a4: push esi
a3: mov eax,array[esi-4]
cmp eax,array[esi]
jb a2
xchg eax,array[esi]
sub esi,4 ;двигаемся к началу массива
mov array[esi],eax
jnz a3
a2: pop esi
add esi,4 ;двигаемся к концу массива
cmp esi,n*4 ;просмотрели весь массив?
jb a4 |
|
Алгоритм можно улучшить пользуясь тем, что готовая последовательность уже упорядочена. Место вставки нового элемента можно найти значительно быстрее, если применить бинарный поиск, исследовав сперва средний элемент упорядоченной последовательности и продолжая деление пополам, пока не будет найдено место вставки. Для
элементов лучший случай — 25, средний и худший — 106 (лучше пузырьковой сортировки почти в 3 раза).
| Assembler |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| mov ebx,1 ;ebx - граница неотсортированного массива
b1: mov edi,ebx
mov edx,edi;edi индекс первого элемента отсортированного массива
xor esi,esi;esi индекс последнего элемента отсортированного массива
mov eax,array[ebx*4]
cmp eax,array[ebx*4-4]
jnb b2
b6: cmp esi,edi ;проверка esi>edi на завершение поиска
jg b5 ;проверены все элементы, вставляем новый элемент
shr edx,1 ;индекс центрального элемента равен (edi+esi)/2
cmp array[edx*4],eax;сравниваем с искомым значением
ja b3 ;array[edx*4]<eax
jz b5 ;array[edx*4]=eax
inc edx ;учтем только что проверенное значение
mov esi,edx ;изменяем нижнюю границу поиска
add edx,edi ;создаем индекс центрального элемента
jmp short b6 ;переходим к следующему элементу
b3: dec edx ;учтем только что проверенное значение
mov edi,edx ;изменяем верхнюю границу поиска
add edx,esi ;создаем индекс центрального элемента
jmp b6 ;переходим к следующему элементу
b5: mov ecx,ebx ;сдвигаем отсортированные элементы, чтобы
sub ecx,esi ;освободить место для нового элемента
shl esi,2; esi=esi*4
push eax
b7: mov eax,array[esi+ecx*4-4];сдвиг отсортированных элементов
mov array[esi+ecx*4],eax
loop b7
pop eax
mov array[esi],eax;вставляем новый элемент
b2: inc ebx
cmp ebx,n
jb b1 |
|
Сортировка прямым выбором
Алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов время выполнения в худшем, среднем и лучшем случае
.
Шаги алгоритма:
- находим минимальное значение в текущем списке;
- производим обмен этого значения со значением на первой позиции;
- теперь сортируем хвост списка, исключив из рассмотрения уже отсортированный первый элемент.
| Assembler |
1
2
3
4
5
6
7
8
9
10
11
12
| mov edi,offset array ;edi = указатель на массив
mov ecx,N ;ecx = количество элементов
a0: lea ebx,[edi+ecx*4] ;ebx = максимальный индекс в проходе+1
mov eax,[edi] ;eax=min=величина первого элемента в проходе
a1: sub ebx,4 ;двигаемся по проходу вверх
cmp eax,[ebx]
jbe a2 ;min > array[ebx] ?
xchg eax,[ebx] ;swap(array[ebx],min)
a2: cmp ebx,edi
jnz a1 ;проход закончился?
stosd ;mov [edi],eax edi=+4 на первой позиции минимальный элемент
loop a0 |
|
Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента.
Существует также двунаправленный вариант сортировки методом вставок, в котором на каждом проходе отыскивается и устанавливается на своё место и минимальное, и максимальное значения.
Сортировка Шелла
Алгоритм сортировки, идея которого состоит в сравнении элементов, стоящих не только рядом, но и на расстоянии друг от друга.
При сортировке Шелла сначала сравниваются и сортируются между собой элементы, отстоящие друг от друга на некотором расстоянии
. После этого процедура повторяется при значениях
меньших, чем
, сортировка завершается упорядочиванием элементов при
(то есть, обычной сортировкой вставками).
Пусть дан список
и выполняется его сортировка методом Шелла, а в качестве значений
,
и
выбраны 5, 3, 1. На первом шаге сортируются подсписки
, составленные из всех элементов
, различающихся на 5 позиций, т.е. подсписки
,
,
,
, A_{5,5}=(a_{5},a_{15})[/latex]. В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов. Процесс завершается обычной сортировкой вставками получившегося списка.
Выбор длины промежутков
Среднее время работы алгоритма зависит от длин промежутков (
), на которых будут находится сортируемые элементы исходного списка на каждом шаге алгоритма. Существует несколько подходов к выбору этих значений (
— длина сортируемого списка):
- при выборе последовательности значений
, 
в худшем случае алгоритм выполнит — сравнений 140:| Assembler |
1
| Table dd 32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1 |
|
- все значения
, 
; такая последовательность шагов приводит к алгоритму класса 
— сравнений 108:| Assembler |
1
| Table dd 797161,265720,88573,29524,9841,3280,1093,364,121,40,13,4,1 |
|
- все значения
, где 
, в порядке убывания; в таком случае сложность алгоритма понижается до 
- последовательность из
, если 
четное и 
если нечетное. При использовании таких приращений среднее количество операций: 
, в худшем случае — порядка 
- последовательности вида
— сравнений 118:| Assembler |
1
| Table dd 32767,16383,8191,4095,2047,1023,511,255,127,63,31,15,7,3,1 |
|
- последовательность Дж. Инсерпи и Р. Седгевика — сравнений 115:
| Assembler |
1
| Table dd 198768,86961,33936,13776,4592,1968,861,336,112,48,21,7,3,1 |
|
| Assembler |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| ;------------------------------------------------
mov ecx,-17;в таблице приращений 16 элементов
entry: inc ecx
jz exit; если последний элемент в таблице - выход из программы
cmp [Table+ecx*4+64],n; ищем максимальное приращение (gap),
jge entry;соответствующее размеру нашего массива
a6: mov edx,[Table+ecx*4+64];получаем очередное приращение из таблицы
shl edx,2;выбрали интервал,у нас двойные слова,поэтому edx=edx´4
a2: mov ebx,edx;i=gap
a3: mov esi,ebx
sub esi,edx;j=i-gap
a4: mov eax,array[esi];for(i=gap;i<dim;i++)/*проход массива*/
cmp eax,array[esi+edx];сравнение пар,отстоящих
jbe a5;на gap друг от друга
xchg eax,array[esi+edx];swap(a[j],a[j+gap])
mov array[esi],eax
sub esi,edx ;j-=gap
jge a4
a5: add ebx,4 ;i++
cmp ebx,n*4 ;i < dim
jb a3 ;for(j=i-gap; j>=0 && a[j] > a[j+gap]
inc ecx
jnz a6
exit: |
|
Сортировка Хоара (быстрая сортировка)
Сортировка даёт в среднем
сравнений при упорядочении
элементов. В худшем случае получается
сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой
, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.
Шаги алгоритма:
- В массиве выбирается некий опорный элемент (pivot).
- Массив реорганизуется таким образом, чтобы все элементы со значением меньше или равным значению pivot оказались слева от него, а элементы со значением больше значения pivot — справа от него.
- Рекурсивно упорядочиваются подсписки, лежащие слева и справа от опорного элемента.
- Базой рекурсии являются списки, состоящие из одного или двух элементов, которые уже упорядочены. За каждую итерацию, по крайней мере один элемент ставится на свое место.
При выборе опорного элемента из данного диапазона случайным образом, худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки —
.
| Assembler |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| push offset array+n*4-4;указатель на последний элемент
push offset array;указатель на первый элемент массива
call quick_sort ; quicksort (data, data+n-1)
;-----------------------------------------------------
partition proc Lb:dword, Ub:dword
; функция partition возвращает адрес pivot
mov edx,Ub
sub edx,eax ;eax=Lb
shr edx,3 ;(Ub-Lb)/2
; После завершения этого цикла все значения слева от элемента pivot
; будут меньше значения элемента pivot, а все значения справа от
; элемента pivot будут больше, чем значение элемента pivot
mov edi,[eax+edx*4] ;получаем указатель на pivot
;pivot = *(Lb+(Ub-Lb)/2)
cmp eax,Ub ;eax=Lb
ja short b0 ;return Lb;
; Поиск значения, большего чем pivot, в нижней части массива
b1: mov eax,Lb
cmp [eax],edi ;edi=pivot
jnl short b3 ;while (*Lb < pivot)
add Lb,4 ;Lb++;
jmp short b1
; Поиск значения, меньшего чем pivot, в верхней части массива
b4: sub Ub,4
b3: mov eax,Ub
cmp [eax],edi ;while (*Ub > pivot)
jg short b4 ;Ub--
mov ecx,Lb
cmp ecx,eax ;eax=Ub
ja short b5 ;if(Lb <= Ub)
sub Ub,4 ;swap( Lb++, Ub-- )
add Lb,4
mov edx,[eax] ;eax=Ub
xchg edx,[ecx] ;ecx=Lb
mov [eax],edx ;*Ub<-->*Lb;
b5: mov eax,Lb
cmp eax,Ub
jbe short b1 ;while (*Lb < pivot)
b0: pop ebp
retn 8
partition endp
;------------------------------------------------------------
quick_sort proc Lb:dword, Ub:dword
mov eax,Lb
cmp eax,Ub ; if (Lb >= Ub)
jnb short exit1 ;сортировать нечего
push Ub
push eax ;eax=Lb
call partition
mov edi,eax ;eax=pivot_ptr
sub eax,4 ;pivot_ptr-1
push eax
push Lb
call quick_sort ;отсортируем то, что слева от pivot
push Ub
push edi ;edi=pivot_ptr
call quick_sort ; и то, что справа от pivot
exit1: pop ebp
retn 8
quick_sort endp |
|
Контрольные вопросы и упражнения
- Напишите программу, которая упорядочивает в алфавитном порядке буквы, коды которых находятся в CHAR, CHAR+1, ...,CHAR+20 при помощи известных вам способов сортировки.
- Пусть имеется массив DATA_LIST из 10 двойных слов. Напишите программу, которая:
- помещает наибольшее и наименьшее из чисел DATA_LIST в регистры EBX и EDX;
- вычисляет сумму и произведение чисел DATA_LIST и запоминает результаты в SUM и PRODUCT соответственно.
- Используйте двумерный массив в метеорологической программе. Найдите общее количество осадков для каждого года, среднегодовое количество осадков и среднее количество осадков за каждый месяц. Для получения общего количества осадков за год сложите все данные, находящиеся в нужной строке. Чтобы найти среднее количество осадков за данный месяц складываете все данные в указанном столбце.
- Дан массив A размера N. Упорядочить его по возрастанию методом сортировки простым обменом («пузырьковой» сортировкой): просматривать массив, сравнивая его соседние элементы (A1 и A2, A2 и A3 и так далее) и менять их местами, если левый элемент пары больше правого; повторить описанные действия
раз. Для контроля за выполняемыми действиями выводить содержимое массива после каждого просмотра на экран. Учесть, что при каждом просмотре количество анализируемых пар уменьшается на 1.
- Дан массив A размера N. Упорядочить его по возрастанию методом сортировки простым выбором: найти максимальный элемент массива и поменять его с последним
-м элементом; выполнить описанные действия раз, каждый раз уменьшая на 1 количество анализируемых элементов и выводя содержимое массива на экран.
- Дан массив размера . Упорядочить его по возрастанию методом сортировки простыми вставками: сравнить элементы A1 и A2 и, при необходимости меняя их местами, добиться того, чтобы они оказались упорядоченными по возрастанию; затем обратиться к элементу A3 и переместить его в левую (уже упорядоченную) часть массива, сохранив ее упорядоченность; повторить этот процесс для остальных элементов, выводя содержимое массива на экран после обработки каждого элемента (от A2 до AN). При выполнении описанных действий удобно использовать прием «барьера», записывая очередной элемент перед его обработкой в дополнительный элемент массива A0.
- Дан массив A размера N. Не изменяя данный массив, вывести номера его элементов на экран в том порядке, в котором соответствующие им элементы образуют возрастающую последовательность. Использовать метод «пузырьковой» сортировки, модифицировать его следующим образом: создавать вспомогательный целочисленный массив номеров I, заполнив его числами от 1 до N; просматривать массив A, сравнивая пары элементов массива A с номерами I1 и I2, I2 и I3, … и меняя местами соответствующие элементы массива I, если левый элемент пары больше правого. Повторив описанную процедуру раз, получим в массиве I требуемую последовательность номеров.
