2d:null 2e:["$","title",null,{"children":"Shuffling Algorithms | Jonathan Helfman | Observable"}] 33:T58a,md` A fork of stwind's wonderful https://observablehq.com/@stwind/sorting-algorithms to add - shuffling algorithms, - colors that vary in brightness uniformly, which although not as pretty as the original, helps to further clarify the sort order, and - a function to concat multiple sorts and shuffles. The charts in this notebook use two different time scales: - the first 19 charts use a common time scale. - the last three charts use a common time scale that is different from the first 19. Implications: - time-based comparisons between the first 19 and the last 3 are invalid. - because the first 19 use a common time scale, the fastest algorithms have their steps more compressed than they would if they were scaled to use their own maximum time. The charts in this notebook show time running horizontally from left-to-right. Charts in an Observable notebook seem have a maximum width. Implications: Because these visualizations have a maximum width, - they are limited to only be able to show a limited number of values or stripes -- any more values and the longer-running sorts would not have time to finish before running off the right edge, and - they make it difficult to appreciate the difference between some algorithms, such as Naive and Fisher-Yates shuffles. See the next notebook https://observablehq.com/@jonhelfman/shuffling-algorithms/2 for a vertical option that addresses these issues. `34:Tfb3,smoothSort = { class Shapes { static get LN() { return [ 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457, 1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703, 48315633, 78176337, 126491971, 204668309, 331160281, 535828591, 866988873,1402817465, 2269806339, 3672623805 ]; } static leftChild(tree) { return tree[0] > 1 ? [tree[0] - 1, tree[1]] : undefined; } static rightChild(tree) { return tree[0] > 1 ? [tree[0] - 2, tree[1] + Shapes.LN[tree[0]-1]] : undefined; } static rootOffset(tree) { return tree[1] + Shapes.LN[tree[0]] - 1; } constructor() { this.trees = []; } push() { const n = this.trees.length; if (!this.canCollapse()) { if (n == 0) { this.trees.push([1, 0]); } else { const last = this.trees[n-1]; if (last[0] == 1) { this.trees.push([0, last[1] + 1]); } else { this.trees.push([1, last[1] + Shapes.LN[last[0]]]); } } } else { this.collapseLast(); } } pop() { const last = this.trees.pop(); if (last && last[0] > 1) { this.trees.push([last[0] - 1, last[1]]); this.trees.push([last[0] - 2, last[1] + Shapes.LN[last[0]-1]]); } } collapseLast() { this.trees.pop(); const last = this.trees.pop(); this.trees.push([last[0]+1, last[1]]); } canCollapse() { if (this.trees.length < 2) return false; const n = this.trees.length; const tree1 = this.trees[n-1], tree2 = this.trees[n-2]; return tree1[0] + 1 == tree2[0]; } } return values => { const n = values.length; const { copy, history } = prepare(values); let time = 1; const shapes = new Shapes(); function balance(tree) { let left = Shapes.leftChild(tree); let right = Shapes.rightChild(tree); if (left) { const p = Shapes.rootOffset(tree); const l = Shapes.rootOffset(left); const r = Shapes.rootOffset(right); if (copy[l] > copy[p] && copy[l] > copy[r]) { swap(l, p, ++time, copy, history); balance(left); } else if (copy[r] > copy[p]) { swap(r, p, ++time, copy, history); balance(right); } } } function shouldSwapHeaps(i, j) { const tree1 = shapes.trees[i]; const tree2 = shapes.trees[j]; const left = Shapes.leftChild(tree1); const right = Shapes.rightChild(tree1); const a = Shapes.rootOffset(tree1); const b = Shapes.rootOffset(tree2); if (copy[a] < copy[b]) { if (!left || copy[Shapes.rootOffset(left)] < copy[b]) { return !right || copy[Shapes.rootOffset(right)] < copy[b]; } else { return false; } } else { return false; } } function swapHeaps(i, j) { const a = Shapes.rootOffset(shapes.trees[i]); const b = Shapes.rootOffset(shapes.trees[j]); swap(a, b, ++time, copy, history); } function rectify(i) { if (shapes.trees.length == 1) { balance(shapes.trees[0]); } else if (shapes.trees.length > 1) { let cur = i; for (let j = i - 1; j >= 0;j--) { if (shouldSwapHeaps(cur, j)) { swapHeaps(cur, j); cur = j; } } balance(shapes.trees[cur]); } } for (let i = 0; i < n; i++) { shapes.push(); rectify(shapes.trees.length-1); } for (let i = 0; i < n; i++) { const before = shapes.trees.length; shapes.pop(); if (before < shapes.trees.length) { rectify(shapes.trees.length - 2); rectify(shapes.trees.length - 1); } } return { time, history }; } }35:T4c1,plot = (result, { maxTime, scales }) => { const svg = d3.select(DOM.svg(width, params.height)); const lines = svg.append('g').classed('lines', true) .attr('transform',`translate(0,${params.lineWidth})`); const data = makePointsData(result, maxTime); const polylinePoints = d => d[1].map(([t, y]) => `${scales.x(t)},${scales.y(y)}`).join(' '); lines.selectAll('.line').data(data) .join(enter => enter.append('g').call(g => { g.append('polyline').classed('line-border', true) .attr('points', polylinePoints) .attr('stroke', d3.hsl(0,0,0.1)) .attr('stroke-width', `${params.lineWidth+1.5}px`) .attr('stroke-linecap', 'round') .attr('stroke-linejoin', 'round') .attr('fill', 'none'); g.append('polyline').classed('line-fill', true) .attr('points', polylinePoints) .attr('stroke', d => scales.color(scales.values(d[0]))) .attr('stroke-width', `${params.lineWidth}px`) .attr('stroke-linecap', 'round') .attr('stroke-linejoin', 'round') .attr('fill', 'none'); })) .classed('line', true); svg.on('click', () => { mutable values = genValues(); }); return svg.node(); }36:[] 31:{"id":"c810f46e0742d6fe","slug":"shuffling-algorithms","title":"Shuffling Algorithms","thumbnail":"d52b7b54ed571c33e4750dfef38df237661bbdeb017ca78d3f3c70b2956a4b1e","access_level":"public","create_time":"$D2019-11-26T16:22:58.189Z","update_time":"$D2019-12-07T21:42:33.982Z","view_time":null,"first_public_time":"$D2019-11-27T01:39:29.691Z","has_unpublished_edits":null,"fork":{"id":"b445dd50dec51620","slug":"sorting-algorithms","title":"Sorting Algorithms","owner":{"id":"7fad80bf128915e9","login":"stwind","name":"Zihou Ng"}},"stars":4,"starred":false,"owner":{"type":"team","id":"6c3b7072b5e94b97","login":"jonhelfman","name":"Jonathan Helfman","avatar_url":"https://avatars-next.observableusercontent.com/a404535763c16060490629d896d876b5b4cea8c603c4993b2aaed749a15b041a","tier":"starter_2024"},"version":2920,"publish_version":2920,"role":null,"authored":false,"authors":[{"type":"individual","id":"ba5c813f0f621f19","login":"jonhelfman","name":"Jonathan Helfman","avatar_url":"https://avatars-next.observableusercontent.com/a404535763c16060490629d896d876b5b4cea8c603c4993b2aaed749a15b041a","tier":null}],"members":[{"type":"individual","id":"ba5c813f0f621f19","login":"jonhelfman","name":"Jonathan Helfman","avatar_url":"https://avatars-next.observableusercontent.com/a404535763c16060490629d896d876b5b4cea8c603c4993b2aaed749a15b041a","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":6,"collection":{"id":"975bb2d9548b1596","slug":"algorithms","title":"Algorithms","owner":{"id":"6c3b7072b5e94b97","login":"jonhelfman","name":"Jonathan Helfman"}},"type":"notebook","body":{"title":"Shuffling Algorithms","cells":[{"id":0,"value":"idTop = md`# Shuffling Algorithms`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2640,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2691,"value":"md`### Naive Shuffle`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2561,"value":"plot(results.shuffle, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2916,"value":"results.shuffle","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2918,"value":"settings","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2695,"value":"md`### Fisher-Yates Shuffle`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2617,"value":"{\n const { copy, history } = prepare(svalues);\n return plot( fisherYatesShuffle(copy, history), settings)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2760,"value":"md `### Riffle Shuffle\n\nClearly wrong`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2725,"value":"{\n const { copy, history } = prepare(svalues);\n return plot( riffleShuffle(copy, history), settings)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2754,"value":"md`### Riffle Shuffle2\nCloser to expected`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2729,"value":"{\n const { copy, history } = prepare(svalues);\n return plot( riffleShuffle2(copy, history), settings)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2778,"value":"md`### Riffle Shuffle3\n\nAdd some randomness`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2776,"value":"{\n const { copy, history } = prepare(svalues);\n return plot( riffleShuffle3(copy, history), settings)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":309,"value":"idInsertion = md`### Insertion Sort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2789,"value":"{\n const { copy, history } = prepare(values);\n return plot( insertionSort(copy, history), settings)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1664,"value":"idCyclesort = md`### Cycle Sort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2836,"value":"{\n const { copy, history } = prepare(values);\n return plot( cyclesort(copy, history), settings)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1172,"value":"isCountingsort = md`### Counting Sort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2864,"value":"{\n const { copy, history } = prepare(values);\n return plot( countingSort(copy, history), settings)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2552,"value":"naiveShuffle = (values) => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1;\n for (let i = 0;i < n;i++) {\n const j = Math.floor(Math.random() * n)\n swap(i, j, time++, copy, history);\n }\n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2570,"value":"fisherYatesShuffle = (values, history=new Map(), time=1) => {\n const n = values.length;\n const copy = values.map(v => v)\n for (let i = 1;i < n;i++) {\n const j = Math.floor(Math.random() * (i + 1))\n swap(i, j, time++, copy, history);\n }\n return { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2718,"value":"// from https://dev.to/s_awdesh/everyday-im-shuffling-im-a-card--fire-1f8b\nriffleShuffle = (values, history=new Map(), time=1) => {\n const n = values.length;\n const copy = values.map(v => v)\n \n let i = Math.floor(values.length/2)\n let j = values.length-1\n while (i > 0) {\n swap(i--, j--, time++, copy, history);\n }\n return { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2727,"value":"riffleShuffle2 = (values, history=new Map(), time=1) => {\n const n = values.length;\n const copy = values.map(v => v)\n \n let i = Math.floor(values.length/2)\n let j = 0\n while (i < values.length) {\n swap(i, j, time++, copy, history);\n i += 2\n j += 2\n }\n return { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2768,"value":"riffleShuffle3 = (values, history=new Map(), time=1) => {\n const n = values.length;\n const copy = values.map(v => v)\n \n let i = Math.floor(values.length/2)\n let j = 0\n while (i < values.length) {\n swap(i, j, time++, copy, history);\n i += 1 + Math.floor(Math.random() * 2)\n j += 1 + Math.floor(Math.random() * 2)\n }\n return { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":271,"value":"// re-implementation of insertionSort to not set time or history\ninsertionSort = (values, history=new Map(), time=1) => {\n const n = values.length;\n //const { copy, history } = prepare(values);\n const copy = values.map(d => d)\n \n //let time = 1;\n for (let i = 1;i < n;i++) {\n let j = i;\n while (j > 0 && copy[j] < copy[j-1]) {\n swap(j, --j, time++, copy, history);\n }\n }\n return { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1781,"value":"// re-implementation of cyclesort to not set time or history\ncyclesort = (values, history=new Map(), time=1) => {\n //const { copy, history } = prepare(values);\n //let time = 1;\n const copy = values.map(v => v)\n \n for (let i = 0; i < values.length; i++) {\n if (copy[i] != i) {\n let prev = copy[i], n = prev;\n \n for (; n != i; n = prev) {\n const tmp = copy[n];\n history.get(prev).push([time++, n]);\n copy[n] = prev;\n prev = tmp;\n }\n \n history.get(prev).push([time++, n]);\n copy[n] = prev;\n }\n }\n \n return { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2857,"value":"countingSort = (values, history=new Map(), time=1) => {\n const n = values.length;\n //const { copy, history } = prepare(values);\n //let time = 1;\n const copy = values.map(v => v)\n \n for (let i = 0; i < n;i++) {\n if (copy[i] != i) {\n history.get(i).push([time++, i]);\n copy[i] = i;\n }\n }\n \n return { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2794,"value":"md`### Experimental Braid function to run multiple sorts and shuffles`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2819,"value":"function braid (alglist) {\n let { copy, history } = prepare(svalues);\n let time = 1\n alglist.forEach(a => {\n const rc = a(copy, history, time);\n copy = rc.copy\n history = rc.history\n time = rc.time\n })\n \n return {copy, history, time}\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2598,"value":"{\n return plot( braid ([riffleShuffle, riffleShuffle2, countingSort, riffleShuffle3, countingSort]), settings )\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2715,"value":"{\n return plot( braid ([ fisherYatesShuffle, riffleShuffle2]), settings )\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2780,"value":"{\n return plot( braid ([ riffleShuffle3, countingSort, riffleShuffle3, cyclesort, fisherYatesShuffle]), settings )\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2797,"value":"md`## Below are unchanged from original notebook`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":642,"value":"idQuicksort = md`### Quicksort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":639,"value":"plot(results.quick, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":492,"value":"quicksort = values => {\n const { copy, history } = prepare(values);\n let time = 1;\n \n function partition(left, right, pivot) {\n const v = copy[pivot];\n swap(pivot, --right, ++time, copy, history);\n for (let i = left; i < right; i++) {\n if (copy[i] <= v) {\n swap(i, left++, ++time, copy, history);\n }\n }\n swap(left, right, ++time, copy, history);\n return left;\n }\n \n function sort(left, right) {\n if (left < right - 1) {\n const pivot = partition(left, right, (left + right) >> 1);\n sort(left, pivot);\n sort(pivot + 1, right);\n }\n }\n \n sort(0, values.length);\n return { time, history }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":718,"value":"idMergesort = md`### Mergesort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":712,"value":"plot(results.merge, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":676,"value":"mergesort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1;\n \n function sort(lo, hi) {\n if (lo == hi - 1) return;\n \n const mid = (lo + hi) >> 1;\n sort(lo, mid);\n sort(mid, hi);\n \n let i = lo, j = mid;\n while (i < j && j < hi) {\n if (copy[i] < copy[j]) {\n i++;\n } else {\n time++;\n const t = copy[j];\n \n for (let k = j; k > i;k--) {\n history.get(copy[k-1]).push([time, k]);\n copy[k] = copy[k-1];\n }\n \n history.get(t).push([time++, i]);\n copy[i] = t;\n i++; j++;\n }\n }\n }\n \n sort(0, n);\n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1113,"value":"idShellsort = md`### Shellsort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1116,"value":"plot(results.shell, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1096,"value":"shellsort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1;\n let h = 1;\n while (h < n / 3) h = h * 3 - 1;\n \n while (h >= 1) {\n for (let i = h;i < n; i++) {\n for (let j = i; j >= h && copy[j] < copy[j-h]; j -= h) {\n swap(j, j - h, ++time, copy ,history);\n }\n }\n \n h = Math.floor(h/3);\n }\n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1152,"value":"idHeapsort = md`### Heapsort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1155,"value":"plot(results.heapsort, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1123,"value":"heapsort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1;\n \n function sink(i, n) {\n let child = (i << 1) + 1;\n while (child < n) {\n if (child + 1 < n && copy[child] < copy[child+1])\n child++;\n\n if (copy[child] > copy[i]) {\n swap(i, child, time++, copy, history);\n } else {\n break;\n }\n i = child;\n child = (i << 1) + 1;\n }\n }\n \n for (let i = Math.floor(n/2);i >= 0;i--) {\n sink(i, n);\n }\n \n let end = n - 1;\n while (end > 0) {\n swap(0, end, time++, copy, history);\n sink(0, end--);\n }\n\n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1372,"value":"idRadixSort = md`### Radix Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1508,"value":"plot(results.radix, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1437,"value":"radixsort = values => {\n const { copy, history } = prepare(values);\n let time = 1;\n \n function sort(base) {\n const counts = Array(10).fill(0);\n for (const v of copy) {\n const key = Math.floor(v / base) % 10;\n counts[key]++;\n }\n \n for (let i = 1; i < 10; i++)\n counts[i] += counts[i-1];\n \n const cp = copy.slice();\n for (let i = cp.length - 1; i >= 0;i--) {\n const v = cp[i];\n const key = Math.floor(v / base) % 10;\n const pos = --counts[key];\n \n history.get(v).push([time++, pos]);\n copy[pos] = v;\n }\n }\n \n for (let exp = 1; exp < 100; exp *= 10)\n sort(exp);\n \n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1670,"value":"idBitonicSort = md`### Bitonic Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1725,"value":"plot(results.bitonic, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1723,"value":"bitonicSort = values => {\n const { copy, history } = prepare(values);\n let time = 1;\n \n function comp(i, j, asc) {\n if (copy[i] > copy[j] == asc) {\n swap(i, j, time++, copy, history);\n }\n }\n \n function merge(lo, n, asc) {\n if (n > 1) {\n const k = n / 2;\n for (let i = lo; i < lo + k; i++) {\n comp(i, i + k, asc);\n }\n merge(lo, k, asc);\n merge(lo + k, k, asc);\n }\n }\n \n function sort(lo, n, asc) {\n if (n > 1) {\n const k = n / 2;\n sort(lo, k, true);\n sort(lo + k, k, false);\n merge(lo, n, asc);\n }\n }\n \n sort(0, values.length, true);\n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1673,"value":"md`\n\nRefererences\n\n* [Bitonic Sort - GeeksforGeeks](https://www.geeksforgeeks.org/bitonic-sort/)\n* [Bitonic sort](http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1667,"value":"md`\n\nReferences\n\n* [Cyclesort - a curious little sorting algorithm](https://corte.si/posts/code/cyclesort/index.html)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1651,"value":"idTimsort = md`### Timsort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1964,"value":"plot(results.timsort, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1960,"value":"timsort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1;\n const RUN = 4;\n \n function insertionSort(l, r) {\n for (let i = l + 1; i < r; i++) {\n let j = i;\n while (j > l && copy[j] < copy[j-1]) {\n swap(j, --j, time++, copy, history);\n }\n }\n }\n \n function merge(l, mid, r) {\n let i = l, j = mid;\n while (i < j && j < r) {\n if (copy[i] < copy[j]) {\n i++;\n } else {\n time++;\n const t = copy[j];\n \n for (let k = j; k > i;k--) {\n history.get(copy[k-1]).push([time, k]);\n copy[k] = copy[k-1];\n }\n \n history.get(t).push([time++, i]);\n copy[i] = t;\n i++; j++;\n }\n }\n }\n \n for (let i = 0; i < n; i += RUN) {\n insertionSort(i, i + RUN);\n }\n \n for (let size = RUN; size < n; size *= 2) {\n for (let i = 0; i < n; i += size * 2) {\n merge(i, i + size, Math.min(n, i + size * 2));\n }\n }\n \n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1658,"value":"md`\nReferences\n\n* [Timsort - Wikipedia](https://en.wikipedia.org/wiki/Timsort)\n* [Visualising Sorting Algorithms: Python's timsort](https://corte.si/posts/code/timsort/index.html)\n * [Timsort - a study in grayscale](https://corte.si/posts/code/timsort-grayscale/index.html)\n* [The Case for Timsort - Richard Scheiwe - Medium](https://medium.com/@rscheiwe/the-case-for-timsort-349d5ce1e414)\n* [Timsort: The Fastest sorting algorithm for real-world problems.](https://dev.to/s_awdesh/timsort-fastest-sorting-algorithm-for-real-world-problems--2jhd)\n* [TimSort - GeeksforGeeks](https://www.geeksforgeeks.org/timsort/)\n* [timsort.txt](https://bugs.python.org/file4451/timsort.txt)\n* [[1805.08612] On the Worst-Case Complexity of TimSort](https://arxiv.org/abs/1805.08612)\n* [timsort/cpp-TimSort: A C++ implementation of timsort](https://github.com/timsort/cpp-TimSort)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1837,"value":"idSmoothSort = md`### Smooth Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2387,"value":"plot(results.smooth, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2283,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1840,"value":"md`\nThis implementation is a port of [bowd/smoothsort](https://github.com/bowd/smoothsort), originally written in Rust.\n\nReferences\n\n* [Smoothsort - Wikipedia](https://en.wikipedia.org/wiki/Smoothsort)\n* [Smoothsort Demystified](http://www.keithschwarz.com/smoothsort/)\n* [E.W.Dijkstra Archive: Smoothsort, an alternative for sorting in situ (EWD 796a)](https://www.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/EWD796a.html)\n* [Smoothsort in Rust — BOWD](https://www.bowd.io/smoothsort-rust/)\n * [Leonardo numbers and Math I wish I knew — BOWD](https://www.bowd.io/leonardo-numbers)\n * [Leonardo heaps and how they work — BOWD](https://www.bowd.io/leonardo-heaps/)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"idSelection = md`### Selection Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"plot(resultsN2.selection, settingsN2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"selectionSort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1;\n \n for (let i = 0; i < n; i++) {\n let min = i;\n for (let j = i + 1;j < n; j++) { \n if (copy[j] < copy[min]) {\n min = j;\n }\n time++;\n }\n \n if (i != min) {\n swap(i, min, time, copy, history);\n }\n }\n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2175,"value":"idOddEvenSort = md`### Odd Even Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2199,"value":"plot(resultsN2.oddeven, settingsN2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2193,"value":"oddEvenSort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1, done = false;\n \n while (!done) {\n done = true;\n for (let start = 0; start < 2; start++) {\n for (let i = start; i < n - 1; i += 2) {\n time++\n if (copy[i] > copy[i+1]) {\n swap(i, i+1, time, copy, history);\n done = false;\n }\n }\n }\n }\n \n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2179,"value":"idCocktailSort = md`### Cocktail Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2215,"value":"plot(resultsN2.cocktail, settingsN2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2209,"value":"cocktailSort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1, swapped = true, start = 0, end = n;\n \n while (swapped) {\n swapped = false;\n for (let i = start; i < end; i++) {\n time++;\n if (copy[i] > copy[i+1]) {\n swap(i, i+1, time, copy, history);\n swapped = true;\n }\n }\n \n if (!swapped) break;\n swapped = false;\n \n end--;\n for (let i = end; i >= start; i--) {\n time++;\n if (copy[i] > copy[i+1]) {\n swap(i, i+1, time, copy, history);\n swapped = true;\n }\n }\n start++;\n }\n \n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":262,"value":"md`## Misc`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2116,"value":"md`### Data`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"params = ({\n numValues: 16,\n lineWidth:8,\n jitter: 0.5,\n height: 220,\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"mutable values = genValues()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2582,"value":"svalues = d3.range(values.length)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2121,"value":"md`### Results`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":287,"value":"results = ({\n //insertion: insertionSort(values),\n quick: quicksort(values),\n merge: mergesort(values),\n shell: shellsort(values),\n heapsort: heapsort(values),\n //counting: countingSort(values),\n radix: radixsort(values),\n bitonic: bitonicSort(values),\n //cycle: cyclesort(values),\n timsort: timsort(values),\n smooth: smoothSort(values),\n shuffle: naiveShuffle(svalues),\n //fisherYatesShuffle: fisherYatesShuffle(svalues)\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2095,"value":"settings = makePlotSettings(results)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2124,"value":"resultsN2 = ({\n selection: selectionSort(values),\n oddeven: oddEvenSort(values),\n cocktail: cocktailSort(values),\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2129,"value":"settingsN2 = makePlotSettings(resultsN2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2113,"value":"md`### Utils`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":249,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2091,"value":"makePlotSettings = results => {\n const maxTime = d3.max(d3.values(results), d => d.time) + 2;\n const scales = {\n values: d3.scaleLinear().domain([d3.min(values), d3.max(values)]).range([0.2, 0.8]),\n x: d3.scaleLinear().domain([0,maxTime]).range([0,width]),\n y: d3.scaleLinear().domain([0,values.length]).range([0,params.height]),\n //color: d3.interpolateRdYlBu\n //color: d3.interpolatePuBuGn\n color: d3.interpolateYlGnBu\n };\n return { maxTime, scales };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":145,"value":"makePointsData = ({ history }, maxTime) => {\n function makePoints(entries) {\n const res = [entries[0]];\n for (let i = 1; i < entries.length; i++) {\n const a = entries[i-1], b = entries[i];\n res.push([b[0] - params.jitter, a[1]]);\n res.push([b[0] + params.jitter, b[1]]);\n }\n res.push([maxTime, res[res.length-1][1]]);\n return res;\n }\n \n return [...history.entries()].map(([k, v]) => [k, makePoints(v)]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2035,"value":"genValues = () => d3.shuffle(d3.range(params.numValues))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":321,"value":"prepare = values => ({ \n copy: values.slice(),\n history: values.reduce((map, x, i) => map.set(x, [[0, i]]), new Map())\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":647,"value":"swap = (i, j, time, copy, history) => {\n history.get(copy[i]).push([time, j]);\n history.get(copy[j]).push([time, i]);\n \n const t = copy[i];\n copy[i] = copy[j];\n copy[j] = t;\n }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"md`## Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"d3 = require('d3@5')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":53,"value":"md`## References\n\n* [cortesi/sortvis: Sorting algorithm visualisation with Cairo](https://github.com/cortesi/sortvis)\n * [Visualising Sorting Algorithms](https://corte.si/posts/code/visualisingsorting/index.html)\n* [Visualizing Algorithms](https://bost.ocks.org/mike/algorithms/)\n * [Quicksort V - bl.ocks.org](https://bl.ocks.org/mbostock/6dcc9a177065881b1bc4)\n* [Sorting algorithm - Wikipedia](https://en.wikipedia.org/wiki/Sorting_algorithm)\n* [Big-O Algorithm Complexity Cheat Sheet](https://www.bigocheatsheet.com/)\n* [SORTING](http://sorting.at/)\n* [BonzaiThePenguin/WikiSort](https://github.com/BonzaiThePenguin/WikiSort)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1","titling":"auto"}} 32:"$31:body"