QuickSort algo and a demonstration

[Larry Hammick]

Code Select Expand

TITLE q.asm

comment|
Makes a console program q.exe illustrating the QuickSort algo.
sample build-file:
if exist q.obj del q.obj
if exist q.exe del q.exe
\masm32\bin\ml /c /coff q.asm
if errorlevel 1 goto end
\masm32\bin\Link /SUBSYSTEM:CONSOLE q.obj
if errorlevel 1 goto end
dir q.exe
:end
|

.386
.model flat, stdcall
option casemap :none

include \masm32\include\kernel32.inc
includelib \masm32\lib\kernel32.lib

QuickSort PROTO :DWORD,:DWORD,:DWORD

.data
mydata dd " EEE"," FFF"," DDD"," AAA"," GGG"," BBB"," CCC"
myitemcount equ 7
myscratch dd myitemcount dup (?)   ;work area of the same size as the data

AmtWritten dd ?

.code
mycomparer:
      ;The input to the comparer routine is a pair (eax,edx), which in practice might be e.g. the
      ;addresses of two asciiz strings to compare lexicographically. The comparer routine returns
      ;its result in the flags. The comparer must save ebp, ebx, esi, and DF.
    cmp eax,edx     ;Trivial routine, for illustration.
    ret

Go:
    mov ebx,offset mycomparer
    invoke QuickSort, myitemcount, addr myscratch, addr mydata
    invoke GetStdHandle, -11    ; = STD_OUTPUT_HANDLE
    invoke WriteConsoleA, eax, addr mydata, 4*myitemcount, addr AmtWritten, 0
    invoke ExitProcess,0

QuickSort PROC itemcount:DWORD,scratchsite:DWORD,datasite:DWORD
LOCAL nextlower:DWORD,nexthigher:DWORD,pivotsite:DWORD
    mov eax,scratchsite
    mov nextlower,eax  ;nextlower and nexthigher are pointers for MainLoop.
    mov eax,itemcount  ;nextlower starts at the bottom of the work area and
    dec eax            ;gets incremented. nexthigher starts at the top and
    jle QuickSort_ret  ;gets decremented.
    mov ecx,eax    ;loop count
    shl eax,2      ;4 bytes per item
    add eax,scratchsite
    mov nexthigher,eax
    mov esi,datasite
    lodsd
    xchg eax,edx      ;edx will be pivot
MainLoop:       ;Mainloop puts one item in its final location and all
    lodsd       ;the others either above or below that item.
    push eax
    push edx
    push ecx
    call ebx
    pop ecx
    pop edx
    pop eax
    jb short @F        ;i.e. jump if the pivot edx is bigger than eax
    mov edi,nexthigher
    stosd
    sub nexthigher,4
    jmp short LoopMainLoop
  @@:
    mov edi,nextlower
    stosd
    mov nextlower,edi
  LoopMainLoop:
    loop MainLoop
    mov edi,nextlower ;At this point nexthigher = nextlower + 4
    mov [edi],edx     ;Poke edx into its final location
    mov pivotsite,edi
    mov eax,edi       ;Will calculate new itemcount, for the lower chunk, in eax.
    mov esi,scratchsite
    sub eax,esi
    mov edi,datasite
    mov ecx,itemcount
    rep movsd         ;copy the scratch area to the data area
    shr eax,2
        ;sort the stuff below the pivot:
        invoke QuickSort,eax,scratchsite,datasite
    ;for the stuff above the pivot, we calculate the datasite in edx,
    ;scratchsite in ecx, and itemcount in eax.
    mov eax,pivotsite
    mov ecx,eax
    add ecx,4
    mov edx,ecx
    sub edx,scratchsite
    add edx,datasite
    sub eax,scratchsite
    shr eax,2
    neg eax
    add eax,itemcount
    dec eax
        ;ready to do the stuff above the pivot:
        invoke QuickSort,eax,ecx,edx
QuickSort_ret:
    ret
QuickSort ENDP

END Go