Pages: [1]
|
 |
|
Author
|
Topic: Modified Bubble Sort (Read 8915 times)
|
veronicak5678
Guest
|
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: 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
|
|
|
Logged
|
|
|
|
FORTRANS
Member
    
Gender: 
Posts: 1147
Imagine
|
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.
|
|
|
Logged
|
|
|
|
veronicak5678
Guest
|
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.
|
|
|
Logged
|
|
|
|
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
|
|
|
Logged
|
|
|
|
veronicak5678
Guest
|
Thanks guys. I'll work on it today and probably be back with some more questions!
|
|
|
Logged
|
|
|
|
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
;--------------------------------------------------------------------------------------------
|
|
« Last Edit: December 08, 2009, 05:09:53 PM by dedndave »
|
Logged
|
|
|
|
FORTRANS
Member
    
Gender: 
Posts: 1147
Imagine
|
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
|
|
|
Logged
|
|
|
|
ilian007
Guest
|
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
|
|
|
Logged
|
|
|
|
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
|
|
|
Logged
|
|
|
|
ilian007
Guest
|
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.. ?
|
|
|
Logged
|
|
|
|
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
|
|
|
Logged
|
|
|
|
ilian007
Guest
|
Thank you dedndave will try to figure it out :)
|
|
|
Logged
|
|
|
|
ilian007
Guest
|
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 ;)
|
|
|
Logged
|
|
|
|
|
Pages: [1]
|
|
|
 |