//+------------------------------------------------------------------+ //| ShellSort.mq5 | //| 2019-2021, dimitri pecheritsa | //| mql5.com/en/users/dmipec | //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ //| shell sort - array sorting algorithm | //| cases: best: n log n, average: n^(4/3), worst: n^(3/2) | //| memory: 1, stable: no, method: insertion | //| note: small code size | //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ //| shellsort, also known as shell sort or shell's method, is an | //|in-place comparison sort. it can be seen as either a | //|generalization of sorting by exchange (bubble sort) or sorting by | //|insertion (insertion sort). the method starts by sorting pairs of | //|elements far apart from each other, then progressively reducing | //|the gap between elements to be compared. by starting with far | //|apart elements, it can move some out-of-place elements into | //|position faster than a simple nearest neighbor exchange. donald | //|shell published the first version of this sort in 1959. the | //|running time of shellsort is heavily dependent on the gap | //|sequence it uses. for many practical variants, determining their | //|time complexity remains an open problem. | //| known complexities range from o(n^2) to o(n^(4/3)) and θ(n | //|log^2 n). this, combined with the fact that shellsort is | //|in-place, only needs a relatively small amount of code, and does | //|not require use of the call stack, makes it is useful in | //|situations where memory is at a premium, such as in embedded | //|systems and operating system kernels. | //| shellsort is not stable: it may change the relative order of | //|elements with equal values. it is an adaptive sorting algorithm | //|in that it executes faster when the input is partially sorted. | //| shellsort performs more operations and has higher cache miss | //|ratio than quicksort. however, since it can be implemented using | //|little code and does not use the call stack, some implementations | //|of the qsort function in the c standard library targeted at | //|embedded systems use it instead of quicksort. shellsort is, for | //|example, used in the uclibc library. for similar reasons, in the | //|past, shellsort was used in the linux kernel. | //| shellsort can also serve as a sub-algorithm of introspective | //|sort, to sort short subarrays and to prevent a slowdown when the | //|recursion depth exceeds a given limit. this principle is | //|employed, for instance, in the bzip2 compressor. | //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ //| script program start function | //| a shell sort example. sort terminal symbols by the digits value | //+------------------------------------------------------------------+ #include <Mqh\Algorithms\ShellSort\ShellSort.mqh> #include <Mqh\Algorithms\ShellSort\Functions.mqh> void OnStart(void) { //--- load symbols from the terminal. they will be treated as the //items array by the sorter string symbols[]; SymbolsLoad(symbols); //--- create the keys array which contains the digits values for //each symbol from the symbols array, which is the basis for sorting int keys[]; SymbolKeysDigit(symbols,keys); //--- sort symbols by digits in accending order with the shell sort //algorithm ArraySort(keys,symbols,new CShellSort<int,string>); //--- check the result of sorting by printing a table of symbols SymbolsPrint(symbols); } //-------------------------------------------------------------------- // symbol | color | digits //-------------------------------------------------------------------- // .USTECHCash | clrPink | 1 // .DE30Cash | clrPink | 1 // .JP225Cash | clrPink | 1 // .US30Cash | clrPink | 1 // .US500Cash | clrPink | 1 // ATVI | clrPaleGoldenrod | 2 // NVDA | clrPaleGoldenrod | 2 // CSCO | clrPaleGoldenrod | 2 // ORCL | clrPaleGoldenrod | 2 // AMZN | clrPaleGoldenrod | 2 // UPS | clrPaleGoldenrod | 2 // NFLX | clrPaleGoldenrod | 2 // ADBE | clrPaleGoldenrod | 2 // SBUX | clrPaleGoldenrod | 2 // EBAY | clrPaleGoldenrod | 2 // TSLA | clrPaleGoldenrod | 2 // MCD | clrPaleGoldenrod | 2 // DIS | clrPaleGoldenrod | 2 // FOXA | clrPaleGoldenrod | 2 // NEM | clrPaleGoldenrod | 2 // JPM | clrPaleGoldenrod | 2 // BAC | clrPaleGoldenrod | 2 // C | clrPaleGoldenrod | 2 // WFC | clrPaleGoldenrod | 2 // V | clrPaleGoldenrod | 2 // GS | clrPaleGoldenrod | 2 // PYPL | clrPaleGoldenrod | 2 // PRU | clrPaleGoldenrod | 2 // BRK.B | clrPaleGoldenrod | 2 // AAPL | clrPaleGoldenrod | 2 // KO | clrPaleGoldenrod | 2 // PEP | clrPaleGoldenrod | 2 // PG | clrPaleGoldenrod | 2 // PM | clrPaleGoldenrod | 2 // NKE | clrPaleGoldenrod | 2 // GM | clrPaleGoldenrod | 2 // BTCUSD | clrMediumSpringGreen | 2 // ETHUSD | clrMediumSpringGreen | 2 // WMT | clrPaleGoldenrod | 2 // DAL | clrPaleGoldenrod | 2 // XOM | clrPaleGoldenrod | 2 // CVX | clrPaleGoldenrod | 2 // BRENT | clrPink | 2 // WTI | clrPink | 2 // BTCEUR | clrMediumSpringGreen | 2 // DSHUSD | clrMediumSpringGreen | 2 // LTCUSD | clrMediumSpringGreen | 2 // Crypto.Top | clrMediumSpringGreen | 2 // Crypto.ALT | clrMediumSpringGreen | 2 // GOOGL | clrPaleGoldenrod | 2 // FB | clrPaleGoldenrod | 2 // MSFT | clrPaleGoldenrod | 2 // IBM | clrPaleGoldenrod | 2 // VZ | clrPaleGoldenrod | 2 // INTC | clrPaleGoldenrod | 2 // HPE | clrPaleGoldenrod | 2 // EA | clrPaleGoldenrod | 2 // MMM | clrPaleGoldenrod | 2 // XBTUSD | clrMediumSpringGreen | 2 // ETHEUR | clrMediumSpringGreen | 2 // GE | clrPaleGoldenrod | 2 // PFE | clrPaleGoldenrod | 2 // LLY | clrPaleGoldenrod | 2 // CMCSA | clrPaleGoldenrod | 2 // JNJ | clrPaleGoldenrod | 2 // BA | clrPaleGoldenrod | 2 // CAT | clrPaleGoldenrod | 2 // NLMK.L | clrGold | 3 // SGGD.L | clrGold | 3 // FIVE.L | clrGold | 3 // SBER.L | clrGold | 3 // NVTK.L | clrGold | 3 // XAUUSD | clrKhaki | 3 // AUDJPY | clrHoneydew | 3 // CHFJPY | clrHoneydew | 3 // ROSN.L | clrGold | 3 // PLZL.L | clrGold | 3 // EOSUSD | clrMediumSpringGreen | 3 // MGNT.L | clrGold | 3 // EURJPY | clrHoneydew | 3 // LKOD.L | clrGold | 3 // NZDJPY | clrHoneydew | 3 // MNOD.L | clrGold | 3 // ATAD.L | clrGold | 3 // OGZD.L | clrGold | 3 // USDJPY | clrHoneydew | 3 // SVST.L | clrGold | 3 // GBPJPY | clrHoneydew | 3 // CADJPY | clrHoneydew | 3 // USDRUB | clrHoneydew | 4 // XRPUSD | clrMediumSpringGreen | 4 // EURCHF | clrHoneydew | 5 // AUDNZD | clrHoneydew | 5 // XAGUSD | clrKhaki | 5 // AUDUSD | clrHoneydew | 5 // EURGBP | clrHoneydew | 5 // GBPAUD | clrHoneydew | 5 // EURNZD | clrHoneydew | 5 // EURAUD | clrHoneydew | 5 // EURPLN | clrHoneydew | 5 // GBPUSD | clrHoneydew | 5 // GBPCHF | clrHoneydew | 5 // NZDCAD | clrHoneydew | 5 // NZDCHF | clrHoneydew | 5 // EURUSD | clrHoneydew | 5 // NZDUSD | clrHoneydew | 5 // USDCAD | clrHoneydew | 5 // USDCHF | clrHoneydew | 5 // GBPNZD | clrHoneydew | 5 // USDPLN | clrHoneydew | 5 // USDMXN | clrHoneydew | 5 // USDZAR | clrHoneydew | 5 // EURCAD | clrHoneydew | 5 // USDCNH | clrHoneydew | 5 // AUDCAD | clrHoneydew | 5 // AUDCHF | clrHoneydew | 5 // GBXUSD | clrPlum | 5 // LTCBTC | clrMediumSpringGreen | 5 // ETHBTC | clrMediumSpringGreen | 5 // CADCHF | clrHoneydew | 5 // GBPCAD | clrHoneydew | 5 // USDTRY | clrHoneydew | 5 //+------------------------------------------------------------------+
