TITLE Quick Sort functions

;; qSort.asm
;;
;; The following is an implementation of quick sort in assembly which
;; will sort a list of dwords in c

;; use make.bat to compile this, should work on lab machines.


.386
.model flat

public qSort

arrSize  equ [ebp+08]
arrayPtr equ [ebp+12]

.code
qSort PROC near


  push ebp
  mov ebp, esp


  mov esi, arrayPtr  ; esi will be the start of the array
  mov edi, arrSize   ; edi will be the end of the array
  dec edi            ; 0 base the size
  shl edi, 2         ; Multiply arrSize by 4
  add edi, arrayPtr
  mov eax, arrayPtr
  mov ebx, DWORD PTR [esi]

findPlace:                   ; Start by trying to find where pivot goes
  
  add  esi, 4
  cmp  ebx, DWORD PTR [esi]  ; see if the item is less
  jbe  findSwap
  mov  eax, esi              ; Now we know we have a val lower than ebx here
  cmp  esi, edi              ; See if we have more to check
  jae  found
  jmp  findPlace


findSwap:
  cmp  DWORD PTR [edi], ebx  ; See if the end is above the pivot
  jb   doSwap
  sub  edi, 4                ; otherwise move edi backwards
  cmp  esi, edi              ; see if we finished searching the array
  jae  found    
  jmp  findSwap              ; and check again

doSwap:
  mov  ecx, DWORD PTR [edi]  ; Now do the swap
  xchg ecx, DWORD PTR [esi]
  mov  DWORD PTR [edi], ecx
  mov  eax, esi
  jmp  findPlace

found:
  cmp  eax, arrayPtr         ; See if our pivot moved and we need to change
                             ; our item
  jbe  done                  ; don't swap if that's the case
  xchg eax, esi              ; Load our pivot place
  xchg ebx, DWORD PTR [esi]  ; Put our pivot val into the pivot place
  mov  esi, arrayPtr         ; Finish the change
  mov  DWORD PTR [esi], ebx  
  xchg eax, esi

done:

  ;; Here we've put the first item in it's proper spot, edi and esi should
  ;; both point to the proper spot and all items below and above are properly
  ;; configured. Now we just return the pivot place, and let the C++ function
  ;; do the recursion if nescessary, I know I'm taking the easy way out but
  ;; oh well ;-)
  
  sub  esi, arrayPtr      ; work out the number of items left.
  shr  esi, 2             ; div 4 to get the right number.

  mov  eax, esi           ; and set the pass back value

  pop ebp
  ret

qSort ENDP
end