Issue with Bubblesort of words

[Fran71]

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:

Code Select Expand


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:

Code Select Expand


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.

[clive]

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.

[dedndave]

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

[untio]

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.

[Fran71]

Thank you all for the replies.  I will be home in just a few minutes and update my post.  :)

EDIT: post updated.

[clive]

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).

Code Select Expand

#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);
}


[Fran71]

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)

Code Select Expand



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



[clive]

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.

[Fran71]

ok, I'm testing the procedure out when using Control flow directives:

Code Select Expand



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..

[clive]

The DEC DX, and INC BX need to be pulled out to the next level to do what you want them too.

[clive]

Pseudo Code in 'C'

Code Select Expand

  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

Code Select Expand

        .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


[Fran71]

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);