Quicksort of Integers. (win32 console - Nagoa version).
Example code: (Attached it too).
qsort.asm
;; 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
