Иллюстрированный самоучитель по задачам и примерам Assembler

Работа с массивами. Сортировка массивов.

Приемы практической работы с массивами продемонстрируем на примерах выполнения конкретных операций: сортировка массива, поиск в массиве, транспонирование матрицы и др. На примере работы с массивами очень удобно обсуждать особенности реализации этих операций, так как в общем случае элементы массива могут быть не просто скалярами, но и более сложными по структуре данными. Поэтому дальнейшее наше изложение помимо демонстрации приемов работы с массивами в программах на ассемблере будет посвящено рассмотрению возможных подходов к реализации нескольких классов практически важных алгоритмов.


Под сортировкой понимается процесс перестановки элементов некоторого множества в порядке убывания или возрастания. Если элементы множества – скаляры, то сортировка ведется относительно их значений. Если элементы множества – структуры, то каждая структура должна иметь поле, относительно которого будет производиться упорядочивание местоположения элементов (то есть сортировка) относительно других элементов-структур множества.

Различают два типа алгоритмов сортировки: сортировку массивов и сортировку файлов. Другое их название – алгоритмы внутренней и внешней сортировки. Разница заключается в местонахождении объектов сортировки: для внутренней сортировки – это оперативная память компьютера, для внешней – файл. В данном разделе будут рассмотрены алгоритмы внутренней сортировки массивов. Алгоритмы внешней сортировки будут рассмотрены в разделе, посвященном работе с файлами.

Существует несколько алгоритмов сортировки массивов, которым следует уделить внимание в контексте проблемы изучения ассемблера. По критерию эффективности алгоритмы сортировки массивов делят на простые и улучшенные. Среди простых методов сортировки, которые также называют сортировками "на том же месте", мы рассмотрим следующие:

  • сортировка прямым включением;
  • сортировка прямым выбором;
  • сортировка прямым обменом.

Улучшенные методы сортировки в нашем изложении будут представлены следующими алгоритмами:

  • сортировка Шелла;
  • сортировка с помощью дерева;
  • быстрая сортировка.

Сортировка прямым включением

Идея сортировки прямым включением (программа prg4_96.asm) заключается в том, что в сортируемой последовательности masi длиной n (i = 0..n – 1) последовательно выбираются элементы начиная со второго (i< 1) и ищутся их местоположения в уже отсортированной левой части последовательности. При этом поиск места включения очередного элемента х в левой части последовательности mas может закончиться двумя ситуациями:

  • найден элемент последовательности mas, для которого masi<x;
  • достигнут левый конец отсортированной слева последовательности.

Первая ситуация разрешается тем, что последовательность mas начиная с masi раздвигается в правую сторону и на место masi перемещается х. Во второй ситуации следует сместить всю последовательность вправо и на место mas0 переместить х.

В этом алгоритме для отслеживания условия окончания просмотра влево отсортированной последовательности используется прием "барьера". Суть его в том, что к исходной последовательности слева добавляется фиктивный элемент X. В начале каждого шага просмотра влево отсортированной части массива элемент X устанавливается в значение того элемента, для которого будет осуществляться поиск места вставки.

ПРОГРАММА рrg4_96
//prg4_96 – программа на псевдоязыке сортировки прямым включением
//Вход: mas[n] – неупорядоченная последовательность байтовых двоичных значений.
//Выход: mas[n] – упорядоченная последовательность байтовых двоичных значений.
//.---------…----…--………
ПЕРЕМЕННЫЕ
INT_BYTE n=8: //количество элементов в сортируемом массиве
INT_BYTE mas[n]: //сортируемый массив размерностью п (О..п-l)
INT_BYTE X; //барьер
INT_BYTE i=0: j=0 //индексы
НАЧ_ПРОГ
ДЛЯ 1:-1 ДО п-1 /Л изменяется в диапазоне О..п-l
НАЧ_БЛ0К_1
//присвоение исходных значений для очередного шага
X: = mas[i]: mas[0]: = X; j: = i-l
ПОКА (X<mas[j]) ДЕЛАТЬ НАЧ_БЛОК_2
mas[j+l]: = mas[j]; j: = j-l КОН_БЛ0К_2
mas[j+l]: = X
КОН_БЛОК_1 КОН_ПРОГ
;prg4_96.asm – программа на ассемблере сортировки прямым включением.
.data
mas db 44.55.12.42.94.18.06.67:задаем массив
n=$-mas
X db 0:барьер
.code
mov ex.п-1:цикл по 1
movsi.l:i=2 сус13: присвоение исходных значений для очередного шага
mov al,mas[si]
movx.al:X: = mas[i]: mas[0]:-X: j: = i-l
push si;временно сохраним i. теперь J-1:еще один цикл, который перебирает элементы
; до барьера x=mas[i] сус12: mov al,mas[si-l]
emp x,al;сравнить х < mas[j-l]
ja ml:если x > mas[j-l]: если x < mas[j-l]. то
mov al,mas[si-l]
irovmas[si],al
dec si
jmpcycl2 ml: mov al,x
movmas[si].al
pop si
incsi
loop cyc!3

Этот способ сортировки не очень экономен, хотя логически он выглядит очень естественно.

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.