Сборник по задачам и примерам Assembler


Сортировка массивов - часть 2


Первая ситуация разрешается тем, что последовательность 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

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




- Начало -  - Назад -  - Вперед -