NASM - The Netwide Assembler

NASM Forum => Example Code => Topic started by: Mathi on February 26, 2012, 06:19:25 PM

Title: Quicksort (Integers) - Win32 Console Demo.
Post by: Mathi on February 26, 2012, 06:19:25 PM
Quicksort of Integers.   (win32 console - Nagoa version).

Example code: (Attached it too).

qsort.asm

Code: [Select]
;; PSEUDO CODE
;; http://en.wikipedia.org/wiki/Quicksort#In-place_version
;; 
;;function quicksort(array, 'left', 'right')
;;
;; // If the list has 2 or more items
;; if 'left' < 'right'
;;
;; // See "Choice of pivot" section below for possible choices
;; choose any 'pivotIndex' such that 'left' = 'pivotIndex' = 'right'
;;
;; // Get lists of bigger and smaller items and final position of pivot
;; 'pivotNewIndex' := partition(array, 'left', 'right', 'pivotIndex')
;;
;; // Recursively sort elements smaller than the pivot
;; quicksort(array, 'left', 'pivotNewIndex' - 1)
;;
;; // Recursively sort elements at least as big as the pivot
;; quicksort(array, 'pivotNewIndex' + 1, 'right')
;;
;;left is the index of the leftmost element of the array
;;right is the index of the rightmost element of the array (inclusive)
;;number of elements in subarray = right-left+1
;;
;;function partition(array, 'left', 'right', 'pivotIndex')
;; 'pivotValue' := array['pivotIndex']
;; swap array['pivotIndex'] and array['right']  // Move pivot to end
;; 'storeIndex' := 'left'
;; for 'i' from 'left' to 'right' - 1  // left = i < right
;; if array['i'] < 'pivotValue'
;; swap array['i'] and array['storeIndex']
;; 'storeIndex' := 'storeIndex' + 1
;; swap array['storeIndex'] and array['right']  // Move pivot to its final place
;; return 'storeIndex'
;;     
;;     

;; ----------  qsort.asm ------------
;;
;; nasm -fobj qsort.asm
;; alink -c -oPE -subsys con qsort
;;

%include "nagoa-20120202.inc"

;%macro API 2                                   ;Function , Library
; import %1 %2
; extern %1
;%endmacro

%macro Wait_For_Keypress 0

push dword 4
push dword GMEM_FIXED | GMEM_ZEROINIT
CALL [GlobalAlloc]
mov ebx,eax
mov edi,ebx
push ebx

push dword STD_INPUT_HANDLE
CALL [GetStdHandle]
mov edx,eax

pop ebx
push edx

push ebx
push eax
CALL [GetConsoleMode]

and byte [ebx], 0xFF ^ (ENABLE_LINE_INPUT | ENABLE_ECHO_INPUT)
pop edx

push edx
push dword [ebx]
push dword edx
CALL [SetConsoleMode]
pop edx


push dword NULL
push dword ebx
push dword 1
push dword ebx
push dword edx
CALL [ReadConsoleA]
%endmacro

API GlobalAlloc,kernel32.dll
API GlobalFree,kernel32.dll
API ExitProcess,kernel32.dll
API GetStdHandle,kernel32.dll
API WriteFile, kernel32.dll
API GetCommandLineA, kernel32.dll
API ReadConsoleA, kernel32.dll
API GetConsoleMode, kernel32.dll
API SetConsoleMode, kernel32.dll


global ..start
segment .bss USE32

buffer resb 32

segment .data USE32

inarray dd 10,454,34,64,23,12,6454,3423,1345,235,25,32          ;;INPUT ARRAY - (SAMPLE DATA)
UBOUND EQU (($-inarray)/4) - 1  ;; calculate Upper Bound of the array (11 in this case)

consolehdl dd 0
newline db 10
newlineLEN equ 1
byteswritten dd 0


segment .code USE32 class=code

;;;;;START PROGRAM;;;;

..start:

call    GetStdHandle,STD_OUTPUT_HANDLE
mov     [consolehdl], eax   

loccall QuickSort,inarray,0,UBOUND   ;;Call from the Main program

;;Now Print the sorted array

mov esi,inarray
xor ebx,ebx
while ebx,le,UBOUND
lodsd
int2str eax,buffer

pusha
call    WriteFile,[consolehdl],buffer,edx,byteswritten,0   ;;Print Number to the screen.
call    WriteFile,[consolehdl],newline,1,byteswritten,0    ;;Print NewLine.
popa

inc ebx
wend

Wait_For_Keypress

call ExitProcess,0

;;;;;END PROGRAM;;;;

proc QuickSort,array,left,right
stack pivot,4,pivotNew,4
mov eax,[@right]
if [@left],l,eax
mov [@pivot],eax   ;; we chose last index as the pivot
loccall partition,[@array],[@left],[@right],[@pivot] 
mov [@pivotNew],eax

;;Recursively sort elements smaller than the pivot
mov ebx,[@pivotNew]
dec ebx
loccall QuickSort,[@array], [@left],ebx

;; Recursively sort elements at least as big as the pivot
mov ebx,[@pivotNew]
inc ebx
loccall QuickSort,[@array], ebx, [@right]
endif

endproc


proc partition,array,left,right,pivot
stack pivotValue,4,storeIndex,4

mov edi,[@array]
mov ebx,[@pivot]
lea edi,[edi + ebx *4]
mov eax,[edi]
mov [@pivotValue],eax

;;we are skipping the below step, because we chose the last index as the pivotIndex.
;;swap array['pivotIndex'] and array['right']  // Move pivot to end

mov eax,[@left]
mov [@storeIndex],eax


mov ebx,[@left]
ForLoop:
cmp ebx,[@right]
jge EndFor

mov esi,[@array]
lea esi,[esi + ebx*4]
mov ecx,[esi]

if ecx,l,[@pivotValue]

mov edi,[@array]
mov edx,[@storeIndex]
lea edi,[edi + edx*4]
mov eax,[edi]

mov [esi],eax
mov [edi],ecx

inc dword [@storeIndex]
endif

inc ebx

jmp ForLoop
EndFor:     

mov edi,[@array]
mov ebx,[@storeIndex]
lea edi,[edi + ebx*4]
mov eax,[edi]     

mov esi,[@array]
mov ebx,[@right]
lea esi,[esi + ebx*4]
mov ecx,[esi]

mov [edi],ecx
mov [esi],eax

return [@storeIndex]

endproc