### Author Topic: Quicksort (Integers) - Win32 Console Demo.  (Read 13113 times)

#### Mathi

• Jr. Member
• Posts: 82
• Country:
##### Quicksort (Integers) - Win32 Console Demo.
« 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]%endmacroAPI GlobalAlloc,kernel32.dllAPI GlobalFree,kernel32.dllAPI ExitProcess,kernel32.dllAPI GetStdHandle,kernel32.dllAPI WriteFile, kernel32.dllAPI GetCommandLineA, kernel32.dllAPI ReadConsoleA, kernel32.dllAPI GetConsoleMode, kernel32.dllAPI SetConsoleMode, kernel32.dllglobal ..startsegment .bss USE32buffer resb 32segment .data USE32inarray 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 0newline db 10newlineLEN equ 1byteswritten dd 0segment .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,rightstack 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] endifendprocproc partition,array,left,right,pivotstack 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`