//+------------------------------------------------------------------+
//| HeapSort.mq5 |
//| 2019 - 2021, dimitri pecheritsa |
//| https://www.mql5.com/en/users/dmipec |
//+------------------------------------------------------------------+
//+------------------------------------------------------------------+
//| heap sort - array sorting algorithm |
//| best - n log n, average - n log n, worst - n log n |
//| memory - 1, stable - no, method - selection |
//| heapsort is a much more efficient version of selection sort. it |
//|also works by determining the largest (or smallest) element of |
//|the list, placing that at the end (or beginning) of the list, |
//|then continuing with the rest of the list, but accomplishes this |
//|task efficiently by using a data structure called a heap, a |
//|special type of binary tree. once the data list has been made |
//|into a heap, the root node is guaranteed to be the largest (or |
//|smallest) element. when it is removed and placed at the end of |
//|the list, the heap is rearranged so the largest element remaining |
//|moves to the root. using the heap, finding the next largest |
//|element takes o(log n) time, instead of o(n) for a linear scan as |
//|in simple selection sort. this allows heapsort to run in o(n log |
//|n) time, and this is also the worst case complexity. |
//| although somewhat slower in practice on most machines than a |
//|well-implemented quicksort, it has the advantage of a more |
//|favorable worst-case o(n log n) runtime. heapsort is an in-place |
//|algorithm, but it is not a stable sort. |
//| heapsort was invented by j. w. j. williams in 1964. this was |
//|also the birth of the heap, presented already by williams as a |
//|useful data structure in its own right. in the same year, r. w. |
//|floyd published an improved version that could sort an array |
//|in-place, continuing his earlier research into the treesort |
//|algorithm. |
//| heapsort primarily competes with quicksort, another very |
//|efficient general purpose nearly-in-place comparison-based sort |
//|algorithm. |
//+------------------------------------------------------------------+
//| comparion with other algorithms |
//| quicksort is typically somewhat faster due to some factors, but |
//|the worst-case running time for quicksort is o(n2), which is |
//|unacceptable for large data sets and can be deliberately |
//|triggered given enough knowledge of the implementation, creating |
//|a security risk. |
//| thus, because of the o(n log n) upper bound on heapsort's |
//|running time and constant upper bound on its auxiliary storage, |
//|embedded systems with real-time constraints or systems concerned |
//|with security often use heapsort, such as the linux kernel. |
//| heapsort also competes with merge sort, which has the same time |
//|bounds. merge sort requires Ω(n) auxiliary space, but heapsort |
//|requires only a constant amount. heapsort typically runs faster |
//|in practice on machines with small or slow data caches, and does |
//|not require as much external memory. on the other hand, merge |
//|sort has several advantages over heapsort: |
//| merge sort on arrays has considerably better data cache |
//|performance, often outperforming heapsort on modern desktop |
//|computers because merge sort frequently accesses contiguous |
//|memory locations (good locality of reference); heapsort |
//|references are spread throughout the heap. |
//| heapsort is not a stable sort; merge sort is stable. |
//| merge sort parallelizes well and can achieve close to linear |
//|speedup with a trivial implementation; heapsort is not an obvious |
//|candidate for a parallel algorithm. |
//| merge sort can be adapted to operate on singly linked lists |
//|with o(1) extra space. heapsort can be adapted to operate on |
//|doubly linked lists with only o(1) extra space overhead. |
//| merge sort is used in external sorting; heapsort is not. |
//|locality of reference is the issue. |
//| introsort is an alternative to heapsort that combines quicksort |
//|and heapsort to retain advantages of both: worst case speed of |
//|heapsort and average speed of quicksort. |
//+------------------------------------------------------------------+
//+------------------------------------------------------------------+
//| script program start function |
//| heap sort example |
//| sort symbols (items) by color (key). color in mql is an |
//|integer. similarly items can be sorted by any other key, e.g. by |
//|digits |
//+------------------------------------------------------------------+
#include <Mqh\Algorithms\HeapSort\HeapSort.mqh>
#include <Mqh\Algorithms\HeapSort\Functions.mqh>
void OnStart(void)
{
//--- load symbols to the array (items) from the terminal
string symbols[];
SymbolsLoad(symbols);
//--- load colors of the symbols to the keys array
color keys[];
SymbolKeysColor(symbols,keys);
//--- sort symbols by color in accending order with the heap sort
//algorithm
ArraySort(keys,symbols,new CHeapSort<color,string>);
//--- print a table of symbols to check result
SymbolsPrint(symbols);
}
//--------------------------------------------------------------------
// symbol | color name (id) | digits
//--------------------------------------------------------------------
// OGZD.L | clrGold (55295) | 3
// SGGD.L | clrGold (55295) | 3
// MGNT.L | clrGold (55295) | 3
// ATAD.L | clrGold (55295) | 3
// PLZL.L | clrGold (55295) | 3
// FIVE.L | clrGold (55295) | 3
// ROSN.L | clrGold (55295) | 3
// NVTK.L | clrGold (55295) | 3
// SBER.L | clrGold (55295) | 3
// MNOD.L | clrGold (55295) | 3
// SVST.L | clrGold (55295) | 3
// NLMK.L | clrGold (55295) | 3
// LKOD.L | clrGold (55295) | 3
// XAGUSD | clrKhaki (9234160) | 5
// XAUUSD | clrKhaki (9234160) | 3
// LTCUSD | clrMediumSpringGreen (10156544) | 2
// XRPUSD | clrMediumSpringGreen (10156544) | 4
// ETHBTC | clrMediumSpringGreen (10156544) | 5
// BTCEUR | clrMediumSpringGreen (10156544) | 2
// Crypto.ALT | clrMediumSpringGreen (10156544) | 2
// ETHEUR | clrMediumSpringGreen (10156544) | 2
// Crypto.Top | clrMediumSpringGreen (10156544) | 2
// EOSUSD | clrMediumSpringGreen (10156544) | 3
// LTCBTC | clrMediumSpringGreen (10156544) | 5
// BTCUSD | clrMediumSpringGreen (10156544) | 2
// XBTUSD | clrMediumSpringGreen (10156544) | 2
// ETHUSD | clrMediumSpringGreen (10156544) | 2
// DSHUSD | clrMediumSpringGreen (10156544) | 2
// ADBE | clrPaleGoldenrod (11200750) | 2
// PM | clrPaleGoldenrod (11200750) | 2
// MMM | clrPaleGoldenrod (11200750) | 2
// EA | clrPaleGoldenrod (11200750) | 2
// HPE | clrPaleGoldenrod (11200750) | 2
// VZ | clrPaleGoldenrod (11200750) | 2
// MSFT | clrPaleGoldenrod (11200750) | 2
// PFE | clrPaleGoldenrod (11200750) | 2
// GOOGL | clrPaleGoldenrod (11200750) | 2
// JNJ | clrPaleGoldenrod (11200750) | 2
// BA | clrPaleGoldenrod (11200750) | 2
// CAT | clrPaleGoldenrod (11200750) | 2
// NKE | clrPaleGoldenrod (11200750) | 2
// PG | clrPaleGoldenrod (11200750) | 2
// PEP | clrPaleGoldenrod (11200750) | 2
// KO | clrPaleGoldenrod (11200750) | 2
// GM | clrPaleGoldenrod (11200750) | 2
// GE | clrPaleGoldenrod (11200750) | 2
// AAPL | clrPaleGoldenrod (11200750) | 2
// PYPL | clrPaleGoldenrod (11200750) | 2
// LLY | clrPaleGoldenrod (11200750) | 2
// FB | clrPaleGoldenrod (11200750) | 2
// BRK.B | clrPaleGoldenrod (11200750) | 2
// IBM | clrPaleGoldenrod (11200750) | 2
// V | clrPaleGoldenrod (11200750) | 2
// INTC | clrPaleGoldenrod (11200750) | 2
// WFC | clrPaleGoldenrod (11200750) | 2
// C | clrPaleGoldenrod (11200750) | 2
// PRU | clrPaleGoldenrod (11200750) | 2
// ATVI | clrPaleGoldenrod (11200750) | 2
// GS | clrPaleGoldenrod (11200750) | 2
// JPM | clrPaleGoldenrod (11200750) | 2
// NEM | clrPaleGoldenrod (11200750) | 2
// TSLA | clrPaleGoldenrod (11200750) | 2
// CVX | clrPaleGoldenrod (11200750) | 2
// DAL | clrPaleGoldenrod (11200750) | 2
// WMT | clrPaleGoldenrod (11200750) | 2
// EBAY | clrPaleGoldenrod (11200750) | 2
// SBUX | clrPaleGoldenrod (11200750) | 2
// MCD | clrPaleGoldenrod (11200750) | 2
// NFLX | clrPaleGoldenrod (11200750) | 2
// UPS | clrPaleGoldenrod (11200750) | 2
// AMZN | clrPaleGoldenrod (11200750) | 2
// FOXA | clrPaleGoldenrod (11200750) | 2
// NVDA | clrPaleGoldenrod (11200750) | 2
// XOM | clrPaleGoldenrod (11200750) | 2
// DIS | clrPaleGoldenrod (11200750) | 2
// CMCSA | clrPaleGoldenrod (11200750) | 2
// CSCO | clrPaleGoldenrod (11200750) | 2
// BAC | clrPaleGoldenrod (11200750) | 2
// ORCL | clrPaleGoldenrod (11200750) | 2
// .JP225Cash | clrPink (13353215) | 1
// WTI | clrPink (13353215) | 2
// BRENT | clrPink (13353215) | 2
// .USTECHCash | clrPink (13353215) | 1
// .US30Cash | clrPink (13353215) | 1
// .US500Cash | clrPink (13353215) | 1
// .DE30Cash | clrPink (13353215) | 1
// GBXUSD | clrPlum (14524637) | 5
// USDMXN | clrHoneydew (15794160) | 5
// USDTRY | clrHoneydew (15794160) | 5
// USDPLN | clrHoneydew (15794160) | 5
// EURUSD | clrHoneydew (15794160) | 5
// USDJPY | clrHoneydew (15794160) | 3
// USDCHF | clrHoneydew (15794160) | 5
// EURNZD | clrHoneydew (15794160) | 5
// CADJPY | clrHoneydew (15794160) | 3
// USDCAD | clrHoneydew (15794160) | 5
// NZDUSD | clrHoneydew (15794160) | 5
// EURJPY | clrHoneydew (15794160) | 3
// NZDJPY | clrHoneydew (15794160) | 3
// NZDCHF | clrHoneydew (15794160) | 5
// EURGBP | clrHoneydew (15794160) | 5
// CADCHF | clrHoneydew (15794160) | 5
// AUDJPY | clrHoneydew (15794160) | 3
// NZDCAD | clrHoneydew (15794160) | 5
// GBPCHF | clrHoneydew (15794160) | 5
// EURCHF | clrHoneydew (15794160) | 5
// GBPUSD | clrHoneydew (15794160) | 5
// GBPJPY | clrHoneydew (15794160) | 3
// EURCAD | clrHoneydew (15794160) | 5
// AUDUSD | clrHoneydew (15794160) | 5
// GBPNZD | clrHoneydew (15794160) | 5
// GBPCAD | clrHoneydew (15794160) | 5
// EURAUD | clrHoneydew (15794160) | 5
// USDCNH | clrHoneydew (15794160) | 5
// GBPAUD | clrHoneydew (15794160) | 5
// USDRUB | clrHoneydew (15794160) | 4
// USDZAR | clrHoneydew (15794160) | 5
// EURPLN | clrHoneydew (15794160) | 5
// CHFJPY | clrHoneydew (15794160) | 3
// AUDNZD | clrHoneydew (15794160) | 5
// AUDCHF | clrHoneydew (15794160) | 5
// AUDCAD | clrHoneydew (15794160) | 5
//+------------------------------------------------------------------+
#32775LibrariesMetaTrader 5👁 5218 views
heap sort - array sorting algorithm
D
Author
DMITRII PECHERITSAPublished date
Jan 6, 2021
📚Related Articles
← View other articles →#77531Libraries
CSetupLedger: a per-setup win rate ledger for Expert Advisors
Why I wrote it My scalper trades two setups. A bullish order block and the bearish mirror of it. The Strategy Tester gave me one profit factor for both of them. I spent two weeks t...
Ali AkbarView detail →
#77488Libraries
Position sizing from risk, using the broker's own tick value and volume step
Every lot size calculator that assumes one pip is worth ten dollars is wrong on gold, wrong on indices, wrong on JPY crosses and wrong on any account not denominated in USD which i...
Ralph Ivan SimeonView detail →
#77156Libraries
PropFirm Defense
A prop firm account runs under a second rulebook MetaTrader 5 knows nothing about: a maximum loss measured from a fixed starting balance, a daily limit that resets at an hour the b...
Bruno Nunes Myrrha RibeiroView detail →