BubbleSort с Ассемблером
Так что для моего задания я должен написать BubbleSort на ассемблере. Я основал свой ассемблерный код на этом цикле Java BubbleSort. По какой-то причине ассемблер думает, что массивы A и B - это один большой массив, и пытается все отсортировать. Кажется, я не могу заставить его прекратить сортировку, как только это будет сделано с A, и начать все заново с B.
while (Done == 0)
{
Done = 1; // 1 represents true.
i = 0;
while ( i < N-k)
{
if (A[i] > A[i+1])
{
Help = A[i];
A[i] = A[i+1];
A[i+1] = Help;
Done = 0; // Not sorted...
}
i++;
}
k = k + 1;
}
Вот код ассемблера. Форматирование немного испортилось, но, надеюсь, все еще читаемо.
Start:
move.l #A, D0
move.l #5, D1
bsr BubbleSort * Sort array A
move.l #0, i
Print1:
move.l #5, D0
move.l i, D5
cmp.l i, D0
beq Start2 **********
move.l #A, A0
move.l i, D0
muls #4, D0
move.l 0(A0, D0.w), D0
jsr WriteInt
addi.l #1, i
bra Print1
Start2:
move.l #str, A0 ************
move.l #5, D0
jsr WriteLn
move.l #B, D0
move.l #10, D1
bsr BubbleSort * Sort array B
move.l #0, i
Print2:
move.l #10, D0
cmp.l i, D0
beq Stop
move.l #B, A0
move.l i, D0
muls #4, D0
move.l 0(A0, D0.w), D0
jsr WriteInt
addi.l #1, i
bra Print2
*D0 = address of int array to be sorted
*D1 = N
BubbleSort:
movea.l #A, A0
move.l #0, i
move.l #0, D *Done is 0
move.l D, D2 *pass Done to D2
move.l D1, N *N is number of elements
move.l #0, k
WhileStart:
cmp.l #0, D2 * compare if D2 == 0
BNE WhileEnd *if not 0, go to WhileEnd
move.l #1, D2 * D2=1
move.l #0, i * i = 0
move.l i, D3 *pass i to D3
move.l k, D4 * pass k to D4
move.l N, D7 * pass N to D7
sub.l D4,D7 * D7 = N-k
WhileStart2:
cmp.l D7, D3 *Compare i with N-k
BGE WhileEnd2
move.l i, D3
muls #4 D3
move.l 0(A0, D3.w), D5 *D5 = A[i]
move.l i, D4
add.l #1, D4 *i+1
muls #4, D4
move.l 0(A0, D4.w), D6 *D6 = A[i+1]
IfStart:
cmp.l D6, D5 *compare A[i] with A[i+1]
BLE IfEnd
move.l D5, 5000 * pass A[i] to memory location 5000
move.l D6, 0(A0, D3.w) *A[i] = A[i+1]
move.l 5000, 0(A0, D4.w) *A[i+1] = whatever was at location 5000 (old A[i])
move.l #0, D2 * D2=0 again
move.l i, D3 * passing i to D3
bra IfEnd *End of If loop
IfEnd:
move.l i, D3 *i++
add.l #1, D3
move.l D3, i
bra WhileStart2 *Go back and compare i with N-k
WhileEnd2:
move.l k, D4 *k = k + 1
add.l #1, D4
move.l D4, k
bra WhileStart * go back
WhileEnd:
rts *** I have added a rts to make sure your function returns....
1 ответ
Это сборка M68K. Вот хорошая ссылка: http://wpage.unina.it/rcanonic/didattica/ce1/docs/68000.pdf
Я вижу две семантические ошибки в вашем коде:
1) В своей процедуре пузырьковой сортировки вы никогда не используете значение, которое вызывающая сторона поместила в D0. Вы фактически жестко кодируете адрес массива, чтобы быть A с первым оператором:
movea.l #A, A0
Это предотвратит сортировку массива B. Я бы рекомендовал заменить это на:
move.l D0, A0
2) Ваша адресация элементов включает в себя дополнительный коэффициент 2. Например, вы используете D4 в качестве регистра индекса от A0 в этом фрагменте:
muls #4, D4
move.l 0(A0, D4.w), D6 *D6 = A[i+1]
Режим адресации "Адресный регистр косвенный с индексом" (с. 2.2.8 в http://www.freescale.com/files/archives/doc/ref_manual/M68000PRM.pdf) уже масштабирует содержимое вашего индексного регистра (D4) на 2, основываясь на размере 32-битного операнда (т. е. ".l" в move.l) и спецификации 16-битного индексного регистра (т. е. ".w" в D4.w). Таким образом, ваша инструкция muls должна умножаться только на 2. Еще лучше, вы можете опустить инструкцию muls и просто изменить "D4.w" на "D4.l".
Похоже, что все ваши обращения к массивам имеют одну и ту же ошибку индексации x2. Предполагая, что у вас есть A и B, объявленные в смежных областях памяти, эта ошибка индексации x2 приведет к тому, что ваша процедура сортировки, при вызове A, получит доступ к элементам B, что, разумеется, приведет к некоторому частичному упорядочению обоих массивов в процессе. И это будет выглядеть так, будто ваша процедура сортировки сортирует и А, и В одновременно.