koros0111/RadixSort
Watch
1
0
Fork
You've already forked RadixSort
 0
forked from amrali/RadixSort
Code Pull requests Activity
RadixSort/RadixSort.mqh
amrali 97e2b571c5
2026-08-02 14:43:06 +03:00

543 lines
24 KiB
MQL5
Raw Permalink Blame History

//+------------------------------------------------------------------+
//| RadixSort.mqh |
//| Copyright © 2026, Amr Ali |
//| https://www.mql5.com/en/users/amrali |
//+------------------------------------------------------------------+
#property copyright "Copyright © 2026, Amr Ali"
#property link "https://www.mql5.com/en/users/amrali"
#property version "1.50"
#property description "Ultra-fast sorting for numeric arrays of any dimension."
#ifdef __MQL4__
#property strict
#endif
#ifndef RADIX_SORT_UNIQUE_HEADER_ID_H
#define RADIX_SORT_UNIQUE_HEADER_ID_H
//+------------------------------------------------------------------+
//| RadixSort |
//+------------------------------------------------------------------+
//| Sorts the values in the first dimension of a multidimensional |
//| numeric array in the ascending order. |
//| |
//| Arguments: |
//| array[] |
//| [in][out] : Numeric array for sorting. |
//| descending |
//| [in] : false for ascending order (default), true for |
//| descending order. |
//| |
//| Return value: true if successful, otherwise false. |
//| |
//| Note: |
//| An array is always sorted in the ascending order irrespective |
//| of the AS_SERIES flag value. |
//| |
//| The function accepts any-dimensional arrays of simple type |
//| (char, uchar, short, ushort, int, uint, long, ulong, bool, |
//| color, datetime, float, double) as a parameter. However, |
//| sorting is always applied to the first (zero) dimension. |
//| |
//| Performance: |
//| This is a highly-optimized implementation of LSD RadixSort |
//| in MQL using radix-256 (8-bit digits). This could be useful |
//| for sorting huge numeric arrays with millions of numbers. |
//| It is at least 3-10 times faster than built-in ArraySort(). |
//| |
//| IEEE-754 floating-point ordering: |
//| Floating-point values are sorted by transforming their raw |
//| IEEE-754 bit representation into an order-preserving integer |
//| key. This produces the correct numerical ordering for all |
//| finite values without performing floating-point comparisons. |
//| Special values follow their IEEE-754 bit ordering: negative |
//| NaNs precede -infinity, positive NaNs follow +infinity, and |
//| -0.0 sorts before +0.0. |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSort(T &arr[], const bool descending = false)
{
const int n = ArraySize(arr);
//--- match the behavior of the built-in ArraySort():
//--- empty array -> false, single-element -> true.
if(n < 2)
return(n == 1);
//--- fall back to ArraySort() for a small array
if(n < 128)
return(ArraySort(arr) &&
(!descending || ArrayReverse(arr)));
//--- temporary array to hold the sorted numbers
T temp[];
if(ArrayResize(temp, n) != n)
return(false);
//--- frequency histogram of the i-th byte
int counts[sizeof(T)][256];
//--- reset counts array
ZeroMemory(counts);
//--- compute frequency histograms of the i-th byte
for(int i = 0; i < n; i++)
{
const T ai = arr[i];
for(uchar col = 0; col < sizeof(T); col++)
{
uchar key = extract_key(ai, (uchar)(col << 3));
++counts[col][key];
}
}
//--- checks whether the array is dynamic, in order to utilize ArraySwap() optimization on MT5.
const bool dynamic = ArrayIsDynamic(arr);
//--- sort the array elements one byte at a time in LSD order (right-most byte first)
for(uchar col = 0; col < sizeof(T); col++)
{
const uchar shift = col << 3;
//--- determine if any columns can be skipped
//--- for each digit, check if all the elements are in the same bucket.
//--- If so, we can skip the whole digit. Instead of checking all the buckets,
//--- we pick first key and check whether the bucket contains all the elements.
if(counts[col][extract_key(arr[0], shift)] == n)
{
continue;
}
//--- transform counts to offset (ranks)
int offset = 0;
for(int i = 0; i < 256; i++)
{
int old_count = counts[col][i];
counts[col][i] = offset;
offset += old_count;
}
//--- gather forwards in temp (stable sort, elements ordered by i-th byte)
for(int i = 0; i < n; i++)
{
uchar key = extract_key(arr[i], shift);
temp[counts[col][key]++] = arr[i];
}
//--- copy back from temp to arr
CopyOrSwap(arr, temp, dynamic);
}
//---
if(descending)
return(ArrayReverse(arr));
//---
return(true);
}
//+------------------------------------------------------------------+
//| RadixSort |
//+------------------------------------------------------------------+
//| Sorts the values in the first dimension of a multidimensional |
//| numeric array in the ascending order. |
//| |
//| Function overload for two-dimensional numeric arrays. |
//| |
//| Arguments: |
//| array[] |
//| [in][out] : Numeric array for sorting. |
//| descending |
//| [in] : false for ascending order (default), true for |
//| descending order. |
//| |
//| Return value: true if successful, otherwise false. |
//| |
//| Remark: |
//| This is a stable sort: rows with equal first-column values |
//| retain their original relative order. |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSort(T &arr[][], const bool descending = false)
{
const int n = ArraySize(arr);
const int na = ArrayRange(arr, 0);
const int nb = ArrayRange(arr, 1);
//--- match the behavior of the built-in ArraySort():
//--- empty array -> false, single-element -> true.
if(na < 2)
return(na == 1);
//--- fall back to ArraySort() for a small array
if(na < 128)
return(ArraySort(arr) &&
(!descending || ArrayReverse(arr)));
//--- allocate temporary buffer to hold numbers from the first column
T first_col[];
if(ArrayResize(first_col, na) != na)
return(false);
for(int i = 0; i < na; i++)
first_col[i] = arr[i][0];
//--- calculate order of numbers in the first dimension
int indices[];
if(!RadixSortIndices(first_col, indices))
return(false);
//--- flatten the multidimensional numeric array into a properly-sized buffer
T flat[];
if(ArrayResize(flat, n) != n)
return(false);
if(ArrayCopy(flat, arr) != n)
return(false);
//--- sort the flattened multidimensional array using the sorted indices.
for(int i = 0; i < na; i++)
{
const int index = indices[i];
for(int j = 0; j < nb; j++)
arr[i][j] = flat[nb * index + j];
}
//---
if(descending)
return(ArrayReverse(arr));
//---
return(true);
}
//+------------------------------------------------------------------+
//| RadixSort |
//+------------------------------------------------------------------+
//| Sorts the values in the first dimension of a multidimensional |
//| numeric array in the ascending order. |
//| |
//| Function overload for three-dimensional numeric arrays. |
//| |
//| Arguments: |
//| array[] |
//| [in][out] : Numeric array for sorting. |
//| descending |
//| [in] : false for ascending order (default), true for |
//| descending order. |
//| |
//| Return value: true if successful, otherwise false. |
//| |
//| Remark: |
//| This is a stable sort: rows with equal first-column values |
//| retain their original relative order. |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSort(T &arr[][][], const bool descending = false)
{
const int n = ArraySize(arr);
const int na = ArrayRange(arr, 0);
const int nb = ArrayRange(arr, 1);
const int nc = ArrayRange(arr, 2);
//--- match the behavior of the built-in ArraySort():
//--- empty array -> false, single-element -> true.
if(na < 2)
return(na == 1);
//--- fall back to ArraySort() for a small array
if(na < 128)
return(ArraySort(arr) &&
(!descending || ArrayReverse(arr)));
//--- allocate temporary buffer to hold numbers from the first column
T first_col[];
if(ArrayResize(first_col, na) != na)
return(false);
for(int i = 0; i < na; i++)
first_col[i] = arr[i][0][0];
//--- calculate order of numbers in the first dimension
int indices[];
if(!RadixSortIndices(first_col, indices))
return(false);
//--- flatten the multidimensional numeric array into a properly-sized buffer
T flat[];
if(ArrayResize(flat, n) != n)
return(false);
if(ArrayCopy(flat, arr) != n)
return(false);
//--- sort the flattened multidimensional array using the sorted indices.
for(int i = 0; i < na; i++)
{
const int index = indices[i];
for(int j = 0; j < nb; j++)
for(int k = 0; k < nc; k++)
arr[i][j][k] = flat[nc * (nb * index + j) + k];
}
//---
if(descending)
return(ArrayReverse(arr));
//---
return(true);
}
//+------------------------------------------------------------------+
//| RadixSort |
//+------------------------------------------------------------------+
//| Sorts the values in the first dimension of a multidimensional |
//| numeric array in the ascending order. |
//| |
//| Function overload for four-dimensional numeric arrays. |
//| |
//| Arguments: |
//| array[] |
//| [in][out] : Numeric array for sorting. |
//| descending |
//| [in] : false for ascending order (default), true for |
//| descending order. |
//| |
//| Return value: true if successful, otherwise false. |
//| |
//| Remark: |
//| This is a stable sort: rows with equal first-column values |
//| retain their original relative order. |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSort(T &arr[][][][], const bool descending = false)
{
const int n = ArraySize(arr);
const int na = ArrayRange(arr, 0);
const int nb = ArrayRange(arr, 1);
const int nc = ArrayRange(arr, 2);
const int nd = ArrayRange(arr, 3);
//--- match the behavior of the built-in ArraySort():
//--- empty array -> false, single-element -> true.
if(na < 2)
return(na == 1);
//--- fall back to ArraySort() for a small array
if(na < 128)
return(ArraySort(arr) &&
(!descending || ArrayReverse(arr)));
//--- allocate temporary buffer to hold numbers from the first column
T first_col[];
if(ArrayResize(first_col, na) != na)
return(false);
for(int i = 0; i < na; i++)
first_col[i] = arr[i][0][0][0];
//--- calculate order of numbers in the first dimension
int indices[];
if(!RadixSortIndices(first_col, indices))
return(false);
//--- flatten the multidimensional numeric array into a properly-sized buffer
T flat[];
if(ArrayResize(flat, n) != n)
return(false);
if(ArrayCopy(flat, arr) != n)
return(false);
//--- sort the flattened multidimensional array using the sorted indices.
for(int i = 0; i < na; i++)
{
const int index = indices[i];
for(int j = 0; j < nb; j++)
for(int k = 0; k < nc; k++)
for(int l = 0; l < nd; l++)
arr[i][j][k][l] = flat[nd * (nc * (nb * index + j) + k) + l];
}
//---
if(descending)
return(ArrayReverse(arr));
//---
return(true);
}
//+------------------------------------------------------------------+
//| RadixSortIndices |
//+------------------------------------------------------------------+
//| Populate an array of indices[] in the order that would sort |
//| the values of a numeric array[] in the ascending order. |
//| |
//| Arguments: |
//| array[] : Array with numeric values to sort |
//| indices[] : Array for sorted indices |
//| descending : false for ascending order (default), true for |
//| descending order. |
//| |
//| Return value: true if successful, otherwise false. |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSortIndices(const T &arr[], int &indices[], const bool descending = false)
{
const int n = ArraySize(arr);
//--- prepare array to hold the indices of the numbers
if(ArrayResize(indices, n) != n)
return(false);
for(int i = 0; i < n; i++)
indices[i] = i;
//--- allocate temporary buffer to hold the numbers
T temp[];
if(ArrayCopy(temp, arr) != n)
return(false);
//--- calculate order of numbers in the ascending order
if(!ParallelRadixSort(temp, indices, descending))
return(false);
//---
return(true);
}
//+------------------------------------------------------------------+
//| ParallelRadixSort |
//+------------------------------------------------------------------+
//| The function sorts array[] and items[] simultaneously using |
//| the RadixSort algorithm. The items[] array (e.g. structs or |
//| other data) is reordered according to the ascending numeric |
//| values in array[]. |
//| |
//| Arguments: |
//| array[] : Array with numeric keys to sort |
//| items[] : Array of items (e.g. structs) to sort by keys |
//| descending : false for ascending order (default), true for |
//| descending order. |
//| |
//| Return value: true if successful, otherwise false. |
//+------------------------------------------------------------------+
template<typename T,typename TItem>
bool ParallelRadixSort(T &arr[], TItem &items[], const bool descending = false)
{
const int n = ArraySize(arr);
//--- match the behavior of the built-in ArraySort():
//--- empty array -> false, single-element -> true.
if(n < 2)
return(n == 1);
if(ArraySize(items) != n)
return(false);
//--- temporary array to hold the sorted numbers (keys)
T temp[];
if(ArrayResize(temp, n) != n)
return(false);
//--- temporary array to hold the sorted items
TItem items2[];
if(ArrayResize(items2, n) != n)
return(false);
//--- frequency histogram of the i-th byte
int counts[sizeof(T)][256];
//--- reset counts array
ZeroMemory(counts);
//--- compute frequency histograms of the i-th byte
for(int i = 0; i < n; i++)
{
const T ai = arr[i];
for(uchar col = 0; col < sizeof(T); col++)
{
uchar key = extract_key(ai, (uchar)(col << 3));
++counts[col][key];
}
}
//--- checks whether the arrays are dynamic, in order to utilize ArraySwap() optimization on MT5.
const bool dynamic_arr = ArrayIsDynamic(arr);
const bool dynamic_items = ArrayIsDynamic(items);
//--- sort the array elements one byte at a time in LSD order (right-most byte first)
for(uchar col = 0; col < sizeof(T); col++)
{
const uchar shift = col << 3;
//--- determine if any columns can be skipped
//--- for each digit, check if all the elements are in the same bucket.
//--- If so, we can skip the whole digit. Instead of checking all the buckets,
//--- we pick first key and check whether the bucket contains all the elements.
if(counts[col][extract_key(arr[0], shift)] == n)
{
continue;
}
//--- transform counts to offset (ranks)
int offset = 0;
for(int i = 0; i < 256; i++)
{
int old_count = counts[col][i];
counts[col][i] = offset;
offset += old_count;
}
//--- gather forwards in temp (stable sort, elements ordered by i-th byte)
for(int i = 0; i < n; i++)
{
uchar key = extract_key(arr[i], shift);
offset = counts[col][key]++;
temp[offset] = arr[i];
items2[offset] = items[i];
}
//--- copy back from temp to arr
CopyOrSwap(arr, temp, dynamic_arr);
CopyOrSwap(items, items2, dynamic_items);
}
//---
if(descending)
{
return(ArrayReverse(arr)
&& ArrayReverse(items));
}
//---
return(true);
}
//+------------------------------------------------------------------+
//| Copies or swaps the contents of two arrays. |
//| |
//| Used internally by RadixSort() and ParallelRadixSort() to |
//| reduce memory copying and improve performance. This helper |
//| uses ArraySwap() for dynamic arrays on MQL5. |
//+------------------------------------------------------------------+
template<typename T>
void CopyOrSwap(T &dst[], T &src[], const bool is_dynamic)
{
#ifdef __MQL5__
if(is_dynamic)
ArraySwap(dst, src);
else
ArrayCopy(dst, src);
#else
ArrayCopy(dst, src);
#endif
}
//+------------------------------------------------------------------+
//| Returns an integer key for "signed" primitive types. |
//+------------------------------------------------------------------+
// https://github.com/eloj/radix-sorting#-key-derivation
// http://stereopsis.com/radix.html
// https://stackoverflow.com/a/42304235/4208440
// https://github.com/skarupke/ska_sort/blob/master/ska_sort.hpp
// https://github.com/JakubValtar/radsort/blob/master/src/scalar.rs
uchar extract_key(const char value, const uchar shift)
{
return (uchar)((value ^ 0x80) >> shift);
}
uchar extract_key(const short value, const uchar shift)
{
return (uchar)((value ^ 0x8000) >> shift);
}
uchar extract_key(const int value, const uchar shift)
{
return (uchar)((value ^ 0x80000000) >> shift);
}
uchar extract_key(const long value, const uchar shift)
{
return (uchar)((value ^ 0x8000000000000000) >> shift);
}
//+------------------------------------------------------------------+
//| Returns an integer key for float. |
//| |
//| flip a float for sorting |
//| finds SIGN of fp number. |
//| if it's 1 (negative float), it flips all bits |
//| if it's 0 (positive float), it flips the sign only |
//| |
//| The IEEE-754 bit pattern is transformed into a monotonically |
//| increasing unsigned integer key while preserving the total order |
//| of all finite floating-point values. |
//| |
//| - Negative values sort before positive values. |
//| - -0.0 sorts before +0.0. |
//| - NaNs are ordered by their raw bit patterns. |
//| - Positive and negative infinities are ordered naturally. |
//+------------------------------------------------------------------+
uchar extract_key(const float value, const uchar shift)
{
union _f { float value; uint bits; } f;
f.value = value;
//--- extend the sign bit to the whole width with arithmetic
//--- right shift to get a flip mask 0xffffffff or 0x80000000
return (uchar)((f.bits ^ (((int)f.bits >> 31) | 0x80000000)) >> shift);
}
//+------------------------------------------------------------------+
//| Returns an integer key for double. |
//+------------------------------------------------------------------+
uchar extract_key(const double value, const uchar shift)
{
union _d { double value; ulong bits; } d;
d.value = value;
//--- extend the sign bit to the whole width with arithmetic
//--- right shift to get a flip mask 0xffffffff or 0x80000000
return (uchar)((d.bits ^ (((long)d.bits >> 63) | 0x8000000000000000)) >> shift);
}
//+------------------------------------------------------------------+
//| Returns an integer key for other "unsigned" primitive types. |
//| uchar, ushort, uint, ulong, bool, color, datetime. |
//+------------------------------------------------------------------+
template<typename T>
uchar extract_key(const T value, const uchar shift)
{
return (uchar)(value >> shift);
}
//+------------------------------------------------------------------+
#endif // #ifndef RADIX_SORT_UNIQUE_HEADER_ID_H
View git blame Copy permalink