Modified Bubble Sort

The MASM Forum Archive 2004 to 2012

Welcome, Guest. Please login or register.
December 05, 2019, 07:42:05 PM

MASM32 Downloads
Forum Links and Website
Archived Old Forum Files
Links for VC and MASM

128553 Posts in 15254 Topics by 684 Members
Latest Member: mottt

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:

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

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.

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.

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

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

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

Hi,

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

Quote

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

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

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

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

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

Thank you dedndave will try to figure it out :)

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