Libraries: Radix sort (The fastest numeric sort) - page 2

 

Update 30 November 2022

Added validation tests for RadixSort() against MQL's ArraySort().

 

Update 4 December 2022

Added support for multidimensional numeric array. However, sorting is always applied to the first (zero) dimension. 

RadixSort() can completely replace MQL's ArraySort().
 

Update 7 December 2022

Updated the ParallelRadixSort() function to sort two parallel arrays of different types, simultaneously.

template<typename TKey,typename TItem>
bool ParallelRadixSort(TKey &[], TItem &[]);

The first argument: an array containing the keys.

The second argument: array of the target items to sort (based on the keys).

Example:

#include "RadixSort.mqh"

void OnStart()
  {
//--- Parallel arrays for position tickets and opening times
   ulong tickets[];
   datetime times[];
   
//--- Fill arrays with positions information
   int total = PositionsTotal();
   ArrayResize(tickets, total);
   ArrayResize(times, total);
   for(int i = 0; i < total; i++)
     {
      tickets[i] = PositionGetTicket(i);
      times[i] = PositionGetInteger(POSITION_TIME);
     }
     
//--- Sort position tickets by their opening times
      ParallelRadixSort(times, tickets);
  }
 

Update 9 December 2022

The algorithm falls back to ArraySort() if the array contains less than some threshold of items (currently 128).

Updated validation tests for RadixSort() against MQL's ArraySort().


 

Update 12 December 2022

Updated validation tests for RadixSort() against MQL's ArraySort().

 
amrali #:

Updated the ParallelRadixSort() function to sort two parallel arrays of different types, simultaneously.

The first argument: an array containing the keys.

The second argument: array of the target items to sort (based on the keys).

Another usage for the ParallelRadixSort() function is that it could be used to shuffle arrays:

#include "RadixSort.mqh"

//+------------------------------------------------------------------+
//| ArrayShuffle                                                     |
//| Randomizes the order of array elements in-place.                 |
//+------------------------------------------------------------------+
template<typename T>
void ArrayShuffle(T &array[])
  {
//--- prepare an array of random numbers
   int n = ArraySize(array);
   int random[];
   ArrayResize(random, n);
   for(int i = 0; i < n; i++)
     {
      random[i] = MathRand();
     }
//--- shuffle input by sorting of random numbers
   ParallelRadixSort(random, array);
  }

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
void OnStart()
  {
   string fruits[] = {"orange", "banana", "apple", "peach", "grape"};
   ArrayShuffle(fruits);
   ArrayPrint(fruits);
  }