QuickSort algorithm

[iZ!]

I converted an old non-recursive QuickSort program written in BASIC into ml64 asm.
It doesn't sort the original array, but it writes indices of the array into another array in an ascending order.

Entry points: SortLng, SortULng, SortDbl and SortAny

The first three expect 3 arguments to be passed:
RCX - Pointer to the beginning of array of 64-bit integers or REAL8 to sort
RDX - Pointer to the beginning of array of 32-bit integers which will hold indices of the array in first argument. Its size must be at least the number given in R8
R8 - Number of items to examine in the array

The call destroys RAX, RCX, RDX, R8, R9, R10 and R11 registers.

EDIT: Example demonstrating sorting of Int64 and REAL8 arrays:

Code Select Expand


includelib ArrayMan.lib

SortULng proto ;  Unsigned Int64 array ptr, indicesPtr, lenOfArray
SortLng proto ;  QWORD array ptr, indicesPtr, lenOfArray
SortDbl proto ;  REAL8 array ptr, indicesPtr, lenOfArray

.data

array1 dq 20, 19, 18, 17, 16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9
array2 real8 20.0, 19.0, 18.0, 17.0, 16.0, 15.0, 14.0, 13.0, 12.0, 11.0, 10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0, -1.0, -2.0, -3.0, -4.0, -5.0, -6.0, -7.0, -8.0, -9.0
indx dd 30 dup(0)

.code

mainP proc

mov rcx,offset array1
mov rdx,offset indx
mov r8,30 ; array of 30 elements

call SortLng ;sort int64 array, result in 'indx'

mov rcx,offset array2
mov rdx,offset indx
mov r8,30 ; array of 30 elements

call SortDbl ;sort REAL8 array, result in 'indx'

ret

mainP endp




For sorting any kind of array, see the example is in my next post.

-------------------------

I've also posted this on GitHub.

[Vortex]

Hello,

Could you post an example demonstrating the usage of the library?

[iZ!]

Here's the deal: write your own delegate functions to compare array items. This gives you the ability to sort any kind of array.
All three delegate functions are called with index in EAX. The procedures have to find the array element based on this index.

1st procedure: stores the value of array element with index passed in EAX
2nd procedure: Compares that value with array element with index in EAX, returns True if less
3rd procedure: Compares the stored value with array element with index in EAX, returns True if bigger

Code Select Expand


includelib ArrayMan.lib
SortAny proto ; lenOfArray, indicesPtr, ldValueMethod, cmpMethodLT, cmpMethodGT
option casemap:none

.data
array1 dq 20, 19, 18, 17, 16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9

indx dd 30 dup(0)

.code

.data

array1 dq 20, 19, 18, 17, 16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9
indx dd 30 dup(0)

.code


mainP proc

push rsi
push rdi
push rbx

mov rsi,offset array1 ; In this example, we'll use
mov rdi,offset indx   ; RSI and RDI to point to bases of arrays


;call the QuickSort procedure
mov rcx,30 ; array of 30 elements
mov rdx,offset indx
mov r8,loadValueToCmp ; load pointer to procedure
mov r9,isItLess ; load pointer to procedure
mov r10,isItMore ; load pointer to procedure
call SortAny

;result in 'indx' at [RDI]

pop rbx
pop rdi
pop rsi
ret

mainP endp


loadValueToCmp proc
; To-do: Store array item with index given in EAX. This value will be compared with other array items in the next two procedures.
;You can use RAX, RDI, RSI, R8 or FPU registers to store the pivot value.
;These registers will retain their values during any subsequent calls to LTmethod and GTmethod procedures.
;All other registers need to be preserved on return from all the procedures.
;If you don't know what pivot is and you don't want to dive into QuickSort algorithm to find out,
;just imagine it as a variable which holds one of the array items you will need to compare to other array elements in the two mentioned procedures.

;Example here demonstrates loading an 8-byte integer from an array into R8

SHL RAX, 3 ; multiply by 8 to get the offset in memory, since we are dealing with 8-byte integers
mov r8,qword ptr [rsi+rax] ;rsi points to base of array1

ret

loadValueToCmp endp


isItMore proc

;  To-Do: Compare item with index in EAX with pivot value
; and return True if pivot is greater than array item
    SHL RAX, 3
    cmp r8,[rsi+rax]
    jg isGreater
    xor ax,ax
    ret

isGreater: 
    mov ax,-1
    ret

isItMore endp


isItLess proc
;  To-Do: Compare item with index in EAX with pivot value
; and return True(in AX) if pivot is less than array item
  SHL RAX, 3
  cmp r8,[rsi+rax]
  jl isLess
  xor rax,rax
  ret
 
isLess:
   
    mov ax,-1
    ret

isItLess endp




