37:null 38:["$","title",null,{"children":"Sort and Shuffle Algorithm Animations | Jonathan Helfman | Observable"}] 3e:T5c7,sortAnimationPlot = { // (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(aSortResult, aSortMaxtime); //console.log(data) const polylinePoints = d => d[1].map(([t, y]) => orientation === 'horizontal' ? `${aSortScales.x(t)},${aSortScales.y(y)}` : `${aSortScales.y(y)},${aSortScales.x(t)}` ).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 => aSortScales.color(aSortScales.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(); }3f:T5e2,shuffleAnimationPlot = { // (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(aShuffleResult, aShuffleMaxtime); //console.log(data) const polylinePoints = d => d[1].map(([t, y]) => orientation === 'horizontal' ? `${aShuffleScales.x(t)},${aShuffleScales.y(y)}` : `${aShuffleScales.y(y)},${aShuffleScales.x(t)}` ).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 => aShuffleScales.color(aShuffleScales.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(); }40:T447,timsort = (values, history=new Map(), time=1) => { const n = values.length; //const { copy, history } = prepare(values); //let time = 1; const copy = values.map(v => v) const RUN = 4; function insertionSort(l, r) { for (let i = l + 1; i < r; i++) { let j = i; while (j > l && copy[j] < copy[j-1]) { swap(j, --j, time++, copy, history); } } } function merge(l, mid, r) { let i = l, j = mid; while (i < j && j < r) { if (copy[i] < copy[j]) { i++; } else { time++; const t = copy[j]; for (let k = j; k > i;k--) { history.get(copy[k-1]).push([time, k]); copy[k] = copy[k-1]; } history.get(t).push([time++, i]); copy[i] = t; i++; j++; } } } for (let i = 0; i < n; i += RUN) { insertionSort(i, i + RUN); } for (let size = RUN; size < n; size *= 2) { for (let i = 0; i < n; i += size * 2) { merge(i, i + size, Math.min(n, i + size * 2)); } } return { copy, history, time }; }41:Tffa,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, history=new Map(), time=1) => { const n = values.length; //const { copy, history } = prepare(values); //let time = 1; const copy = values.map(v => v) 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 { copy, history, time }; } }42:T58d,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); //console.log(data) const polylinePoints = d => d[1].map(([t, y]) => orientation === 'horizontal' ? `${scales.x(t)},${scales.y(y)}` : `${scales.y(y)},${scales.x(t)}` ).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(); }43:[] 3c:{"id":"0653a00db2358def","slug":"shuffling-algorithms/2","title":"Sort and Shuffle Algorithm Animations","thumbnail":"6fffe22f6260b9f144c3bb8723274984b10072e89ec8f1050576d51721849a50","access_level":"public","create_time":"$D2019-11-28T01:00:06.998Z","update_time":"$D2022-04-07T17:48:06.658Z","view_time":null,"first_public_time":"$D2019-11-28T17:21:22.659Z","has_unpublished_edits":null,"fork":{"id":"c810f46e0742d6fe","slug":"shuffling-algorithms","title":"Shuffling Algorithms","owner":{"id":"6c3b7072b5e94b97","login":"jonhelfman","name":"Jonathan Helfman"}},"stars":3,"starred":false,"owner":{"type":"team","id":"6c3b7072b5e94b97","login":"jonhelfman","name":"Jonathan Helfman","avatar_url":"https://avatars-next.observableusercontent.com/a404535763c16060490629d896d876b5b4cea8c603c4993b2aaed749a15b041a","tier":"starter_2024","bio":"Student of math, d3, svg, etc. Prototyper of visualizations for electronics design and test. ","following":false},"version":3651,"publish_version":3651,"role":null,"authored":false,"authors":[{"type":"individual","id":"ba5c813f0f621f19","login":"jonhelfman","name":"Jonathan Helfman","avatar_url":"https://avatars-next.observableusercontent.com/a404535763c16060490629d896d876b5b4cea8c603c4993b2aaed749a15b041a","tier":null,"bio":"Student of math, d3, svg, etc. Prototyper of visualizations for electronics design and test. ","following":false}],"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":9,"collection":{"id":"975bb2d9548b1596","slug":"algorithms","title":"Algorithms","owner":{"id":"6c3b7072b5e94b97","login":"jonhelfman","name":"Jonathan Helfman"}},"type":"notebook","body":{"titling":"auto","title":"Sort and Shuffle Algorithm Animations","cells":[{"id":0,"value":"idTop = md`# Sort and Shuffle Algorithm Animations`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2640,"value":"md`\nForking https://observablehq.com/@jonhelfman/shuffling-algorithms?collection=@jonhelfman/algorithms to add\n- a vertical option, and\n- animation -- the first two charts show algorithms with animation.\n\nIn this notebook time is scaled per chart to help clarify the swaps (so time comparisons across charts are invalid).\n\nClick any chart to re-run.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2914,"value":"viewof orientation = radio({\n title: 'Orientation',\n description: 'Horizontal charts show 16 elements, while vertical charts show 64',\n options: [\n { label: 'Horizontal', value: 'horizontal' },\n { label: 'Vertical', value: 'vertical' },\n ],\n value: 'vertical'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3299,"value":"viewof delay = slider({\n min: 0, \n max: 1500, \n step: 10, \n value: 20,\n description: \"Delay\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3355,"value":"viewof asort = select({\n description: 'Choose a sort algorithm to animate',\n options: Object.keys(sortmap)\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3094,"value":"$3e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3220,"value":"viewof ashuffle = select(\n {\n description: 'Choose a shuffle algorithm to animate',\n options: Object.keys(shufflemap)\n })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3346,"value":"$3f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3254,"value":"md`### Prepare shuffle animation data`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2836,"value":"{\n const { copy, history } = prepare(svalues);\n const res = shufflemap[ashuffle](copy, history)\n const settings = makePlotSettings({shuffle:res})\n mutable aShuffleMaxtime = settings.maxTime\n \n for(let i = 1; i < settings.maxTime; i++) {\n const arr2 = []\n for(let j = 0; j < res.history.size; j++){\n const v = res.history.get(j)\n const arr3 = []\n v.forEach(a => {if(a[0] <= i){\n arr3.push(a)\n }\n })\n arr2.push(arr3)\n }\n const naresult = {copy: copy, history: new Map(arr2.map((v,i) => [i,v]))}\n // update mutables\n mutable aShuffleResult = naresult\n yield Promises.delay(delay)\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3232,"value":"shufflemap = {\n const algmap = {\n naiveShuffle: naiveShuffle,\n fisherYatesShuffle: fisherYatesShuffle,\n riffleShuffle: riffleShuffle,\n riffleShuffle2: riffleShuffle2,\n riffleShuffle3: riffleShuffle3,\n }\n return algmap\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3103,"value":"aShuffleScales = { return {\n values: d3.scaleLinear().domain([d3.min(values), d3.max(values)]).range([0.2, 0.8]),\n x: d3.scaleLinear().domain([0,aShuffleMaxtime]).range([0,width]),\n y: orientation === 'horizontal' ? \n d3.scaleLinear().domain([0,values.length]).range([0,params.height]) :\n d3.scaleLinear().domain([0,values.length]).range([10,params.height - 100]) \n ,\n //color: d3.interpolateRdYlBu\n //color: d3.interpolatePuBuGn\n color: d3.interpolateYlGnBu\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3098,"value":"mutable aShuffleMaxtime = 10","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3100,"value":"mutable aShuffleResult = {}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3504,"value":"md`### Prepare sort animation data`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3349,"value":"{\n const { copy, history } = prepare(values);\n const res = sortmap[asort](copy, history)\n //console.log(res)\n const settings = makePlotSettings({sort:res})\n mutable aSortMaxtime = settings.maxTime\n \n for(let i = 0; i < settings.maxTime; i++) {\n const arr2 = []\n for(let j = 0; j < res.history.size; j++){\n const v = res.history.get(j)\n const arr3 = []\n if(v){ v.forEach(a => {if(a[0] <= i){\n arr3.push(a)\n }\n })\n }\n arr2.push(arr3)\n }\n const naresult = {copy: copy, history: new Map(arr2.map((v,i) => [i,v]))}\n // update mutables\n mutable aSortResult = naresult\n yield Promises.delay(delay)\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3332,"value":"sortmap = {\n const algmap = {\n cyclesort: cyclesort,\n countingSort: countingSort,\n insertionSort: insertionSort,\n quicksort: quicksort,\n mergesort: mergesort,\n shellsort: shellsort,\n heapsort: heapsort,\n radixsort: radixsort,\n bitonicSort: bitonicSort,\n timsort: timsort,\n smoothSort: smoothSort,\n selectionSort: selectionSort,\n oddEvenSort: oddEvenSort,\n cocktailSort: cocktailSort\n }\n return algmap\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3353,"value":"aSortScales = { return {\n values: d3.scaleLinear().domain([d3.min(values), d3.max(values)]).range([0.2, 0.8]),\n x: d3.scaleLinear().domain([0,aSortMaxtime]).range([0,width]),\n y: orientation === 'horizontal' ? \n d3.scaleLinear().domain([0,values.length]).range([0,params.height]) :\n d3.scaleLinear().domain([0,values.length]).range([10,params.height - 100]) \n ,\n //color: d3.interpolateRdYlBu\n //color: d3.interpolatePuBuGn\n color: d3.interpolateYlGnBu\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3351,"value":"mutable aSortMaxtime = 10","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3358,"value":"mutable aSortResult = {}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3412,"value":"md`## Shuffles`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2691,"value":"md`### Naive Shuffle`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2561,"value":"{\n const { copy, history } = prepare(svalues);\n const res = naiveShuffle(copy, history)\n return plot(res, makePlotSettings({shuffle:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2695,"value":"md`### Fisher-Yates Shuffle`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2617,"value":"{\n const { copy, history } = prepare(svalues);\n const res = fisherYatesShuffle(copy, history)\n return plot(res, makePlotSettings({shuffle:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2760,"value":"md `### Riffle Shuffle\n\nFrom https://dev.to/s_awdesh/everyday-im-shuffling-im-a-card--fire-1f8b\n\nClearly wrong.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2725,"value":"{\n const { copy, history } = prepare(svalues);\n const res = riffleShuffle(copy, history)\n return plot(res, makePlotSettings({shuffle:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2754,"value":"md`### Riffle Shuffle2\nCloser to expected`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2729,"value":"{\n const { copy, history } = prepare(svalues);\n const res = riffleShuffle2(copy, history)\n return plot(res, makePlotSettings({shuffle:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2776,"value":"{\n const { copy, history } = prepare(svalues);\n const res = riffleShuffle3(copy, history)\n return plot(res, makePlotSettings({shuffle:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3456,"value":"md`### Shuffle functions`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2552,"value":"naiveShuffle = (values) => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 2;\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 { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2570,"value":"fisherYatesShuffle = (values, history=new Map(), time=2) => {\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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$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=2) => {\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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2727,"value":"riffleShuffle2 = (values, history=new Map(), time=2) => {\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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2768,"value":"riffleShuffle3 = (values, history=new Map(), time=2) => {\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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3415,"value":"md`## Sorts`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1664,"value":"idCyclesort = md`### Cycle Sort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3086,"value":"{\n const { copy, history } = prepare(values);\n const res = cyclesort(copy, history)\n //console.log(res)\n return plot(res, makePlotSettings({sort:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1172,"value":"isCountingsort = md`### Counting Sort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2864,"value":"{\n const { copy, history } = prepare(values);\n const res = countingSort(copy, history)\n return plot(res, makePlotSettings({shuffle:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2998,"value":"idInsertion = md`### Insertion Sort `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2996,"value":"{\n const { copy, history } = prepare(values);\n const res = insertionSort(copy, history)\n return plot(res, makePlotSettings({insertion:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":642,"value":"idQuicksort = md`### Quicksort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":639,"value":"{\n const { copy, history } = prepare(values);\n const res = quicksort(copy, history)\n return plot(res, makePlotSettings({quick:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":718,"value":"idMergesort = md`### Mergesort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":712,"value":"{\n const { copy, history } = prepare(values);\n const res = mergesort(copy, history)\n return plot(res, makePlotSettings({merge:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1113,"value":"idShellsort = md`### Shellsort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1116,"value":"{\n const { copy, history } = prepare(values);\n const res = shellsort(copy, history)\n return plot(res, makePlotSettings({shell:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1152,"value":"idHeapsort = md`### Heapsort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1155,"value":"{\n const { copy, history } = prepare(values);\n const res = heapsort(copy, history)\n return plot(res, makePlotSettings({heap:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1372,"value":"idRadixSort = md`### Radix Sort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1508,"value":"{\n const { copy, history } = prepare(values);\n const res = radixsort(copy, history)\n return plot(res, makePlotSettings({radix:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1670,"value":"idBitonicSort = md`### Bitonic Sort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1725,"value":"{\n const { copy, history } = prepare(values);\n const res = bitonicSort(copy, history)\n return plot(res, makePlotSettings({bitonic:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1651,"value":"idTimsort = md`### Timsort `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1964,"value":"{\n const { copy, history } = prepare(values);\n const res = timsort(copy, history)\n return plot(res, makePlotSettings({timsort:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1837,"value":"idSmoothSort = md`### Smooth Sort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2387,"value":"{\n const { copy, history } = prepare(values);\n const res = smoothSort(copy, history)\n return plot(res, makePlotSettings({smooth:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"idSelection = md`### Selection Sort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"{\n const { copy, history } = prepare(values);\n const res = selectionSort(copy, history)\n return plot(res, makePlotSettings({selection:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2175,"value":"idOddEvenSort = md`### Odd Even Sort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2199,"value":"{\n const { copy, history } = prepare(values);\n const res = oddEvenSort(copy, history)\n return plot(res, makePlotSettings({oddeven:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2179,"value":"idCocktailSort = md`### Cocktail Sort`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2215,"value":"{\n const { copy, history } = prepare(values);\n const res = cocktailSort(copy, history)\n return plot(res, makePlotSettings({cocktail:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3459,"value":"md`### Sort functions`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":271,"value":"insertionSort = (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 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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":492,"value":"quicksort = (values, history=new Map(), time=1) => {\n //const { copy, history } = prepare(values);\n //let time = 1;\n const copy = values.map(v => v)\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 { copy, history, time }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":676,"value":"mergesort = (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 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 { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1096,"value":"shellsort = (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 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 { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1123,"value":"heapsort = (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 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 { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1437,"value":"radixsort = (values, history=new Map(), time=1) => {\n //const { copy, history } = prepare(values);\n //let time = 1;\n const copy = values.map(v => v)\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 { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1723,"value":"bitonicSort = (values, history=new Map(), time=1) => {\n //const { copy, history } = prepare(values);\n //let time = 1;\n const copy = values.map(v => v)\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 { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1960,"value":"$40","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2283,"value":"$41","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"selectionSort = (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 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 { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2193,"value":"oddEvenSort = (values, history=new Map(), time=1) => {\n const n = values.length;\n //const { copy, history } = prepare(values);\n //let time = 1, done = false;\n let done = false;\n const copy = values.map(v => v)\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 { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2209,"value":"cocktailSort = (values, history=new Map(), time=1) => {\n const n = values.length;\n //const { copy, history } = prepare(values);\n let swapped = true, start = 0, end = n;\n const copy = values.map(v => v)\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 { copy, history, time };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2794,"value":"md`## Function to run multiple sorts or shuffles\n\nYou may need to switch to the vertical orientation to appreciate these.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2819,"value":"function braid (alglist, timeGap = 2) {\n let { copy, history } = prepare(svalues);\n let time = 0\n alglist.forEach(a => {\n const rc = a(copy, history, time + timeGap);\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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3069,"value":"md`### braid ([riffleShuffle, riffleShuffle2, countingSort, riffleShuffle3, countingSort])`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2598,"value":"{\n const res = braid ([riffleShuffle, riffleShuffle2, countingSort, riffleShuffle3, countingSort])\n return plot(res, makePlotSettings({braid:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3072,"value":"md`### braid ([ fisherYatesShuffle, riffleShuffle2, riffleShuffle2])`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2715,"value":"{\n const res = braid ([ fisherYatesShuffle, riffleShuffle2, riffleShuffle2])\n return plot(res, makePlotSettings({braid:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3076,"value":"md`### braid ([ riffleShuffle3, countingSort, riffleShuffle3, cyclesort, fisherYatesShuffle])`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2780,"value":"{\n const res = braid ([ riffleShuffle3, countingSort, riffleShuffle3, cyclesort, fisherYatesShuffle])\n return plot(res, makePlotSettings({braid:res}))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2116,"value":"md`### Assignments`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"params = ({\n numValues: orientation === \"horizontal\" ? 16 : 64,\n lineWidth: 8,\n jitter: 0.5,\n height: orientation === \"horizontal\" ? 220 : 1300\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"mutable values = genValues()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2582,"value":"svalues = d3.range(values.length)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2113,"value":"md`### Functions`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":249,"value":"$42","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":145,"value":"makePointsData = ({ history }, maxTime) => {\n function makePoints(entries) {\n const res = [entries[0]];\n //console.log(res)\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// console.log(history.entries())\n return [...history.entries()].map(([k, v]) => [k, makePoints(v)]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2091,"value":"makePlotSettings = results => {\n let 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: orientation === 'horizontal' ? \n d3.scaleLinear().domain([0,values.length]).range([0,params.height]) :\n d3.scaleLinear().domain([0,values.length]).range([10,params.height - 100]) \n ,\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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"md`### Imports`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"d3 = require('d3@5')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2916,"value":"import {radio, select, slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1673,"value":"md`\n\nBitonic\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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1667,"value":"md`\n\nCyclesort\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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1658,"value":"md`\nTimsort\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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1840,"value":"md`\n\nSmoothsort: a port of [bowd/smoothsort](https://github.com/bowd/smoothsort), originally written in Rust.\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","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W43","stdlib":"1"}} 3d:"$3c:body"