Faster table sorting with quick-sort algorithm

Code Samples and Tips
1

Here are some sorting subroutines that implement the quick-sort algorithm. This is an iterative implementation derived from Robert Sedgewick and Jon Bentley 3-way partition quick-sort algorithm.

Implemented in 9.3 Basic.

Usage:

QuickSortFloat(Array To Sort, Starting Index, Ending Index, Descending);
QuickSortInt32(Array To Sort, Starting Index, Ending Index, Descending);
QuickSortInt64(Array To Sort, Starting Index, Ending Index, Descending);
QuickSortString(Array To Sort, Starting Index, Ending Index, Descending);

These subroutines have a substantial performance improvement over the other sorting subroutines I have found for Opto devices. They also sort in situ, so have a minimal memory impact.

Below is the measured sort algorithm performance comparison on an R1.
Last column is running on PAC Sim.
Times are in milliseconds.

Table Length  R1 Bubble  R1 Insertion  R1 Quick  Sim i7-4510U Quick
5             3          2             3
10            15         6             7
25            64         32            25        1
50            274        111           64        1
100           1,004      430           142       3
200           4,127      1,778         340       8
400           15,997     6,838         720       18
800                                    1,550     40
1,600                                  3,670     73
3,200                                  7,927     170
6,400                                  16,946    350
10,000                                 27,829    567
20,000                                           1,204
40,000                                           2,645
80,000                                           5,547
160,000                                          11,608
320,000                                          24,347
640,000                                          52,337
1,000,000                                        84,782

Quicksort9.3Basic.zip (11 KB)

2 Likes
2

If anyone wants to do some testing/benchmark on their hardware, here is how I generated a bunch of random table data.

For Integers:

for nIterator=nStartIndex to nEndIndex step 1
  ntBigTable[nIterator] = (nMaxValue - nMinValue) * GenerateRandomNumber() + nMinValue;
next

For Floats:

if(nDecimals==0) then
  nDecimals=1;
endif

for nIterator=nStartIndex to nEndIndex step 1
  ftBigTable[nIterator] = ((nMaxValue - nMinValue) * GenerateRandomNumber() + nMinValue) / (10.0 * nDecimals);
next

For Strings:

if(nMaxStringLength == 0) then
  nMaxStringLength=10;
endif
for nIterator=nStartIndex to nEndIndex step 1
  nStringLength = (nMaxStringLength - 1) * GenerateRandomNumber() + 1;
  sTemp="";
  for nIterator2=0 to nStringLength step 1
    sTemp += Chr(25 * GenerateRandomNumber() + 65);
  next
 stBigTable[nIterator] = sTemp;
next
3

Whoa! Nice bump in speed… Thanks a heap for offering this code up Philip.
Also nice way to make data…

Cheers.

4

Hey Ben, I was just poking around through the subs, nice work! I was wondering, there’s a note in here about no recursive subroutines in Opto. I think I remember hearing that calling subs from subs was coming up soon, is recursion also in the future?

5

From what I have learned, recursion will not be a feature in 9.5

6

Thanks, philip, for building and sharing those sub! And your are correct, while the upcoming 9.5 release will support subs calling subs, it will NOT support sub calling self or any fancier version of recursion (e.g. sub A calls sub B, which calls sub A).

BTW, aec_dan, where do you see this “note in here” you mention about “recursive subroutines in Opto”? Was that perhaps inside philip’s nifty sorting subs? (Which I’ve not yet had a chance to try?)

Just making sure we get all the appropriate docs updated for 9.5…

7

The comment is in a “text tool” comment in the subroutine - explaining why it has to be iterative.

One interesting observation I had in testing this, was that the R1 was faster at sorting strings (random 8 character length) than integers, which surprised me. Any ideas why that might be? Strings were slower on PAC sim.

8

Yep, Mary, I was referring to a note in phillip’s subs.