Работа с массивами. Сортировка массивов.
Сортировка прямым выбором
В алгоритме сортировки прямым выбором (программа prg4_99.asm) на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной минимальный элемент. Если он найден, то производится его перемещение на место крайнего левого элемента несортированной правой части массива.
ПРОГРАММА prg4_99 //prg4_99 – программа на псевдоязыке сортировки прямым выбором //Вход: mas[n] – неупорядоченная последовательность байтовых двоичных значений. //Выход: mas[n] – упорядоченная последовательность байтовых двоичных значений. //.ПЕРЕМЕННЫЕ INT_BYTE n=8; //количество элементов в сортируемом массиве INT_BYTE mas[n]; //сортируемый массив размерностью п (О..п-l) INTJYTE X: i=0: j=0: k=0 // i .j, k – индексы НАЧ_ПРОГ ДЛЯ i: = l ДО n-1 //i изменяется в диапазоне 1..П-1 НАЧ_БЛОК_1 //присвоение исходных значений для очередного шага k: = i: Х: = raas[i] ДЛЯ j:-1+l ДО n //j изменяется в диапазоне 1+1..п ЕСЛИ mas[j]<X TO НАЧ_БЛ0К_2 k: = j: x: = mas[j] К0Н_БЛ0К_2 mas[k]: = mas[i]; mas[i]: = X КОН_БЛОК_1 КОН_ПРОГ ;prg4_99.asm – программа на ассемблере сортировки прямым выбором. .data masdb 44.55.12.42.94.18.06.67;задаем массив n-$-mas X db 0 К dw 0 .code :внешний цикл – по 1 mov сх.л-1 mov si,0 cycll: push ex mov k.si:k: = i mov al,mas[si] movx.al;x: = mas[i] push si:временно сохраним i – теперь j=I+l incsi:j=I+l сложенный цикл – по j mov al,n sub ax.si mov ex,ax количество повторений внутреннего цикла по j cycl2: mov al,mas[si] cmpal,x ja ml mov k.si;k: = j moval,mas[si] movx.al:x: = mas[k] ml: inc si:j: = j+l loop cycl2 pop si mov al,mas[s1] movdi Л mov mas[di],al:mas[k]: = mas[i] mov al,x mov mas[si],al:mas[i]:-x inc si pop ex loop cycll
Первый вариант сортировки прямым обменом
Этот метод основан на сравнении и обмене пар соседних элементов до их полного упорядочивания (программа prg4_101.asm). В народе этот метод называется методом пузырьковой сортировки. Действительно, если упорядочиваемую последовательность расположить не слева направо, а сверху вниз ("слева" – это "верх"), то визуально каждый шаг сортировки будет напоминать всплытие легких (меньших по значению) пузырьков вверх.
ПРОГРАММА prg4_101 //.. //prg4_101 – программа на псевдоязыке сортировки прямым обменом 1 //Вход: mas[n] – неупорядоченная последовательность байтовых двоичных значений. //Выход: mas[n] – упорядоченная последовательность байтовых двоичных значений. //….-.. ПЕРЕМЕННЫЕ INTJ3YTE n=8: //количество элементов в сортируемом массиве INT_BYTE mas[n]; //сортируемый массив размерностью п (О..п-l) INTJYTE X: i-0; j-0 // i .j – индексы НАЧ_ПРОГ ДЛЯ i: = l ДО n-1 //i изменяется в диапазоне L.n-l НАЧ_БЛ0К_1 ДЛЯ j: = n-l ДОВНИЗ i //j изменяется в диапазоне 1+1.,П ЕСЛИ mas[j-l]< mas[j] TO НАЧ_БЛОК_2 x: = mas[j-l]; mas[j-l]: = mas[j]: mas[j]: = X К0Н_БЛ0К_'2 К0Н_БЛ0К_1 КОН_ПРОГ ;prg4_101.asm – программа на ассемблере сортировки прямым выбором 1. ПОВТОРИТЬ .data ДЛЯ j: = r ДОВНИЗ 1 //j изменяв! : задаем массив ЕСЛИ mas[j-l]< mas[j] TO masdb 44.55.12.42.94.18.06.67 НАЧ^БЛОК_1 n=$-mas x: = mas[j-l]: mas[j-l]: X db 0 КОН БЛОК 1 ДЛЯ j:-l ДОВНИЗ г //j изменяв" .code ЕСЛИ mas[j-l]< mas[j] TO НАЧ_БЛОК_2 ;внешний цикл – по 1 x: = mas[j-l]: mas[j-l]: mov ex, n – 1 КОН БЛОК 2 mov si.1 r: = k-l cycl1: ПОКА (1>г) push ex КОН_ПРОГ mov ex n 1 1 1\щ/ V \– Г\, 1 1 sub ex,si количество повторений внутреннего цикла :prg4 104.asm – программа на аса push si временно сохраним i – теперь j=n mov si,n-l cycl2::ЕСЛИ mas[j-l]< mas[j] TO.data mov al,mas[si-l]:задаем массив cmpmas[si].al masdb 44.55.12.42.94.18.06.67 ja ml n=$-mas movx.al:x=mas[j-l] X db 0 mov al,mas[si] L dw 1 mov mas[si-l],al;mas[j-l]= mas[j] R dw n mov al,x k dw n mov mas[si].al:mas[j]=x ml: dec si:цикл по j с декрементом n-i раз.code loop cycl2;….:1: = 2: г: = n: k: =n pop si cycl3::ДЛЯ j:-r ДОВНИЗ 1 inc si mov si.R: j: = R pop ex push si loop cycll sub si.L ;… .mov ex,si количество по pop si