Modified Bubble Sort

[veronicak5678]

Hello everyone-

We are modifying a bubble sort to be more efficient. First, we need to make it quit after it is sorted (no swaps made.) Second, we need to make the passes shorter by one every time. Third, we need to alternate directions of passes, so the first time it will go from 1 to 10, second pass will go from 9 to 1, third will go from 2 to 9, fourth will go from 8 to 2...

We need to compound the mods so the third has all 3. I have done the first 2, but I am having trouble with the third. I almost had it working, but it was awful. I split it into two functions, one for up and one for down, but this seems like a bad idea. Here is the sort to modify:

Code Select Expand

SORT2 PROC NEAR



SUB CX, CX
QUITLOOP:
CMP SWAPOCURRED, 0
JE DONE
DEC ELEMENTS
OUTERLOOP:
SUB DI, DI
MOV SWAPOCURRED, 0
CMP CX, 6

JGE DONE
INNERLOOP:
CMP DI, ELEMENTS
JGE INNERLOOPDONE
MOV AL, ARR2[DI]
MOV BL, ARR2[DI+1]
INC COMPARES
CMP AL, BL
JG SWAPELEMENTS
INC DI
JMP INNERLOOP
SWAPELEMENTS:
INC SWAPS
MOV SWAPOCURRED, 1
MOV ARR2[DI+1], AL
MOV ARR2[DI], BL
INC DI
JMP INNERLOOP
INNERLOOPDONE:
INC CX
JMP QUITLOOP
DONE:

RET
SORT2 ENDP

[FORTRANS]

Hi,

   While you could hold the sort direction, starting and ending
values in variables, and swap them around between passes,
that seems tricky.  Before reading your second paragraph, I
thought having separate sort up and sort down routines would
be easier to code.  Sorry for the lack of concrete help.

Regards,

Steve N.

[veronicak5678]

That's OK, I'm just glad to have at least one response! If I don't get any more, I think I will have to split it up because I can't think of anything else.

[dedndave]

Steve has the right idea
write the sort code as a seperate routine
in the real world, it would be a PROC so that it could be called again if needed
pass the array address and length to the PROC
remember - keep all of your registers busy
i might do it something like this...

AX = AL and AH read bytes
that way, you can pick up 2 bytes at a time (MOV AX,[SI]) and compare them in register with CMP AL,AH
then, MOV [SI],AX to write swapped byte pairs together
BX = bottom address of array
CX = swap flag - initialize CX to 0 - set CL to 1 when a swap is made
DX = top address of array (minus 1 or 2, i think)
SI = array index
DI = direction step value: 1 if scanning upward, -1 if scanning downward
BP = stack frame base pointer to access the passed parameters

step SI with ADD SI,DI
when SI = DX, you are at the end of a scan, then do the following:
DEC CX to reset it to 0 - if it isn't 0 after the DEC, it means the flag wasn't set and you are done
SUB DX,DI to decrease the count next time
(when DX holds the bottom address, DI will be -1, so it will add one to the bottom or subtract one from the top)
XCHG BX,DX to swap ends
NEG DI to swap directions

you get the idea

[veronicak5678]

Thanks guys. I'll work on it today and probably be back with some more questions!

[dedndave]

Veronica,
let me start by saying that this task may be more of a test to see who is getting outside help - lol
there are a few subtleties to this code that i don't think he expects anyone to solve
or - perhaps he needs a bubble sort, and wants us to help him - lol
the thing is, it is more important for you to get the thought process of how to write code rather than getting the code, itself

the first step was planning the register usage as in the previous post
after i wrote the loop, i changed the use of a few registers to better suit my code
but, the planning stage was still important

after that, i wrote the loops, without any initialization code
i wanted the loop to flow well before i set up the registers
when i first wrote it, the swaps at the top of the loop were at the bottom, followed by a JMP
i re-arranged the outer loop to make it more efficient
also, notice that accesses to memory inside the loop are kept to a minimum
almost everything inside the loop is done "in register" or "register to register"
that makes the code run faster, and usually makes the loop smaller, as well

then, i wrote the initialization code so that the registers would be set up, according to what the loops needed
at that point, i changed some registers around to better suit the PROC CALL
also, a couple little "glitches" had to be fixed in case the array size is 0, 1, or 2 bytes long
i had to be careful not to overscan the array, while still making sure it sorted all of it, no matter the size

i wouldn't say this is really an "advanced" routine, but it is tricky enough that a new coder would have problems with it
most bubble sorts i have seen are recursive - that is, they are designed to be routines that call themselves
i am not sure that recursive bubble sorts are any faster - lol
it may just be they needed a task to write a recursive routine - i would think permutation would be a better task for that

anyways, here is the routine i wound up with - i have done minimal testing on it and it seems to work ok

;--------------------------------------------------------------------------------------------

