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 Expand


include qsort.inc

; 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

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  crt_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  crt__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  crt_printf,ADDR msg
@@:
    invoke  crt_printf,ADDR format1,DWORD PTR [esi]
    add     esi,4
    dec     ebx
    jnz     @b
    ret

PrintArray ENDP


END start


[jj2007]

Fantastic, Erol :U

I could not resist the temptation to add it to MasmBasic - let me know if this is ok for you. Sorting Windows.inc takes around 0..16 ms measured with GetTickCount, which is not fast but quite acceptable.

include \masm32\MasmBasic\MasmBasic.inc

.code
start:
   Recall "\Masm32\include\Windows.inc", L$()   ; load wininc into a string array
   mov ecx, eax            ; save the linecount
   shr ecx, 2               ; just for fun, we sort only
   QSort L$(), ecx            ; one quarter of the strings (the count can not be eax)
   Open "O", #1, "SortedAscending.txt"
   xor esi, esi
   For_ n=0 To ecx-1
      .if Len(L$(n)) && esi<5000      ; we skip the empty strings, and write the first 5000
         Print #1, L$(n), CrLf$
         inc esi
      .endif
   Next
   Print Str$("%i lines written to SortedAscending.txt\n", esi)
   QSortDesc L$()         ; now sort them all but descending
   Store "SortedDescending.txt", L$()      ; and write them back to file
   Print Str$("%i lines written to SortedDescending.txt\n", L$(?))
   Exit
end start

[Vortex]

Hi Jochen,

Thanks for testing the qsort function in MasmBasic. Your new addition is a nice feature for string operations.

[jj2007]

Hi Erol,
At first, I was pessimistic because MB stores strings as 8-byte address+len pairs, but it turns out that qsort can handle that with the width parameter. Thanks again :U

QSort MACRO ArrID, ct:=<0>
  push ct
  push ArrID
  call MbQSortP
ENDM

QSortDesc MACRO ArrID, ct:=<0>
  push ct
  push -ArrID
  call MbQSortP
ENDM

; Reference: MSDN
; The comparison function used by msvcrt qsort function must have the C calling convention
MbQSortP [/b]proc   ; based on Erol's code
  mov eax, [esp+4]   ; array ID
  mov edx, MbQsAsc   ; default is ascending
  test eax, eax
  .if Sign?
   neg eax               ; ArrID negativ: descending
   mov edx, MbQsDesc
  .endif
  push ecx      ; save a reg
  push edx      ; proc address
  mov edx, [MbArrTable+4*eax]
[/b]  mov eax, [esp+16]   ; # of elements to be sorted
  test eax, eax
  jne @F
  mov eax, [edx]      ; if zero, take them all from array table
@@:
  push 8   ; width is 2*DWORD
  push eax
  lea edx, [edx+16]   ; ptr to first string in array
  push edx
  call crt_qsort
  add esp, 4*4      ; crt functions want it that way ;-)
  pop ecx      ; restore a valid register ;-)
  retn 8
MbQSortP endp

MbQsAsc proc      ; C arg1:DWORD,arg2:DWORD
   mov eax, [esp+4]      ; arg1
   mov edx, [esp+8]      ; arg2
   invoke crt__stricmp, DWORD PTR [eax], DWORD PTR [edx]
   retn
MbQsAsc endp

MbQsDesc proc   ; C arg1:DWORD,arg2:DWORD
   mov eax, [esp+4]      ; arg1
   mov edx, [esp+8]      ; arg2
   invoke crt__stricmp, DWORD PTR [eax], DWORD PTR [edx]
;   To sort an array in decreasing order, reverse the sense of
;   greater than and less than in the comparison function:
   neg eax
   retn
MbQsDesc endp

[Vortex]

This new demo performs a binary search with msvcrt bsearch to find the zero based index of the element Orange :

Code Select Expand


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