Hi all-
Thank you for this forum. It has been very helpful for me already, although this is my first post here.
I have read the posts on how to create a bubblesort and believe I understand them, but in my exercise, I must take an array of 7 rows by 9 columns and bubblesort them into ascending order, row by row. So the bubblesort will sort each row separately. This is where I have problems. I cannot get the program to compare the right values.
In Java, in order to do what I want to do here I would:
public static void bubbleSort( int a[][], int n ) // int a[rows][columns] and int n is array.length
{
int temp = 0;
int i;
int j;
int k;
for(i = 0; i < 7; i++)
{
k = 8;
for(j = 0; j < k; j++)
{
if(a[i][j] > a[i][j+1])
{
temp = a[i][j+1];
a[i][j+1]=a[i][j];
a[i][j]=temp;
}
}
k--;
}
}
Here is my bubblesort:
sorting proc uses ax bx cx dx si di
local row:WORD
local column:WORD
local count:WORD
push bx
push si
mov row, 0
mov column, 0
mov count, LENGTHOF NUMS
sub count, 1 ; set count to 1 less than member count
mov row, 1
loop1:
xor dx, dx ; zero the changed flag
mov bx, count ; set the loop counter for member count
mov esi, OFFSET [NUMS] ; load array into ESI
loop2:
mov ax, row
mov di, ax
shl di, 3
add di, ax
add di, column
mov ax, NUMS[di] ; load first pair of numbers in array
;call WriteHexB
mov cx, ax
shl cx, 3
add cx, row
add cx, column
mov cx, ax
cmp ax, cx ; compare which is higher
jle loop3
mov ax, cx ; swap if 1st number is higher
mov cx, ax
mov dx, 1 ; set the changed flag
loop3:
add si, 2 ; step up one to compare next pair
mov ax, [esi] ; if I use a 16bit register here [si], i get an error: can't use 16bit register with 32bit address.
inc row
inc column
sub bx, 1 ; decrement the counter
jnz loop2
test dx, dx ; test if the changed flag is set.
jnz loop1 ; loop back if it is
pop si
pop bx
ret
sorting endp
I have attached the full code to this post.
Thank you for your time, I am still very much a beginner and am still learning how assembly works.
Decide if you are doing 16-bit or 32-bit code.
Provide a complete framework/context for your subroutine, including test data, external libraries, etc.
What are parameters to your subroutine, and what are local variables.
Rows and Columns of what size? How does this relate to 63 elements?
Provide the pseudo-code for your current solution, or implemented in a language you are familiar with.
The forum rules preclude homework questions.
This doesn't stop you asking questions or getting help, but your current solution seems totally broken (swapping and getting items from the array).
Review the BubbleSort algorithm again, try it in C, PASCAL, JAVA or something you know now.
well - we can help, Clive
Fran has certainly put forth a good effort
but - he is right - we do not know how "63 elements" relates to the the problem :P
welcome to the forum :U
Hi,
You are using parameters as local variables. I can give you some advice:
1.
If you want to save the push and pop use 'uses'
2. If you want to use local variables, declare them at the start of the procedure with 'local'.
Something like:
miprocedure proc uses ebx ecx edx, parameter1:dword, parameter2:word
local localvariable1:dword
local localvariable2:word
;With 'uses' you can save pushes and popes.
ret
miprocedure endp.
Please forgive my mistakes.
Thank you all for the replies. I will be home in just a few minutes and update my post. :)
EDIT: post updated.
Quote from: Fran71 on March 09, 2011, 06:56:08 PM
Thank you all for the replies. I will be home in just a few minutes and update my post. :)
The Java still looks a tad dodgy. Specifically it assumes an N x N matrix, and 7 != 9.
Another trick with BubbleSorts is that you can terminate early if no swaps occur in the pass (ie its already in sorted order).
#include <windows.h>
#include <stdio.h>
int a[7][9] = {
{ 9, 8, 7, 6, 5, 4, 3, 2, 1 },
{ 9, 4, 3, 2, 1, 8, 7, 6, 5 },
{ 9, 8, 4, 3, 2, 1, 7, 6, 5 },
{ 9, 8, 7, 6, 5, 4, 3, 2, 1 },
{ 5, 4, 3, 2, 9, 8, 7, 6, 1 },
{ 3, 2, 9, 8, 7, 6, 5, 4, 1 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }
};
int main(int argc, char **argv)
{
int i, j, k;
puts("Before");
for(i=0; i<7; i++)
{
printf("%d : ",i);
for(j=0; j<9; j++)
printf("%3d ",a[i][j]);
putchar('\n');
}
putchar('\n');
for(i=0; i<7; i++) // For all rows
{
int swapped = 0;
k = 9 - 1;
do // pass over row until all sorted or maximal
{
for(j=0; j<k; j++) // For columns
{
if (a[i][j] > a[i][j + 1])
{
int s;
s = a[i][j];
a[i][j] = a[i][j + 1];
a[i][j + 1] = s;
swapped = 1;
}
}
k--; // Pull back after each pass, as final element is highest
}
while(swapped && k);
}
puts("After");
for(i=0; i<7; i++)
{
printf("%d : ",i);
for(j=0; j<9; j++)
printf("%3d ",a[i][j]);
putchar('\n');
}
putchar('\n');
return(0);
}
ok, I see. So if I wanted the greatest number first I would set K to 0 in the second for loop, correct? So in my masm program, I'm trying to shift and add to the registers in order compare the correct column and row right now. If I use some conditional control flow directives, I could use an approach more similar to the Java one?
Like this: (pseudocode)
local variables temp, row, column, highElt // all words
set row and column to 0
mov row and column into registers
mov highElt into register
.WHILE row != 7
highElt = 8
.WHILE column != highElt
.IF array[row][column] > array[row][column+1] // I probably still have to shift and
// add in order to get these values into registers, correct?
temp = array[row][column]
array[row][column] = array[row][column+1]
array[row][column+1] = temp
.ENDIF
increase column by one
.ENDW
decrease highElt by one
increase row by one
.ENDW
Quote from: Fran71 on March 09, 2011, 10:16:14 PM
So if I wanted the greatest number first I would set K to 0 in the second for loop, correct?
No, you'd reverse the sense of this test
if (a
[j] > a[j + 1])
to
if (a[j] < a[j + 1])
I decrement K, because during each pass the largest value "bubbles" to the end of the list. And as it's iterated through every member it's not going to find a bigger value in a subsequent pass.
You have to do multiple passes, because as it goes along the value it pulls through the list might change if it encounters a bigger value. But at the end of the pass the last element it compared will be the largest.
If we reversed the comparison, as I suggested above, it is now "bubbling" the smallest value to the end. You could also play with the traversal direction if you wanted.
ok, I'm testing the procedure out when using Control flow directives:
sorting proc uses ax bx cx di edx esi
local row: WORD
local column: WORD
local highElt: WORD
mov ebx, 000000h
mov edx, 000000h
mov esi, 0
mov row, 0
mov column, 0
mov bx, row
mov cx, column
mov highElt, 7
.WHILE bx < 6
mov dx, highElt
mov column, 0
mov cx, 0
.WHILE dx != 0
.WHILE cx < dx
mov ax, NUMS[esi]
mov di, NUMS[esi+2]
call DumpRegs
.IF ax > di
mov NUMS[esi], di
mov NUMS[esi+2], ax
add esi, 2
inc cx
.ELSE
add esi, 2
inc cx
.ENDIF
dec dx
.ENDW
inc bx
.ENDW
.ENDW
ret
sorting endp
But when I run it, the program seems to not really consider the second while loop's conditions. When run, cx is increased like it should be, but in that same run highElt is decreased and bx is increased. Thus, I only get 7 iterations for the whole procedure.
EDIT: Now values are increased/decreased at the correct times but, it's still not swapping correctly..
The DEC DX, and INC BX need to be pulled out to the next level to do what you want them too.
Pseudo Code in 'C'
for(i=0; i<7; i++) // For all rows
{
k = 9 - 1;
do // pass over row until maximal
{
for(j=0; j<k; j++) // For columns
{
if (a[i][j] > a[i][j + 1])
{
int s;
s = a[i][j];
a[i][j] = a[i][j + 1];
a[i][j + 1] = s;
}
}
k--; // Pull back after each pass, as final element is highest
}
while(k);
}
32-bit register based equivalent
.386
.MODEL FLAT,C
.DATA
PUBLIC array
array DW 9, 8, 7, 6, 5, 4, 3, 2, 1 ; Test Data 7 x 9
DW 9, 4, 3, 2, 1, 8, 7, 6, 5
DW 9, 8, 4, 3, 2, 1, 7, 6, 5
DW 9, 8, 7, 6, 5, 4, 3, 2, 1
DW 5, 4, 3, 2, 9, 8, 7, 6, 1
DW 3, 2, 9, 8, 7, 6, 5, 4, 1
DW 1, 2, 3, 4, 5, 6, 7, 8, 9
.CODE
sorter PROC
push ebx ; Push registers that must be saved
push esi
push edi
lea edi,array ; EDI = offset array
mov ecx,7 ; i #rows
rowsort:
push ecx ; save row counter
mov edx,9 - 1 ; k #columns - 1
colsort1:
mov esi,edi ; Restore beginning of row
mov ecx,edx ; j = k
colsort2:
mov ax,[esi+0]
mov bx,[esi+2]
cmp ax,bx
jbe noswap ; below or equal (JAE for reverse sense)
mov [esi+0],bx
mov [esi+2],ax
noswap:
add esi,2 ; next array element
dec ecx ; j-- column
jnz colsort2
dec edx ; k--
jnz colsort1
add edi,2 * 9 ; step to next row
pop ecx ; restore row counter
dec ecx ; i-- row
jnz rowsort
pop edi
pop esi
pop ebx
ret
sorter ENDP
END
thanks. Just a few hours ago, me and a friend got our version up and running. Thanks a ton for all the help. javascript:void(0);