BSort   PROC   NEAR
;
;Byte Array Bubble Sort
;
;Call With: SI = address of array
;           CX = size of array in bytes
;
;  Returns: the array is sorted, lower values at lower addresses
;
;           all general registers are used and not saved
;
;-------------------------------------------

        jcxz    BSort4            ;if array size = 0, sort is done

        dec     cx                ;count to last byte
        jz      BSort4            ;if array size = 1, sort is done

        mov     bp,1              ;bp = 1 - used to set the swap flag
        xor     dx,dx             ;dx = 0 - initial swap flag
        cmp     cx,bp             ;if cx = 1, there are only 2 bytes
        ja      BSort0            ;more than 2 - skip the adjustment

        mov     bp,dx             ;if only 2 bytes, we want one pass, so flag = 0

BSort0: add     cx,si             ;cx = top address
        dec     si                ;adjust for the skip (DI gets ADD'ed before 1st pass)
        mov     di,-1             ;di = 1 for up, -1 for down (gets NEG'ed before 1st pass)
        mov     bx,si             ;bx = bottom address (gets XCHG'ed with CX before 1st pass)
        dec     bx                ;adjust for "one less" (DI gets SUB'ed before 1st pass)

BSort1: sub     bx,di             ;one less next time
        xchg    bx,cx             ;swap ends
        neg     di                ;switch direction
        add     si,di             ;skip one - already did that pair
        add     si,di             ;skip another one - one less next time

BSort2: mov     ax,[si]           ;get 2 bytes
        cmp     al,ah             ;do they need to be swapped ?
        jbe     BSort3            ;no - next address

        xchg    al,ah             ;yes - swap them
        mov     dx,bp             ;set the swap flag
        mov     [si],ax           ;store the swapped byte pair

BSort3: add     si,di             ;step in the current direction
        cmp     si,bx             ;are we at the end ?
        jnz     BSort2            ;no - next pair

        dec     dx                ;yes - clear the sort flag if it is 1
        jz      BSort1            ;if the sort flag was 1 before DEC, we are not done

BSort4: ret                       ;exit the routine

BSort   ENDP

;--------------------------------------------------------------------------------------------

[FORTRANS]

Hi,

   A nice description of the process.  Usually the description
of programming makes it sound more like making sausage.

most bubble sorts i have seen are recursive - that is, they are designed to be routines that call themselves
i am not sure that recursive bubble sorts are any faster - lol
i

   Really?  I guess I've been looking at a different set of
bubble sorts.  Of course, until recently, FORTRAN did not
allow recursion.  A lot of quicksort routines are recursive.
And a lot of the time, a recursive routine is slower, due to
the calling overhead.  YMMV.

Regards,

Steve

[ilian007]

I believe it should be something like ArrLow[DI]+1 and ArrUp[DI]-1 in the loop and do Compares and swaps in the loop. And put them in CountCmp CountSwaps ... He wants us to count numbers of swaps and compares.

Still on the Fibonacci problem. Will start that one later

[dedndave]

BSort2: mov     ax,[si]
        inc word ptr CompareCount ;line added to count compares
        cmp     al,ah
        jbe     BSort3

        inc word ptr SwapCount    ;line added to count swaps
        xchg    al,ah
        mov     dx,bp
        mov     [si],ax

BSort3: add     si,di
        cmp     si,bx
        jnz     BSort2

        inc word ptr PassCount    ;line added to count passes
        dec     dx
        jz      BSort1

[ilian007]

Hi Dedndave,

can you explain a little bit more in details what NEG DI do ? maybe that is what I asked when i wanted to Swap arrays. I am seeing instead of swaping arrays you are changing directions of DI.. ?

[dedndave]

we use the value in DI to control which direction we are "scanning" for byte-pairs
when DI is +1, we step the address upward
when we get to the high-address end of the scan, we NEG DI (making it -1) to go downward
when we get to the low-address end of the scan, we NEG DI (making it +1) to go upward again
at the end of a scan, we test the last byte pair
once we switch directions, we may skip one pair because we just tested that pair before the switch
because that skip is a different direction at each end, we use DI to make the adjustment

when i am trying to figure out what loops are doing, i find it helpful to read the inner loop first
in fact, i often write code that way
this is the inner loop

BSort2: mov     ax,[si]           ;get 2 bytes
        cmp     al,ah             ;do they need to be swapped ?
        jbe     BSort3            ;no - next address

        xchg    al,ah             ;yes - swap them
        mov     dx,bp             ;set the swap flag
        mov     [si],ax           ;store the swapped byte pair

BSort3: add     si,di             ;step in the current direction
        cmp     si,bx             ;are we at the end ?
        jnz     BSort2            ;no - next pair

as you can see, DI is only used to step the index register inside the inner loop

once you understand that loop, then figure out the outer loop

BSort1: sub     bx,di             ;one less next time
        xchg    bx,cx             ;swap ends
        neg     di                ;switch direction
        add     si,di             ;skip one - already did that pair
.
. inner loop
.
        dec     dx                ;yes - clear the sort flag if it is 1
        jz      BSort1            ;if the sort flag was 1 before DEC, we are not done

[ilian007]

Thank you dedndave will try to figure it out :)

[ilian007]

DednDave,

I can only tell that this is a very smart move to use the "NEG" command. :)

u are acutally first time adding the next time substracting ;)