/** * Library with all sort algorithms. * Iterating towards perfection (from the simplest implementation to * their optimized version) to get the lowest O-notation factor with * the minor operations. * * @module nsortik * @author davorpatech * @since 2020-08-23 */ 'use strict'; // // Module imports. // const [util, perf_hooks] = ['util', 'perf_hooks'].map(m => require(m)); // console shortcuts const [cout, cerr, ctbl, ctimes, ctimee] = (c => 'log,error,table,time,timeEnd'.split(',').map(m => c[m].bind(c)))(console); // other shortcuts without namespace const [ // Objects objProto, oassign, odefpropsAs, ofreeze, ovalues, okeys, oentries, oentriesm, // Arrays arrProto, isArray, // Math abs, ceil, floor, round, round10, max, min, pow, exp, sqrt, random, // Strings spaces, ] = [ ...((O, P) => [ P, O.assign, function definePropertiesAs(o, props, { // allow key renaming mkey = (k, v) => k, mval = (v, k) => v, // allow dym compute. // Object.defineProperty descriptor options defaults are false enumerableIf = (k, v) => false, configurableIf = (k, v) => false, writableIf = (k, v) => false, } = {}) { // create property descriptors aplying callback options const descriptors = O.fromEntries( O.entries(props).map(([k, v]) => { // create descriptor return [mkey(k, v), { enumerable: enumerableIf(k, v), configurable: configurableIf(k, v), writable: writableIf(k, v), value: mval(v, k), }]; }) ); O.defineProperties(o, descriptors); return o; }, function deepFreeze(o) { // Retrieve the property names defined on object const propNames = O.getOwnPropertyNames(o); // Freeze properties before freezing self for (const name of propNames) { const value = o[name]; if (value && typeof value === "object") { deepFreeze(value); } } return O.freeze(o); }, O.values, O.keys, O.entries, O.fromEntries, ])(Object, Object.prototype), ...((A, P) => [ P, A.isArray, ])(Array, Array.prototype), ...(M => [ M.abs, M.ceil, M.floor, M.round, function round10(n, dec=2) { return +(+n).toFixed(dec); }, M.max, M.min, M.pow, M.exp, M.sqrt, M.random, ])(Math), ...((S, P) => [ function spaces(n=1) { return ' '.repeat(n); }, ])(String, String.prototype), ]; /** * Module performance utilities. * @private */ // high resolution time in nanos function hrtime(b = true) { return process.hrtime.bigint(); } const { performance: perf, PerformanceObserver } = perf_hooks; const startPerfObserving = ( { entryTypes = [ //'mark', 'measure', 'function', 'gc', ], buffering = true } = {}) => { const inst = new PerformanceObserver((list, obs) => { list.getEntries().forEach( eventEntryProcessor(obs)); //perf.clearMarks(); //perf.clearMeasures(); //perf.clearGC(); //obs.disconnect(); }); inst.observe({ entryTypes, buffer: !!buffering, }); return inst; function eventEntryProcessor(obs) { return (e) => { if (e.name === "END") { // destroy // free memory perf.clearMarks(); obs.disconnect(); } if (!'function:measure' .split(':') .includes(e.entryType) ) return clog(e); // format measurement cout(`%s took: %sms`, e.name, e.duration); }; } }; /** * Two-tailed critical values of Student's T-Distribution with ν degrees * of freedom (τ₁-α,ν) and 9x% percentiles. * @see http://www.itl.nist.gov/div898/handbook/eda/section3/eda3672.htm. */ const stdcTABLE = { // ν°ᶲ. 0.90 0.95 0.975 0.99 0.995 0.999 '_thv_':[0.90, 0.95, 0.975, 0.99, 0.995, 0.999], '_ths_':['090','095', '0975', '099', '0995', '0999'], '1': [3.078, 6.314, 12.706, 31.821, 63.657, 318.313], '2': [1.886, 2.920, 4.303, 6.965, 9.925, 22.327], '3': [1.638, 2.353, 3.182, 4.541, 5.841, 10.215], '4': [1.533, 2.132, 2.776, 3.747, 4.604, 7.173], '5': [1.476, 2.015, 2.571, 3.365, 4.032, 5.893], '6': [1.440, 1.943, 2.447, 3.143, 3.707, 5.208], '7': [1.415, 1.895, 2.365, 2.998, 3.499, 4.782], '8': [1.397, 1.860, 2.306, 2.896, 3.355, 4.499], '9': [1.383, 1.833, 2.262, 2.821, 3.250, 4.296], '10': [1.372, 1.812, 2.228, 2.764, 3.169, 4.143], '11': [1.363, 1.796, 2.201, 2.718, 3.106, 4.024], '12': [1.356, 1.782, 2.179, 2.681, 3.055, 3.929], '13': [1.350, 1.771, 2.160, 2.650, 3.012, 3.852], '14': [1.345, 1.761, 2.145, 2.624, 2.977, 3.787], '15': [1.341, 1.753, 2.131, 2.602, 2.947, 3.733], '16': [1.337, 1.746, 2.120, 2.583, 2.921, 3.686], '17': [1.333, 1.740, 2.110, 2.567, 2.898, 3.646], '18': [1.330, 1.734, 2.101, 2.552, 2.878, 3.610], '19': [1.328, 1.729, 2.093, 2.539, 2.861, 3.579], '20': [1.325, 1.725, 2.086, 2.528, 2.845, 3.552], '21': [1.323, 1.721, 2.080, 2.518, 2.831, 3.527], '22': [1.321, 1.717, 2.074, 2.508, 2.819, 3.505], '23': [1.319, 1.714, 2.069, 2.500, 2.807, 3.485], '24': [1.318, 1.711, 2.064, 2.492, 2.797, 3.467], '25': [1.316, 1.708, 2.060, 2.485, 2.787, 3.450], '26': [1.315, 1.706, 2.056, 2.479, 2.779, 3.435], '27': [1.314, 1.703, 2.052, 2.473, 2.771, 3.421], '28': [1.313, 1.701, 2.048, 2.467, 2.763, 3.408], '29': [1.311, 1.699, 2.045, 2.462, 2.756, 3.396], '30': [1.310, 1.697, 2.042, 2.457, 2.750, 3.385], '31': [1.309, 1.696, 2.040, 2.453, 2.744, 3.375], '32': [1.309, 1.694, 2.037, 2.449, 2.738, 3.365], '33': [1.308, 1.692, 2.035, 2.445, 2.733, 3.356], '34': [1.307, 1.691, 2.032, 2.441, 2.728, 3.348], '35': [1.306, 1.690, 2.030, 2.438, 2.724, 3.340], '36': [1.306, 1.688, 2.028, 2.434, 2.719, 3.333], '37': [1.305, 1.687, 2.026, 2.431, 2.715, 3.326], '38': [1.304, 1.686, 2.024, 2.429, 2.712, 3.319], '39': [1.304, 1.685, 2.023, 2.426, 2.708, 3.313], '40': [1.303, 1.684, 2.021, 2.423, 2.704, 3.307], '41': [1.303, 1.683, 2.020, 2.421, 2.701, 3.301], '42': [1.302, 1.682, 2.018, 2.418, 2.698, 3.296], '43': [1.302, 1.681, 2.017, 2.416, 2.695, 3.291], '44': [1.301, 1.680, 2.015, 2.414, 2.692, 3.286], '45': [1.301, 1.679, 2.014, 2.412, 2.690, 3.281], '46': [1.300, 1.679, 2.013, 2.410, 2.687, 3.277], '47': [1.300, 1.678, 2.012, 2.408, 2.685, 3.273], '48': [1.299, 1.677, 2.011, 2.407, 2.682, 3.269], '49': [1.299, 1.677, 2.010, 2.405, 2.680, 3.265], '50': [1.299, 1.676, 2.009, 2.403, 2.678, 3.261], '51': [1.298, 1.675, 2.008, 2.402, 2.676, 3.258], '52': [1.298, 1.675, 2.007, 2.400, 2.674, 3.255], '53': [1.298, 1.674, 2.006, 2.399, 2.672, 3.251], '54': [1.297, 1.674, 2.005, 2.397, 2.670, 3.248], '55': [1.297, 1.673, 2.004, 2.396, 2.668, 3.245], '56': [1.297, 1.673, 2.003, 2.395, 2.667, 3.242], '57': [1.297, 1.672, 2.002, 2.394, 2.665, 3.239], '58': [1.296, 1.672, 2.002, 2.392, 2.663, 3.237], '59': [1.296, 1.671, 2.001, 2.391, 2.662, 3.234], '60': [1.296, 1.671, 2.000, 2.390, 2.660, 3.232], '61': [1.296, 1.670, 2.000, 2.389, 2.659, 3.229], '62': [1.295, 1.670, 1.999, 2.388, 2.657, 3.227], '63': [1.295, 1.669, 1.998, 2.387, 2.656, 3.225], '64': [1.295, 1.669, 1.998, 2.386, 2.655, 3.223], '65': [1.295, 1.669, 1.997, 2.385, 2.654, 3.220], '66': [1.295, 1.668, 1.997, 2.384, 2.652, 3.218], '67': [1.294, 1.668, 1.996, 2.383, 2.651, 3.216], '68': [1.294, 1.668, 1.995, 2.382, 2.650, 3.214], '69': [1.294, 1.667, 1.995, 2.382, 2.649, 3.213], '70': [1.294, 1.667, 1.994, 2.381, 2.648, 3.211], '71': [1.294, 1.667, 1.994, 2.380, 2.647, 3.209], '72': [1.293, 1.666, 1.993, 2.379, 2.646, 3.207], '73': [1.293, 1.666, 1.993, 2.379, 2.645, 3.206], '74': [1.293, 1.666, 1.993, 2.378, 2.644, 3.204], '75': [1.293, 1.665, 1.992, 2.377, 2.643, 3.202], '76': [1.293, 1.665, 1.992, 2.376, 2.642, 3.201], '77': [1.293, 1.665, 1.991, 2.376, 2.641, 3.199], '78': [1.292, 1.665, 1.991, 2.375, 2.640, 3.198], '79': [1.292, 1.664, 1.990, 2.374, 2.640, 3.197], '80': [1.292, 1.664, 1.990, 2.374, 2.639, 3.195], '81': [1.292, 1.664, 1.990, 2.373, 2.638, 3.194], '82': [1.292, 1.664, 1.989, 2.373, 2.637, 3.193], '83': [1.292, 1.663, 1.989, 2.372, 2.636, 3.191], '84': [1.292, 1.663, 1.989, 2.372, 2.636, 3.190], '85': [1.292, 1.663, 1.988, 2.371, 2.635, 3.189], '86': [1.291, 1.663, 1.988, 2.370, 2.634, 3.188], '87': [1.291, 1.663, 1.988, 2.370, 2.634, 3.187], '88': [1.291, 1.662, 1.987, 2.369, 2.633, 3.185], '89': [1.291, 1.662, 1.987, 2.369, 2.632, 3.184], '90': [1.291, 1.662, 1.987, 2.368, 2.632, 3.183], '91': [1.291, 1.662, 1.986, 2.368, 2.631, 3.182], '92': [1.291, 1.662, 1.986, 2.368, 2.630, 3.181], '93': [1.291, 1.661, 1.986, 2.367, 2.630, 3.180], '94': [1.291, 1.661, 1.986, 2.367, 2.629, 3.179], '95': [1.291, 1.661, 1.985, 2.366, 2.629, 3.178], '96': [1.290, 1.661, 1.985, 2.366, 2.628, 3.177], '97': [1.290, 1.661, 1.985, 2.365, 2.627, 3.176], '98': [1.290, 1.661, 1.984, 2.365, 2.627, 3.175], '99': [1.290, 1.660, 1.984, 2.365, 2.626, 3.175], '100': [1.290, 1.660, 1.984, 2.364, 2.626, 3.174], '∞': [1.282, 1.645, 1.960, 2.326, 2.576, 3.090], }; /** * Proxy decorator to measure an piece * of code passed as a function. * @param {Function} fn * Function to decorate/wrap. * @param {boolean} [options.times] * Configures how many times execute it. * Getting averaged measurements maybe converges to better accuracy value. * @param {number|boolean} [options.prec] * How many decimals you wish on values. * Default=8, Disable with `false` */ function measurefy(fn, { times = 1, prec=-1, moeperc = 2 } = {}) { if (typeof fn !== "function") { throw new TypeError(`Object to measurefy must be an invocable function. Found: ${typeof fn}`); } //ensure at least one execution if (!times || times <= 0) times = 1; if (typeof times !== "number") { throw new TypeError(`"Loops" parameter must be a positive number. Found: ${typeof loops}`); } // locker if (fn.$$measurefy) { throw new ReferenceError(`${fn.name} has already measurified by a process started at a {Date.now() - fn.$$measurefy.start} ago`); } fn.$$measurefy = { start: Date.now(), // loop marker idx: null, // inner measurements store stats: null, }; // hack to dynamify function name return ovalues({ [`${fn.name}$$measurefied`]: // proxy invoker function (...args) { let result, stats; // reserve array memory to all slots const sample = Array(times); try { for (let i = 0; i < times; i++) { fn.$$measurefy.idx = i; // measure start const start = hrtime(); // invoke... result = fn(...args); // measure frame end const end = hrtime(); sample[i] = { start, end, }; } } finally { // recopile inner-exposed measures stats = { // destructured to avoid memory leaks // between scopes ...fn.$$measurefy .stats, }; // erase lock // avoiding memory leaks delete fn.$$measurefy; } // compose making inmutable return ofreeze({ name: fn.name, // real function return result, stats, // destructure computings of // end-start interval measures ...measure(sample), }); }, })[0]; // computed end-start measures function measure(sample) { // compute global and sampled measures return { // complete sample slots measures sample: sample .map(sampleMapper), // global measures using sample slots ...sample.reduce( sampleMerger, {}), }; } function sampleMerger(m, v, i, c) { // on first slot (i === 0) && (m.start = v.start); // on last slot (i === c.length - 1) && ( m.end = v.end, // complete / compute m = sampleMapper( m, true, c) ); return m; } function sampleMapper(v, i, sample) { const m = { // weak copy enumerable props // using rest operator ...v, hrtime: { start: v.start, end: v.end, elapsed: v.end - v.start, }, duration: nan2mil(v.end - v.start), }; // delete moved props to "hrtime" delete m.start; delete m.end; // is global measurements source? if (i === true) { const size = sample.length; const diffs = sample .map(({start, end}) => end - start); /* * Compute the sample mean * (estimate of the population mean). */ const elaps = diffs.reduce( (o, v) => { o.sum += v; //o.prod *= v; return o; }, { fix: m.hrtime.elapsed, sum: 0n, //prod: 1n, }); let duration = { fix: m.duration, std: nan2mil(elaps.sum), }, mean = { fix: duration.fix / size, std: duration.std / size, }; /* * Compute the sample variance * (estimate of the population variance) */ const varz = diffs .map(nan2mil).reduce( (sum, v) => sum + pow(v - mean.std, 2) , 0); let variance = { // all population std: varz / size, // picking sample qua: varz / (size - 1), }, /* * Compute the sample standard deviation * (estimate of the population standard deviation). */ sd = oentriesm( oentries(variance) .map(([k, v]) => [k, sqrt(v)]) ), /* * Compute the standard error of the mean * (a.k.a. the standard deviation of the sampling distribution * of the sample mean). */ sem = oentriesm( oentries(sd) .map(([k, v]) => [k, v / sqrt(size)]) ), /* * Compute the degrees of freedom (ν°ᶲ) */ df = size - 1, /* * Compute the critical value, using the * degrees of freedom (ν°ᶲ) */ criticals = // on ν°ᶲ=0, use the 1st (stdcTABLE[round(df) || 1] || // and if unknown use this stdcTABLE['∞']), /* * Compute the margin of error * of all discriminatory percentiles defined in criticals */ moe = oentriesm( oentries(sem) .reduce((acc, [k, v]) => { // forEach `sem` property generate k-pairs let i = -1; for (const crit of criticals) { i += 1; const cv = v * crit, ck = k + '_' + stdcTABLE['_ths_'][i]; acc.push([ck, cv]); // if matches with desired percentile option, // replicate it in common key (moeperc !== false && (i === moeperc || stdcTABLE['_thv_'].indexOf(moeperc) != -1) ) && acc.unshift([k, cv]); } return acc; }, []) ), /* * Compute the Pearson coefficient representing * the variation between standard deviation and their mean. * (a.k.a. the % dispersion of the sampling distribution). * * Also the relative margin of error `rme` (expressed as * a percentage of the mean). */ [cvp, rme] = [sd, moe].map(src => oentriesm(oentries(src) .map(([k, v]) => [k, (v / mean[k[0]==='f'?'fix':'std']) * 100]) )); /* * when configured, * round all measured props * to fixed n-decimals */ prec !== false && [duration, mean, variance, sd, sem, cvp, moe, rme] .forEach(o => { for (const [k, v] of oentries(o)) { o[k] = prec >= 0 // desired ? round10(v, prec) // default : round10(v, 8); } }); /* * merge */ oassign(m, { duration, mean, variance, deviation: sd, sem, cvp, moe, rme, }); oassign(m.hrtime, { elapsed0: elaps.fix, elapsed: elaps.sum, }); } //(i === 0 || i ===true) && cout(m); return m; } function nan2mil(n) { // bigint nanos to millis return Number(n) / pow(10, 6); } } oassign(measurefy, { innery: (fn, slots = 1) => { // provide counters holder on 1st sample const cnt = fn?.$$measurefy?.idx === 0 && Array(+slots).fill(0); return [fn, cnt]; }, }); /** * Module common utilities. * @private */ /** * Filter that accepts functions that * it's name matches some pattern. * @callback * @param {*} v value to test. * @return {boolean} `true` if match. */ const isBasAlgorithm = v => typeof v === 'function' && v.name.match(/sort(\d+)?$/ig); const applyNamingAlias = (fn, names) => { names = names || []; if (!isArray(names)) names = `${names}`.split(/[\s:;,]+/ig); fn._names_ = [fn.name, ...names]; return fn; }; /** * Resolves right references using provided flags. * @param {Array<*>} arr * The array containing the items. * @param {Comparator|ComparatorCallback} comparer * The comparator to resolve. */ const anref = (arr, comparer, flags) => { // weak clone using destructuring arr = [...arr]; return [ arr, extractComparator(comparer) ]; }; /** * Adapts any compatible structure (like Comparator) * to be a ComparatorCallback. * @param {Comparator|ComparatorCallback} comparer * The comparator to resolve. * @return {ComparatorCallback} */ function extractComparator(comparer) { // make compatible with interface if (comparer instanceof Comparator) comparer = comparer.compare; // check types if (typeof comparer !== "function") { throw new TypeError( `Provided 'comparator' not seems to be a function compatible with Comparator interface Found: ${typeof comparer}`); } return comparer; } /** * Swaps two values in a collection. * @param {Array<*>} arr * The array containing the items. * @param {int} i * Index of first item to swap. * @param {int} j * Index of second item to swap. */ const swap = (arr, i, j) => { // by destructuring [arr[i], arr[j]] = [arr[j], arr[i]]; }; const swaptmp = (arr, i, j) => { // by temporal var const tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }; /** * Shuffler that could be used to sort * some collection giving the same random * oportunities to low and high values. * @callback * @return {number} * random number between -0.5 and 0.5. */ const halfShuffler = () => random() - 0.5; /** * Factory that allows you build collection fillers based on * the iterating index property. * Ideally to use as callback passed to `map`. * @param {string} [opts.name] * dynamic name given to built lambda. * @param {number} [opts.gap=0] * Fixed gap to add to values. * @param {number|string} [opts.rnd=0] * The way to round (or not) values. * @param {number} [opts.lfactor] * Length factor to apply to size of * collection. * @return {Function} built lambda filler. */ const indexFillerFactory = ({ name = "indexFiller", gap = 0, rnd = 'r', lfactor = 0, } = {}) => { rnd += ''; // to str gap = +(gap); // to num lfactor = +(lfactor); // rnd function factory switch const rndFn = /1|u|up/ig.test(rnd) ? ceil : /-1|d|down/ig.test(rnd) ? floor : /0|r/ig.test(rnd) ? round // identity (no round) : v => v; // hack to dynamify function name const impl = ovalues({ [`${name}`]: // generator function (v, i, c) { // avoid zero-division const l = (lfactor && (c.length / lfactor) ) || 0; // compute return i + gap - rndFn(l); } // return this decorated lambda })[0]; return impl; }; /** * Module public interface. * @public */ /** * Comparators allows you compare two items, normally of the same type. * @typedef ComparatorCallback * @callback * @param {*} a * item to compare. * @param {*} b * item to compare with. * @return {number} * the compare result, where `0` means are equals (`b == a`), * negative values when second value is greather than first (`b > a`) * and positives on otherwise (`a > b`). * It could be computed as the distance between both items, * e.g. in numbers (`a - b`). */ /** * Interface Comparator. * @interface */ class Comparator { /** * Compare two items, normally of the same type. * @param {*} a * item to compare. * @param {*} b * item to compare with. * @return {number} * the compare result, where `0` means are equals (`b == a`), * negative values when second value is greather than first (`b > a`) * and positives on otherwise (`a > b`). * It could be computed as the distance between both items, * e.g. in numbers (`a - b`). */ compare(a, b) { throw new TypeError( "Comparator is an interface. Method `compare` must be overriden by subclasses."); //return a - b; } } /** * Interface Comparable * @interface */ class Comparable { /** * Compare an item, with other that normally has the same type. * @param {*} o * item to compare with. * @return {number} * the compare result, where `0` means are equals (`this == o`), * negative values when second value is greather than first (`o > this`) * and positives on otherwise (`this > o`). * It could be computed as the distance between both items, * e.g. in numbers (`this - o`). */ compareTo(o) { throw new TypeError( "Comparable is an interface. Method `compareTo` must be overriden by subclasses."); //return this - o; } } /** * Comparator to order items ascentdently (heavy items are moved to the end). * @type ComparatorCallback */ const naturalOrder = (a, b) => a - b; /** * Comparator to order items descentdently (heavy items are moved to the begining). * @type ComparatorCallback */ const reverseOrder = (a, b) => b - a; /** * Decorator to invert the order provided by comparator that is passed as argument * @param {Comparator|ComparatorCallback} comparator * The comparator to decorate. * @return {ComparatorCallback} decorated comparator. */ const reversedComparator = (comparator) => { // adapt comparator = extractComparator(comparator); // hack to dynamify function name const impl = ovalues({ [`${fn.name}$$reversed`]: // proxy invoker function (a, b) { // negate sign return -comparator(a, b); }, // return decorated lambda })[0]; return impl; }; /** * Decorator to delegate comparing process on a method/function presented in item values to compare, taking `compareTo` as default (a.k.a. Comparable interface) * @param {string} method * The method name to invoke. * On calling, it will receive, as parameter, the item to compare to * @return {ComparatorCallback} decorated comparator */ const methodComparatorFactory = (method, ...args) => { const type = typeof method; if (!["undefined","string"] .includes(type)) throw new TypeError( `Method used to compare must be a string. Found: ${type}`); const resolveFunc = (obj) => { if (type === "undefined") { // like instanceof Comparable method = "compareTo"; } let fn = obj[method]; if (typeof fn !== "function") throw new TypeError( `Item instance must declare method ${method} to invoke as Comparable interface. Value: ${obj}. Found: ${typeof fn}`); return fn; }; // hack to dynamify function name const impl = ovalues({ [`${method || 'default'}$$methodComparator`]: // proxy invoker function (a, b) { const fn = resolveFunc(a); // invoke over `a` // merging extra args at the end return fn.apply(a, [b, ...args]); } // return decorated lambda })[0]; return impl; }; /** * Performs an in-place/inmutable sort of an iterable collection with * `Buble Sort` algorithm using provided `comparator` callback to order items. * * Bubble sort, sometimes referred to as sinking sort, is a simple sorting * algorithm that repeatedly steps through the list, compares adjacent * elements and swaps them if they are in the wrong order. * The pass through the list is repeated until the list is sorted. * The algorithm, which is a comparison sort, is named for the way smaller * or larger elements "bubble" to the top of the list, * like the legend story: `Rabbits & Turtles`. * * Due to it O-notation complexity, bubble sort should be avoided in the case * of large collections. Also will not be efficient in the case of a * reverse-ordered collection, unless we walk it backwards. * The only significant advantage that bubble sort has over most other * algorithms is that the ability to detect that the list is sorted * efficiently is built into the algorithm. It also performs better on a * list that is substantially sorted (having a small number of inversions). * * Worst-case performance: * O(n^2) comparisons, * O(n^2) swaps * Best-case performance: * O(n) comparisons, * O(1) swaps * Average performance: * O(n^2) comparisons, * O(n^2) swaps * Worst-case space complexity: * O(1) total, * O(1) auxiliary * * @param {Array<*>} arr * The collection to sort. * @param {Comparator|ComparatorCallback} comparator * The caller used to compare items. * Receives 2 parameters with values to compare and return 0 if are equals, * negative values when second value is greather than first and positives * on otherwise. * @return {Array<*>} sorted. * @public */ function bubbleSort01( arr, comparator, flags) // Non-optimized. while flag+for version // (loop always over all items) { [arr, comparator] = anref(arr, comparator, flags); let n = (arr && arr.length) || 0; // at least 2 items control let swapped = n > 1; // measurement control const [fn, cnt] = measurefy.innery( bubbleSort01, 3); /* * This outer loop moves until no more changes are needed */ while (swapped) { // notify loop cnt && cnt[0]++; /* * reset flag on loop entering because it might be altered from * a previous iteration */ swapped = false; /* * This inner loop bubbles up items from left to the right. * The `stop` point is the length of the array. * The `start` point is one because we are comparing each item to the * previous item, and the first item doesn't have a pair to compare to. */ for (let i = 1; i < n; i++) { // notify pass cnt && cnt[1]++; /* * if pair is out of order */ if (comparator( arr[i-1], arr[i]) > 0) { /* * swap them and remember * something changed */ swap(arr, i-1, i); swapped = true; // notify swap cnt && cnt[2]++; } } } // broadcast measurements cnt && measurefy.stats01(fn, cnt); return arr; } odefpropsAs(bubbleSort01, { desc: `Non-optimized (while🚩↬for) version. Features: ⋇ Flagging swaps to detect if continue with outer loop is needed`, group: `bubble`, }, { enumerableIf: _ => true, }); function bubbleSort02( arr, comparator, flags) // Mid-optimized. while flag+for version // (one pass less by each loop) { [arr, comparator] = anref(arr, comparator, flags); let n = (arr && arr.length) || 0; // at least 2 items control let swapped = n > 1; // measurement control const [fn, cnt] = measurefy.innery( bubbleSort02, 3); /* * The outer loop moves until no more changes are needed */ while (swapped) { // notify loop cnt && cnt[0]++; /* * reset flag on loop entering because it might be altered from * a previous iteration */ swapped = false; /* * This inner loop bubbles up items from left to the right. * The `stop` point is the length of the array minus how many * reentrances have the outer loop (one less by each iteration). * The `start` point is one because we are comparing each item to the * previous item, and the first item doesn't have a pair to compare to. */ for (let i = 1; i < n; i++) { // notify pass cnt && cnt[1]++; /* * if pair is out of order */ if (comparator( arr[i-1], arr[i]) > 0) { /* * swap them and remember * something changed */ swap(arr, i-1, i); swapped = true; // notify swap cnt && cnt[2]++; } } /* * The n-th pass finds the n-th largest element and puts it into its * final place. So, the inner loop can avoid looking at the last n − 1 * items when running for the n-th time. Therefore, one less... */ n -= 1; } // broadcast measurements cnt && measurefy.stats01(fn, cnt); return arr; } odefpropsAs(bubbleSort02, { desc: `Half-optimized (while🚩↬for) version. Features: ⋇ Flagging swaps to detect if continue with outer loop is needed ⋇ Reducing one by one the passes per loop, since last pass moves the item to right position and after that, all is sorted`, group: `bubble`, }, { enumerableIf: _ => true, }); function bubbleSort03( arr, comparator, flags) // Full-optimized. while flag+for version // (remembering lower swapped position) { [arr, comparator] = anref(arr, comparator, flags); let n = (arr && arr.length) || 0; // measurement control const [fn, cnt] = measurefy.innery( bubbleSort03, 3); /* * The outer loop moves while there are no positions to swap. * Also controls the entrance with at least 2 items to compare */ while (n > 1) { // notify loop cnt && cnt[0]++; /* * Reset last swap index on loop entering because it might be * altered from a previous iteration */ let newn = 0; /* * This inner loop bubbles up items from left to the right. * The `stop` value is the lastest position where a swap was detected, * after it, these next `nn`-items always are sorted (`the rabbits`) * The `start` point is one because we are comparing each item to the * previous item, and the first item doesn't have a pair to compare to. */ for (let i = 1; i < n; i++) { // notify pass cnt && cnt[1]++; /* * if pair is out of order */ if (comparator( arr[i-1], arr[i]) > 0) { /* * swap them and remember * changed index */ swap(arr, i-1, i); newn = i; // notify swap cnt && cnt[2]++; } } /* * It can happen that more than one element is placed in their final * position on a single pass. In particular, after every pass, all * elements after the last swap are sorted, and do not need to be * checked again. This allows to skip over many elements, resulting * in about a worst case 50% improvement in comparison count * (though no improvement in swap counts). So instead of reducing * passes by one, we remember the lowest value and sets here, * also avoiding define a `swapped` flag. */ n = newn; } // broadcast measurements cnt && measurefy.stats01(fn, cnt); return arr; } odefpropsAs(bubbleSort03, { desc: `Full-optimized (while🚩↬for) version. Features: ⋇ Avoid flagging swaps ⋇ Remembering lower swapped position ⋇ Supports processing correlated elements on same pass, with a comparation improvement of 50% in worst cases`, group: `bubble`, }, { enumerableIf: _ => true, }); function bubbleSort11( arr, comparator, flags) // Non-optimized (for↬for) version // (Go through outer loop full size) { [arr, comparator] = anref(arr, comparator, flags); let n = (arr && arr.length) || 0; // at least 2 items control if (n < 2) n = 0; // measurement control const [fn, cnt] = measurefy.innery( bubbleSort11, 3); /* * The outer loop moves from the first item in the array * to the last item in the array. */ for (let i = 0; i < n; i++) { // notify loop cnt && cnt[0]++; /* * The inner loop also moves from the first item in the array towards * a stopping point, bubbling up items from left to the right. * The `stop` value is the length of the array minus one. The minus one * is necessary because we are comparing each item to the next * item, and the last item doesn't have a next item to compare to. */ for (let j = 0; j < n - 1; j++) { // notify pass cnt && cnt[1]++; /* * if pair is out of order */ if (comparator( arr[j], arr[j+1]) > 0) { /* * swap them */ swap(arr, j, j+1); // notify swap cnt && cnt[2]++; } } } // broadcast measurements cnt && measurefy.stats01(fn, cnt); return arr; } odefpropsAs(bubbleSort11, { desc: `Worst-optimized (for↬for) version. Worst Features: ⋇ Go always through the full size outer loop`, group: `bubble`, }, { enumerableIf: _ => true, }); function bubbleSort110( arr, comparator, flags) // Non-optimized (for+for) version // (one outer loop less) { [arr, comparator] = anref(arr, comparator, flags); let n = (arr && arr.length) || 0; // measurement control const [fn, cnt] = measurefy.innery( bubbleSort110, 3); /* * The outer loop moves from the first item in the array * to the last item in the array minus one. * The minus one avoid last loop, where seems all items are already sorted * in, and also controls the entrance with at least 2 items to compare */ for (let i = 0; i < n - 1; i++) { // notify loop cnt && cnt[0]++; /* * The inner loop also moves from the first item in the array towards * a stopping point, bubbling up items from left to the right. * The `stop` value is the length of the array minus one. The minus one * is necessary because we are comparing each item to the next * item, and the last item doesn't have a next item to compare to. */ for (let j = 0; j < n - 1; j++) { // notify pass cnt && cnt[1]++; /* * if pair is out of order */ if (comparator( arr[j], arr[j+1]) > 0) { /* * swap them */ swap(arr, j, j+1); // notify swap cnt && cnt[2]++; } } } // broadcast measurements cnt && measurefy.stats01(fn, cnt); return arr; } odefpropsAs(bubbleSort110, { desc: `Non-optimized (for↬for) version. Features: ⋇ With one outer loop less.`, group: `bubble`, }, { enumerableIf: _ => true, }); function bubbleSort111( arr, comparator, flags) // Non-optimized (for↬for) version // (one outer loop less and flagging changes) { [arr, comparator] = anref(arr, comparator, flags); let n = (arr && arr.length) || 0; // at least 2 items control let swapped = n > 1; // measurement control const [fn, cnt] = measurefy.innery( bubbleSort111, 3); /* * The outer loop moves from the first item in the array * to the last item in the array minus one, or until * no more changes are needed. * The minus one avoid last loop, where all items are already sorted in, * and also controls the entrance with at least 2 items to compare */ for (let i = 0; i < n - 1 && swapped; i++) { // notify loop cnt && cnt[0]++; /* * reset flag on loop entering because it might be altered from * a previous iteration */ swapped = false; /* * The inner loop also moves from the first item in the array towards * a stopping point, bubbling up items from left to the right. * The `stop` value is the length of the array minus one. The minus one * is necessary because we are comparing each item to the next * item, and the last item doesn't have a next item to compare to. */ for (let j = 0; j < n - 1; j++) { // notify pass cnt && cnt[1]++; /* * if pair is out of order */ if (comparator( arr[j], arr[j+1]) > 0) { /* * swap them and remember * something changed */ swap(arr, j, j+1); swapped = true; // notify swap cnt && cnt[2]++; } } } // broadcast measurements cnt && measurefy.stats01(fn, cnt); return arr; } odefpropsAs(bubbleSort111, { desc: `Non-optimized (for↬for) version. Features: ⋇ Flagging swap changes. ⋇ With one outer loop less`, group: `bubble`, }, { enumerableIf: _ => true, }); function bubbleSort12( arr, comparator, flags) // Finnest-optimized (for↬for) version // (reducing to n-last sorted items) { [arr, comparator] = anref(arr, comparator, flags); let n = (arr && arr.length) || 0; // at least 2 items control if (n < 2) n = 0; // measurement control const [fn, cnt] = measurefy.innery( bubbleSort12, 3); /* * The outer loop moves from the first item in the array * to the last item in the array. */ for (let i = 0; i < n; i++) { // notify loop cnt && cnt[0]++; /* * The inner loop also moves from the first item in the array towards * a stopping point, bubbling up items from left to the right. * The `stop` value is the length of the array minus the position * of the outer loop minus one. This stop position is used because * items start by being sorted at the back of the array (`the rabbits`) * and increasing towards the front of the array * (where `the turtles` are). The minus one is necessary because * we are comparing each item to the next item, and the last item * doesn't have a next item to compare to. */ for (let j = 0; j < n-i-1; j++) { // notify pass cnt && cnt[1]++; /* * if pair is out of order */ if (comparator( arr[j], arr[j+1]) > 0) { /* * swap them */ swap(arr, j, j+1); // notify swap cnt && cnt[2]++; } } } // broadcast measurements cnt && measurefy.stats01(fn, cnt); return arr; } odefpropsAs(bubbleSort12, { desc: `Finnest-optimized (for↬for) version. Features: ⋇ Reducing to n-last sorted items with each loop.`, group: `bubble`, }, { enumerableIf: _ => true, }); function bubbleSort120( arr, comparator, flags) // Nearest-optimized (for↬for) version // (reducing to n-last sorted items and with one outer loop less) { [arr, comparator] = anref(arr, comparator, flags); let n = (arr && arr.length) || 0; // measurement control const [fn, cnt] = measurefy.innery( bubbleSort120, 3); /* * The outer loop moves from the first item in the array * to the last item in the array, minus one. * The minus one avoid last loop, where all items are already sorted in, * and also controls the entrance with at least 2 items to compare */ for (let i = 0; i < n - 1; i++) { // notify loop cnt && cnt[0]++; /* * The inner loop also moves from the first item in the array towards * a stopping point, bubbling up items from left to the right. * The `stop` value is the length of the array minus the position * of the outer loop minus one. This stop position is used because * items start by being sorted at the back of the array (`the rabbits`) * and increasing towards the front of the array * (where `the turtles` are). The minus one is necessary because * we are comparing each item to the next item, and the last item * doesn't have a next item to compare to. */ for (let j = 0; j < n-i-1; j++) { // notify pass cnt && cnt[1]++; /* * if pair is out of order */ if (comparator( arr[j], arr[j+1]) > 0) { /* * swap them */ swap(arr, j, j+1); // notify swap cnt && cnt[2]++; } } } // broadcast measurements cnt && measurefy.stats01(fn, cnt); return arr; } odefpropsAs(bubbleSort120, { desc: `Nearest-optimized (for↬for) version. Features: ⋇ Reducing to n-last sorted items with each loop. ⋇ With one outer loop less.`, group: `bubble`, }, { enumerableIf: _ => true, }); function bubbleSort121( arr, comparator, flags) // Full-optimized (for↬for) version // (reducing to n-last sorted items, flagging changes and with one outer loop less) { [arr, comparator] = anref(arr, comparator, flags); let n = (arr && arr.length) || 0; // at least 2 items control let swapped = n > 1; // measurement control const [fn, cnt] = measurefy.innery( bubbleSort121, 3); /* * The outer loop moves from the first item in the array * to the last item in the array, minus one. * The minus one avoid last loop, where all items are already sorted in, * and also controls the entrance with at least 2 items to compare */ for (let i = 0; i < n - 1 && swapped; i++) { // notify loop cnt && cnt[0]++; /* * reset flag on loop entering because it might be altered from * a previous iteration */ swapped = false; /* * The inner loop also moves from the first item in the array towards * a stopping point, bubbling up items from left to the right. * The `stop` value is the length of the array minus the position * of the outer loop minus one. This stop position is used because * items start by being sorted at the back of the array (`the rabbits`) * and increasing towards the front of the array * (where `the turtles` are). The minus one is necessary because * we are comparing each item to the next item, and the last item * doesn't have a next item to compare to. */ for (let j = 0; j < n-i-1; j++) { // notify pass cnt && cnt[1]++; /* * if pair is out of order */ if (comparator( arr[j], arr[j+1]) > 0) { /* * swap them and remember * something changed */ swap(arr, j, j+1); swapped = true; // notify swap cnt && cnt[2]++; } } } // broadcast measurements cnt && measurefy.stats01(fn, cnt); return arr; } odefpropsAs(bubbleSort121, { desc: `Full-optimized (for↬for) version. Features: ⋇ Reducing to n-last sorted items with each loop. ⋇ Flagging swap changes. ⋇ With one outer loop less.`, group: `bubble`, }, { enumerableIf: _ => true, }); /** * Performs an in-place/inmutable sort of an iterable collection with * `Cocktail Sort` algorithm using provided `comparator` callback to order items. * * Cocktail shaker sort, also known as bidirectional bubble sort, cocktail sort, * shaker sort (which can also refer to a variant of selection sort), ripple * sort, shuffle sort, or shuttle sort, is an extension of bubble sort. * This algorithm extension works in the line of operating in two directions. * This mitigates the `rabbits and turtles problem` presented in bubble sort, * moving these heavy items (turtles) more quickly to the beginning of the list, * though it provides only marginal performance improvements. * * An example of a list that proves this point is the list (2,3,4,5,1), which * would only need to go through one pass of cocktail sort to become sorted, * but if using an ascending bubble sort would take four passes. However one * cocktail sort pass should be counted as two bubble sort passes. * Typically cocktail sort is less than two times faster than bubble sort. * * Another optimization could be applied is remembering where the last actual * swap has been done. In the next iteration, there will be no swaps beyond this * limit and the algorithm will do shorter passes. As the cocktail shaker sort * goes bidirectionally, the range of possible swaps, which is the range to be * tested, will reduce per pass converging to the middle of the structure, * thus the overall running time is reduced slightly (about +33%). * * Worst-case performance: * O(n^2) comparisons, * O(n^2) swaps * Best-case performance: * O(n) comparisons, * O(n) swaps * Average performance: * O(n^2) comparisons, * O(n^2) swaps * Worst-case space complexity: * O(1) total, * O(1) auxiliary * * @param {Array<*>} arr * The collection to sort. * @param {Comparator|ComparatorCallback} comparator * The caller used to compare items. * Receives 2 parameters with values to compare and return 0 if are equals, * negative values when second value is greather than first and positives * on otherwise. * @return {Array<*>} sorted. * @public */ function cocktailSort( arr, comparator, flags) // Optimized version { [arr, comparator] = anref(arr, comparator, flags); let n = (arr && arr.length) || 0; /* * Holds the index of lastest sorted item by the bottom. * Stating at zero because we want to iterate from the first item. */ let nl = 0, /* * Holds the index of lastest sorted item by the top. * The minus one is necessary because we are comparing each item * to the next item, and the last item doesn't have a next item * to compare to. */ nr = n - 1, // at least 2 items hack swapped = n > 1; // measurement control const [fn, cnt] = measurefy.innery( cocktailSort, 5); /* * The outer loop moves while there are no more positions to swap * or stops when the middle of structure is reached. */ while (swapped && nl < nr) { // notify loop cnt && cnt[0]++; /* * reset flag on loop entering because it might be altered from * a previous iteration */ swapped = false; /* * This inner loop moves from the first item in the array which maybe * a swapping is needed towards a stopping point, marking if it happens * some swapping movement. * It does bubbling up items from left to the right. * The `stop` value matches with the bottom index of most recently * sorted item by the right, which was resolved at previous iteration. */ for (let i = nl; i < nr; i++) { /* * if pair is out of order */ if (comparator( arr[i], arr[i+1]) > 0) { /* * swap them and remember * something changed */ swap(arr, i, i+1); swapped = true; // notify swap cnt && cnt[3]++; } // notify pass cnt && cnt[1]++; } /* * if nothing moved, then is sorted */ if (!swapped) break; /* * otherwise, reset flag so that it can be used in next stages */ swapped = false; /* * move `end` pointer back, * because items at the end is in its rightful spot * and then, we no longer need to consider it unsorted */ nr -= 1; /* * This other inner loop bubbles down, from end to the start, with same * comparison as in previous stage. * The `stop` value matches with the top index of most recently * sorted item by the left, which was resolved at previous iteration. */ for (let i = nr-1; i >= nl; i--) { /* * if pair is out of order */ if (comparator( arr[i], arr[i+1]) > 0) { /* * swap them and remember * something changed */ swap(arr, i, i+1); swapped = true; // notify swap cnt && cnt[4]++; } // notify pass cnt && cnt[2]++; } /* * increase `start` pointer, because the last stage would have moved * the next smallest number to its rightful spot. */ nl += 1; } // broadcast measurements cnt && measurefy.stats02(fn, cnt); return arr; } odefpropsAs(cocktailSort, { desc: `Full-optimized (while🚩↬2⨯for) version. Features: ⋇ Bidirectional bubble sort. ⋇ Flagging swap changes. ⋇ Breaking if sorted after bubbling on each direction. ⋇ Reducing to 2⨯ n-last sorted items with each loop, one by each direction.`, group: `bidir-bubble`, }, { enumerableIf: _ => true, }); function shakerSort( arr, comparator, flags) // maybe optimized a bit more to halfing passes when already was provided in reverse order { [arr, comparator] = anref(arr, comparator, flags); let n = (arr && arr.length) || 0; // measurement control const [fn, cnt] = measurefy.innery( shakerSort, 5); for (let k = 0; k < n/2; k++) { // notify loop cnt && cnt[0]++; // reset flag on loop entering // because it might be true from // a previous iteration let swapped = false; // bubble up from left to right for (let i = k; i < n-k-1; i++) { /* * if pair is out of order */ if (comparator( arr[i], arr[i+1]) > 0) { /* * swap them and remember * something changed */ swap(arr, i, i+1); swapped = true; // notify swap cnt && cnt[3]++; } // notify pass cnt && cnt[1]++; } /* * if nothing moved, then is sorted */ if (!swapped) break; /* * otherwise, reset flag so that it can be used in next stages */ swapped = false; // bubble down from end to start for (let i = n-2-k; i > k; i--) { /* * if pair is out of order */ if (comparator( arr[i-1], arr[i]) > 0) { /* * swap them and remember * something changed */ swap(arr, i-1, i); swapped = true; // notify swap cnt && cnt[4]++; } // notify passes cnt && cnt[2]++; } /* * if nothing moved, then is sorted */ if (!swapped) break; } // broadcast measurements cnt && measurefy.stats02(fn, cnt); return arr; } odefpropsAs(shakerSort, { desc: `Full-optimized (for½🚩↬2⨯for) version. Features: ⋇ Bidirectional bubble sort. ⋇ Flagging swap changes to control loops. ⋇ Breaking if sorted after bubbling on each direction. ⋇ Reducing to 2⨯ n-last sorted items with each loop, one by each direction. * As collateral effect, exists a passes control reduced by half when array was already provided in reverse order`, group: `bidir-bubble`, }, { enumerableIf: _ => true, }); oassign(measurefy, { stats01: (fn, c) => { const inst = { loops: c[0], get passes() { return this.passesUp; }, get swaps() { return this.swapsUp; }, passesUp: c[1], swapsUp: c[2], get message() { return `⇶ Passes[⇈]= ${this.passes} ↻${this.loops} ↹ Swaps[⇈]= ${this.swaps}`; }, }; fn.$$measurefy.stats = inst; return inst; }, stats02: (fn, c) => { const inst = { loops: c[0], get passes() { return this.passesUp + this.passesDown; }, get swaps() { return this.swapsUp + this.swapsDown; }, passesUp: c[1], swapsUp: c[3], passesDown: c[2], swapsDown: c[4], get message() { return `⇶ Passes[${this.passesUp} ⇈᜶⇊ ${this.passesDown}]= ${this.passes} ↻${this.loops} ↹ Swaps[${this.swapsUp} ⇈/⇊ ${this.swapsDown}]= ${this.swaps}`; }, }; fn.$$measurefy.stats = inst; return inst; }, }); //applyNamingAlias(bubbleSort, 'sinkingSort'); //applyNamingAlias(cocktailSort, 'bidirectionalBubbleSort,cocktailShakerSort,shakerSort,rippleSort,shuffleSort'); module.exports = { // // Utils // measurefy, swap, swaptmp, halfShuffler, indexFillerFactory, indexFiller: indexFillerFactory(), halfIndexFiller: indexFillerFactory({ name: 'halfIndexFiller', rnd: 0, lfactor: 2, }), halfDownIndexFiller: indexFillerFactory({ name: 'halfDownIndexFiller', rnd: -1, lfactor: 2, }), halfUpIndexFiller: indexFillerFactory({ name: 'halfUpIndexFiller', rnd: 1, lfactor: 2, }), // // Comparators // Comparator, Comparable, numbers: { naturalOrder, reverseOrder, }, reversedComparator, methodComparatorFactory, comparableComparator: methodComparatorFactory(), // // Algorithms // //bubbleSort: bubbleSort03, //bubbleSort: bubbleSort121, bubbleSort01, bubbleSort02, bubbleSort03, bubbleSort11, bubbleSort110, bubbleSort111, bubbleSort12, bubbleSort120, bubbleSort121, //cocktailSort, //shakerSort, }; //cout(module.exports); // test if not an import from other module ((module === process.mainModule) && // and execute it when truth (function main( argv, exports, // array size n = 666, // testing sample loops tl = 55) { perf.mark('BEGIN'); const perfObs = startPerfObserving(); // filter testables from module exports const algorithms = ovalues(exports) .filter(isBasAlgorithm); const comparator = //reversedComparator(naturalOrder); //reverseOrder; naturalOrder; // // build a shuffled array of n-numbers // const shuffler = halfShuffler ; const filler = exports.indexFiller //exports.halfIndexFiller ; perf.mark('Gen'); const expected = [...Array(n)] .map(filler) //.reverse() ; perf.mark('Shuffle copy'); const arr = [...expected] .sort(shuffler) ; perf.mark('Shuffled'); perf.measure(`\n GenArray ${n} items`, 'Gen', 'Shuffle copy'); perf.measure(`Shuffling ${n} items`, 'Shuffle copy', 'Shuffled'); cout(); cout(`Testing ${algorithms.length} algorithms ⨯${tl} over ${n} items...`, n<50?arr:''); perf.mark('ALG-INI'); algorithms // // measure & assert testing // .map((fn, i) => { !i && cout(); cout(` ⋇ #${i+1} On ${fn.name} ...`); const m = measurefy(fn, { times: tl, })(arr, comparator); const ok = util.isDeepStrictEqual( m.result, expected); return { fn, index: i, ok, ...m, }; }) // // sort by fastest in group // .sort((a, b) => { return (a.mean.std + a.moe.std > b.mean.std + b.moe.std ? 1 : -1); }) // // print // .forEach((v, i) => { !i && (cout(), cout("=== TOP RESULTS ATTENDING PERFORMANCE ===")); const { fn, index, ok, result: r, duration, mean, moe, deviation, sem, stats, //sample, //...rest } = v; cout(` #${i+1}⁝⁝⁝🔰 %s: ⨯%s%sTEST ${ok ? '✔OK' : '❌KO'} %s :=📊 📊:STATS:📊 📊=: %s ⏲(ms): μ≅ %s ∑ₗ %s μ± %s 📐Dev/SEM: σ %s σᵪ %s `, fn.name, tl, " ".repeat(40 - fn.name.length - `${i+1}${tl}`.length - 19), fn.desc .split(/\n+/ig) .map(v => spaces(3) + v) .join('\n'), stats.message ?.split(/\n+/ig) .map(v => spaces(2) + v) .join('\n'), mean.std, duration.std, moe.std, deviation.std, sem.std, //rest, //sample[1], (!ok && r)||''); }); perf.mark('ALG-END'); cout(`\n=#============@@@@@@@@@@============#=`); perf.measure(`All ${algorithms.length} algorithms ⨯${tl}`, 'ALG-INI', 'ALG-END'); perf.measure('END'); // autodisconnect perf.mark('END'); // autodisconnect //obs.disconnect(); //cout("UPTIME:", process.uptime()); })( process.argv, module.exports ));

Benchmark & optimizing sort algorithms: bubble, cocktail, insertion, selection, merge, quicksort...