| Ambuoroko |
Oct 29th, 2006 6:21 PM |
Quicksort Error
As part of a homework assignment for an Assembly Language class I am taking, I had to implement a sorting algorithm in assembly language. I decided to try to implement quicksort, and I'm very close to having it, but I'm having a very strange error and simply have no idea what it could be.
The quicksort procedure works just fine most of the time. However, if quicksort is called on an array that is in reverse sorted order, the program outputs a whole bunch of garbage values or just freezes up. But, if for example in an array of 10 items, I change the portion to be sorted from 0 to 9, and instead sort 1 to 9, it works fine even for a list in reverse order. If anyone has any ideas the help would be greatly appreciated. I am using Turbo Assembler at school and MASM at home for the project, if that helps
Thanks,
John
-----
:
; Quicksort procedure - Adapted from C++ to Assembly. Original algorithm was taken from
; programs 7.1 and 7.2 of "Algorithms in C++" by Robert Sedgewick.
; This procedure sorts the array called "myArray", from position si to position di.
; To call it, place the index of the first number to be sorted in si and the index of
; the last number to be sorted in di, then call quicksort.
; This quicksort uses the first element of the subarray as the pivot, which is extremely
; bad for nearly-sorted lists. Also, insertion sort may have been better for a small list
; as the program required. But it seemed that quicksort would be a more useful procedure
; to have around for later programs
quicksort proc
cmp si,di ; The base case is an array of one or fewer elements
jae done ; In this case, si = di. Do nothing and return
jmp continue ; Jump over "done" and continue with quicksort
done: ; Done label
ret ; Return
continue: ; Quicksort
mov al, myArray[di] ; Store the last element in al to use as the pivot
mov first, si ; Store si in first
mov last, di ; Store di in last
dec si ; Decrement si to one less than first
; Move through the array from left to right until finding an element
; that is greater than the pivot
moveLeftSide:
inc si ; Increment si. The first time through, this sets si to the first element again
cmp myArray[si], al ; If myArray[si] is less than to the pivot,
jb moveLeftSide ; Keep looking
; Move through the array from right to left until finding an element
; that is less than the pivot
moveRightSide:
dec di ; Decrement di (move left)
cmp di,first ; To prevent "falling off" the left end of the array,
je swapIt ; once di == first, stop looking (go to swapIt)
cmp myArray[di], al ; If myArray[si] is greater than the pivot
ja MoveRightSide ; keep looking
cmp si, di ; If si "passes" di, then the partitioning step is done
jae swapIt ; Go to swapIt and put the pivot in its final position
; After finding two elements that are in the "wrong" side, switch them
mov ch, myArray[di] ; Put DI in ch (temp variable)
mov cl, myArray[si] ; Put SI in cl (temp variable)
mov myArray[di], cl ; Move cl (what was SI) into DI
mov myArray[si], ch ; Move ch (what was DI) into SI
; Continue the partitioning step indefinitely until conditions in the above code end the loop
jmp moveLeftSide
; Once the list has been divided into a less-than-pivot half and a greater-than-pivot
; half, the pivot can be put into it's permanent place, which is between the two halves.
; Switch the pivot with the first element greater than the pivot, which is in myArray[si]
swapIt:
mov di, last ; Move last back into di to get position of the pivot
mov ch, myArray[si] ; Use ch and cl again as temporary variables
mov cl, myArray[di] ; to switch the pivot myArray[di] into
mov myArray[si], cl ; its final position, which will be at
mov myArray[di], ch ; myArray[si]
mov pivotIndex, si ; Store the position of the pivot in pivotIndex
mov si, first ; Move first into si
mov di, last ; Move last into di
mov ax, pivotIndex ; Move the pivotIndex into ax
push si ; Push SI, DI and AX onto the stack to save
push di ; them across the resursive call
push ax ; to quicksort
mov di, ax ; The first recursive call will begin at first (already in SI)
dec di ; and end at 1 position before the pivot (which is already in place)
call quicksort ; Call quicksort to recursively sort the left half of the list
pop ax ; Restore the values of SI, DI and AX
pop di ; in reverse order of the order they were placed on the stack
pop si ; to get back the first and last positions and the position of the pivot
mov si, ax ; The second recursive call will begin at 1 position after the pivot,
inc si ; and end at the last position (which is already in DI)
call quicksort ; Call quicksort to recursively sort the right half of the list
ret ; Return
quicksort endp
|
