Quick sort with msvcrt function qsort

[Vortex]

The MS VC++ run-time library exports a function named qsort to perform quick sort operations on numbers and strings. This function is not the fastest one but it may be interesting to use it for practical programming purposes :

Code: [Select]

; Source code assembled with Pelles Macro Assembler, Version 6.00.4

; Reference :
; http://msdn.microsoft.com/en-us/library/aa272872%28VS.60%29.aspx

; The comparaison function used by msvcrt qsort function must have
; the C calling convention

include qsort.inc

CompareProc PROTO C :DWORD,:DWORD

NUMB_OF_ELEMENTS equ 8


.data

str1    db 'Orange',0
str2    db 'Cherry',0
str3    db 'Strawberry',0
str4    db 'Apple',0
str5    db 'Fig',0
str6    db 'Apricot',0
str7    db 'Pear',0
str8    db 'Peach',0

StrTabl dd str1,str2,str3,str4,str5,str6,str7,str8

msg     db 'List of fruits in alphabetical order',13,10
        db '====================================',13,10,13,10,0

format1 db '%s',13,10,0


.code

start:

    invoke  qsort,ADDR StrTabl,NUMB_OF_ELEMENTS,\
            SIZEOF DWORD,ADDR CompareProc

    call    PrintArray

    invoke  ExitProcess,0
   

CompareProc PROC C arg1:DWORD,arg2:DWORD

    mov     eax,arg1
    mov     ecx,arg2
    invoke  _stricmp,DWORD PTR [eax],DWORD PTR [ecx]

; To sort an array in decreasing order, reverse the sense of
; greater than and less than in the comparison function :
;
;   neg     eax

    ret

CompareProc ENDP


PrintArray  PROC uses esi ebx

    mov     ebx,NUMB_OF_ELEMENTS
    mov     esi,OFFSET StrTabl

    invoke  printf,ADDR msg
@@:
    invoke  printf,ADDR format1,DWORD PTR [esi]

    add     esi,4
    dec     ebx
    jnz     @b
    ret

PrintArray ENDP


END start

[Vortex]

Another example with qsort and bsearch :

Code: [Select]

include BinSearch.inc

; References :
; http://msdn.microsoft.com/en-us/library/aa272872%28VS.60%29.aspx
; http://msdn.microsoft.com/en-us/library/aa272036%28VS.60%29.aspx

; The comparaison function used by msvcrt qsort function must have
; the C calling convention

CompareProc PROTO C :DWORD,:DWORD

NUMB_OF_ELEMENTS equ 8


.data

str1    db 'Orange',0
str2    db 'Cherry',0
str3    db 'Strawberry',0
str4    db 'Apple',0
str5    db 'Fig',0
str6    db 'Apricot',0
str7    db 'Pear',0
str8    db 'Peach',0

key     db 'Orange',0
PtrKey  dd key

StrTabl dd str1,str2,str3,str4,str5,str6,str7,str8

msg     db 'List of fruits in alphabetical order',13,10
        db '====================================',13,10,13,10,0

format1 db '%s',13,10,0
format2 db 13,10,'0 based index of %s = %d',0

.code

start:

    invoke  qsort,ADDR StrTabl,NUMB_OF_ELEMENTS,\
            SIZEOF DWORD,ADDR CompareProc
           
    call    PrintArray

    invoke  bsearch,ADDR PtrKey,ADDR StrTabl,NUMB_OF_ELEMENTS,\
            SIZEOF DWORD,ADDR CompareProc

    mov     edx,eax
    sub     edx,OFFSET StrTabl
    shr     edx,2

    invoke  printf,ADDR format2,DWORD PTR [eax],edx

    invoke  ExitProcess,0
   

CompareProc PROC C arg1:DWORD,arg2:DWORD

    mov     eax,arg1
    mov     ecx,arg2
    invoke  _stricmp,DWORD PTR [eax],DWORD PTR [ecx]

; To sort an array in decreasing order, reverse the sense of
; greater than and less than in the comparison function :
;
;   neg     eax

    ret

CompareProc ENDP


PrintArray  PROC uses esi ebx

    mov     ebx,NUMB_OF_ELEMENTS
    mov     esi,OFFSET StrTabl

    invoke  printf,ADDR msg
@@:
    invoke  printf,ADDR format1,DWORD PTR [esi]
    add     esi,4
    dec     ebx
    jnz     @b
    ret

PrintArray ENDP


END start


[Vortex]

Attached is the UNICODE version of the quick sort demo.

[Vortex]

This version eliminates the _stricmp function :

Code: [Select]

CompareProc PROC C USES esi edi arg1:DWORD,arg2:DWORD

    mov     eax,arg1
    mov     ecx,arg2
    mov     esi,DWORD PTR [eax]
    mov     edi,DWORD PTR [ecx]
    mov     edx,-1
@@:
    add     edx,1
    movzx   eax,BYTE PTR [esi+edx]
    test    eax,eax
    jz      l2
    cmp     al,BYTE PTR [edi+edx]
    je      @b
l1:
    sub     al,BYTE PTR [edi+edx]
    jc      l3
    mov     eax,1
l2:         
    ret
l3:
    xor     eax,eax
    mov     eax,-1

    ret

CompareProc ENDP