SA-MP Forums Archive
[Plugin] Non-recursive QuickSort implementation for PAWN - Printable Version

+- SA-MP Forums Archive (https://sampforum.blast.hk)
+-- Forum: SA-MP Scripting and Plugins (https://sampforum.blast.hk/forumdisplay.php?fid=8)
+--- Forum: Plugin Development (https://sampforum.blast.hk/forumdisplay.php?fid=18)
+--- Thread: [Plugin] Non-recursive QuickSort implementation for PAWN (/showthread.php?tid=647061)


Non-recursive QuickSort implementation for PAWN - ThePhenix - 29.12.2017

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/
********************************************/
/********************************************
                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

Re: Non-recursive QuickSort implementation for PAWN - IlanZ - 29.12.2017

Interesting, good job.

Re: Non-recursive QuickSort implementation for PAWN - rfr - 30.12.2017

interesting good.

Re: Non-recursive QuickSort implementation for PAWN - Kaperstone - 30.12.2017

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?

Re: Non-recursive QuickSort implementation for PAWN - ThePhenix - 30.12.2017

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.

Re: Non-recursive QuickSort implementation for PAWN - khosim24h - 03.10.2018

Great Post . Thanks for sharing