Example of sorting an array of REAL8 numbers:

Code Select Expand


includelib ArrayMan.lib
option casemap:none

SortAny proto ; lenOfArray, indicesPtr, ldValueMethod, cmpMethodLT, cmpMethodGT

.data

array1 real8 20.0, 19.0, 18.0, 17.0, 16.0, 15.0, 14.0, 13.0, 12.0, 11.0, 10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0, -1.0, -2.0, -3.0, -4.0, -5.0, -6.0, -7.0, -8.0, -9.0
indx dd 30 dup(0)

.code


SortReal8Example proc

mov rsi,offset array1 ; In this example, we'll use
mov rdi,offset indx   ; RSI and RDI to point to base of arrays


;call the QuickSort procedure
mov rcx,30 ; array of 30 elements
mov rdx,offset indx
mov r8,loadReal8ToCmp ; load pointer to procedure
mov r9,isItLessR8 ; load pointer to procedure
mov r10,isItMoreR8 ; load pointer to procedure

call SortAny
;result in 'indx' at [RDI]

ret

SortReal8Example endp


loadReal8ToCmp proc

  fstp st(0)
  SHL RAX, 3 ; multiply by 8, since we are dealing with 8-byte real numbers
  fld real8 ptr[rsi+rax]
ret

loadReal8ToCmp endp

isItMoreR8 proc

   SHL RAX, 3
    fcom real8 ptr [rsi+rax]
    fnstsw ax
   and    ax, 0100011100000000B
    jz     isGreaterR
    xor ax,ax
    ret

isGreaterR: 
    not ax
    ret


isItMoreR8 endp


isItLessR8 proc

  SHL RAX, 3
   fcom real8 ptr [rsi+rax]
   fnstsw ax
    and    ax, 0100011100000000B
    cmp    ax, 100h
; I'm cheating here by assuming there's no invalid FP values in the array
    ret
isItLessR8 endp




For a VB.NET example that sorts 1000 randomly generated numbers(using ArrayMan.dll), please refer to this GitHub post. You can also change the number of integers to generate and sort by editing a single line.

[iZ!]

Here's the library(.lib) which doesn't refer the .dll.

[guga]

Here's the library(.lib) which doesn't refer the .dll.

Can you convert it to 32 bits so we can also test for non64 version ? This looks much similar to one JJ did. I wonder how fast it is to be compared with the others in the forum. Doing a benchmark could be good :)

[iZ!]

Can you convert it to 32 bits so we can also test for non64 version ?

I don't think I will. I like x64 because I can store frequently accessed variables into registers.
This project fitted x64 perfectly, since there were many of such variables. There's no .DATA block in my code :)

[iZ!]

I've updated the file in my initial post and the example. It supports real8 arrays now.

Update: Oops, I forgot to write a RET statement in my code, therefore SortDbl proc didn't work.

Update2: Still doesn't work.. Will update soon.

[iZ!]

Please download v3.zip from the first post and see the updated example. By writing three short procedures, you can now sort any array.

[jj2007]

Code Select Expand

POLINK: error: Symbol 'lup1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'doLup1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'aut1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'aut2' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'aut0' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'lup1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'doLup1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'aut1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'aut2' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'aut0' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'lup1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'doLup1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'aut1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'aut2' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'aut0' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'lup01' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'lup0' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'ni0' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'ni1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.
POLINK: error: Symbol 'ni2' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.

[Mikl__]

Sort algorithms in Assembler:

• Bubble sort, Cocktail sort, Heapsort, Direct Power, Direct Pick, Shell sort, Hoare (Quick Sort) (MASM)
• Insertion sort (FASM)

[iZ!]

jj2007: Thanks for sharing that, strangely I didn't get those errors. Try if this is any better. This lib exports only SortAny procedure.

[jj2007]

This one assembles fine. It throws a runtime error then, but that's probably because of my setup.

[iZ!]

This one assembles fine. It throws a runtime error then, but that's probably because of my setup.

Thanks for testing, does the error occur during the call to SortAny procedure?

[jj2007]

Thanks for testing, does the error occur during the call to SortAny procedure?

Yes.

Code Select Expand

0000000140001849   | 48 8B C2                 | mov rax,rdx                       |
000000014000184C   | E8 DF FF FF FF           | call 140001830                    |
0000000140001851   | FF 15 59 1B 00 00        | call qword ptr ds:[1400033B0]     | <<<<<<<<<<<<<<<<<<<
0000000140001857   | 44 8B D9                 | mov r11d,ecx                      |
000000014000185A   | 41 FF CB                 | dec r11d                          |
000000014000185D   | 44 8B E2                 | mov r12d,edx                      |

[iZ!]

This is a call to loadValueToCmp proc. Seems like your code is blocking its access from outside procedures. Only a guess...