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

[amrali]

Update 30 November 2022

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

[amrali]

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().

[amrali]

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);
  }

[amrali]

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().

[amrali]

Update 12 December 2022

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

[amrali]

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);
  }