[ThePhenix]

Non-recursive QuickSort implementation for PAWN

If you don't know what QuickSort is, you should check:
https://en.wikipedia.org/wiki/Quicksort

Overview:
So, basically the other day I was playing around with some sorting algorithms in PAWN and I came across this non-recursive implementation of the quicksort algorithm by Darel Rex Finley. You can find it in the following link:

http://alienryderflex.com/quicksort/

I performed some benchmarks and it seems to be the fastest non-recursive quicksort implementation I have encountered so far. I decided not to implement the algorithm in PAWN code as it will of course execute slower.

Functions:

PHP Code:

/********************************************
    Non-recursive implementation of the quicksort algorithm.
    Available at:
    http://alienryderflex.com/quicksort/nl66...1.68380794
********************************************/
/********************************************
                Natives
********************************************/
/* quicksort_asc(array[], elements = sizeof(array));
    
    Sorts a single dimension array in ascending order.
    
    * Returns 
         - 0: function failed to execute
         - 1: function executed successfully
    * params
        - array[]: the array you desire to sort.
        - elements: the number of elements starting at index 0 that you wish to sort. (not final index).
*/
native quicksort_asc(array[], elements = sizeof(array));
/* quicksort_desc(array[], elements = sizeof(array));
    
    Sorts a single dimension array in descending order.
    
    * Returns 
         - 0: function failed to execute.
         - 1: function executed successfully.
    * params
        - array[]: the array you desire to sort.
        - elements: the number of elements starting at index 0 that you wish to sort (not final index).
*/
native quicksort_desc(array[], elements = sizeof(array));
/********************************************
                Useful Macros 
********************************************/
/* quicksort_ascEx(array[], start, end);
    
    Sorts a single dimension array in ascending order starting at a specific index.
    
    * Returns 
         - 0: function failed to execute
         - 1: function executed successfully
    * params
        - array[]: the array you desire to sort.
        - start: the starting index
        - end: the final index
*/
#define quicksort_ascEx(%0,%1,%2)     (quicksort_asc(%0[%1],%2-%1+1))
/* quicksort_descEx(array[], start, end);
    
    Sorts a single dimension array in descending order starting at a specific index.
    
    * Returns 
         - 0: function failed to execute
         - 1: function executed successfully
    * params
        - array[]: the array you desire to sort.
        - start: the starting index
        - end: the final index
*/
#define quicksort_descEx(%0,%1,%2)  (quicksort_desc(%0[%1],%2-%1+1)) 


Examples:

Ascending order:

PHP Code:

new array[20] = {43, 99, -10, 0, 1, 9, 8, 7, 1939944, 1323324, 123455, -1234555, 21476834, 55433, -12345593, 1444, 23444, 9999, 77, -244};
    quicksort_asc(array); 


Output:

Code:

array[0] = -12345593
array[1] = -1234555
array[2] = -244
array[3] = -10
array[4] = 0
array[5] = 1
array[6] = 7
array[7] = 8
array[8] = 9
array[9] = 43
array[10] = 77
array[11] = 99
array[12] = 1444
array[13] = 9999
array[14] = 23444
array[15] = 55433
array[16] = 123455
array[17] = 1323324
array[18] = 1939944
array[19] = 21476834

Starting at index 1 up to index 3:

PHP Code:

new array[5] = {4, 9, 10, 1, 2};
    quicksort_ascEx(array, 1, 3); 


Outputs:

Code:

array[0] = 4
array[1] = 1
array[2] = 9
array[3] = 10
array[4] = 2

Descending order:

PHP Code:

new array[20] = {43, 99, -10, 0, 1, 9, 8, 7, 1939944, 1323324, 123455, -1234555, 21476834, 55433, -12345593, 1444, 23444, 9999, 77, -244}; 
    quicksort_desc(array); 


Outputs:

Code:

array[0] = 21476834
array[1] = 1939944
array[2] = 1323324
array[3] = 123455
array[4] = 55433
array[5] = 23444
array[6] = 9999
array[7] = 1444
array[8] = 99
array[9] = 77
array[10] = 43
array[11] = 9
array[12] = 8
array[13] = 7
array[14] = 1
array[15] = 0
array[16] = -10
array[17] = -244
array[18] = -1234555
array[19] = -12345593

Starting at index 1 up to index 3:

PHP Code:

new array[5] = {4, 9, 10, 1, 2};
    quicksort_descEx(array, 1, 3); 


Outputs:

Code:

array[0] = 4
array[1] = 10
array[2] = 9
array[3] = 1
array[4] = 2

Download
Source

[IlanZ]

Interesting, good job.

[rfr]

interesting good.

[Kaperstone]

Would love to see benchmarks both for small arrays and big.

By the way, you have posted only numerical sorting, can it sort alphabetically as well?

[ThePhenix]

You can actually as for instance the character 'B' means the same as 66 or 'Z' means the same as 90. Taking into account that, you could do:

PHP Code:

new chararray[9] = {'D', 'C', 'B', 'H', 'A', 'F', 'I', 'E', 'G'};
quicksort_asc(chararray); 


If you use the %c specifier on printf the output would be:

Code:

chararray[0] = A
chararray[1] = B
chararray[2] = C
chararray[3] = D
chararray[4] = E
chararray[5] = F
chararray[6] = G
chararray[7] = H
chararray[8] = I

I might do some speed tests later on.

[khosim24h]

Great Post . Thanks for sharing