//+------------------------------------------------------------------+ //| 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 //+------------------------------------------------------------------+
