2a: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(); }2b: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(); }2c: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 }; }2d: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 }; } }2e: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(); }2f:[] 29:{"title":"Sort and Shuffle Algorithm Animations","cells":[{"id":0,"value":"idTop = md`# Sort and Shuffle Algorithm Animations`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"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"},{"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"},{"id":3094,"value":"$2a","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":3346,"value":"$2b","pinned":false,"hidden":false,"mode":"ojs"},{"id":3254,"value":"md`### Prepare shuffle animation data`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"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"},{"id":3098,"value":"mutable aShuffleMaxtime = 10","pinned":false,"hidden":false,"mode":"ojs"},{"id":3100,"value":"mutable aShuffleResult = {}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3504,"value":"md`### Prepare sort animation data`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"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"},{"id":3351,"value":"mutable aSortMaxtime = 10","pinned":false,"hidden":false,"mode":"ojs"},{"id":3358,"value":"mutable aSortResult = {}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3412,"value":"md`## Shuffles`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2691,"value":"md`### Naive Shuffle`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":2695,"value":"md`### Fisher-Yates Shuffle`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"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"},{"id":2754,"value":"md`### Riffle Shuffle2\nCloser to expected`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":2778,"value":"md`### Riffle Shuffle3\n\nAdd some randomness`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":3456,"value":"md`### Shuffle functions`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"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"},{"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"},{"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"},{"id":3415,"value":"md`## Sorts`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1664,"value":"idCyclesort = md`### Cycle Sort`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":1172,"value":"isCountingsort = md`### Counting Sort`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":2998,"value":"idInsertion = md`### Insertion Sort `","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":642,"value":"idQuicksort = md`### Quicksort`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":718,"value":"idMergesort = md`### Mergesort`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":1113,"value":"idShellsort = md`### Shellsort`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":1152,"value":"idHeapsort = md`### Heapsort`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":1372,"value":"idRadixSort = md`### Radix Sort`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":1670,"value":"idBitonicSort = md`### Bitonic Sort`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":1651,"value":"idTimsort = md`### Timsort `","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":1837,"value":"idSmoothSort = md`### Smooth Sort`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":100,"value":"idSelection = md`### Selection Sort`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":2175,"value":"idOddEvenSort = md`### Odd Even Sort`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":2179,"value":"idCocktailSort = md`### Cocktail Sort`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":3459,"value":"md`### Sort functions`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"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"},{"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"},{"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"},{"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"},{"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"},{"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"},{"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"},{"id":1960,"value":"$2c","pinned":false,"hidden":false,"mode":"ojs"},{"id":2283,"value":"$2d","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"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"},{"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"},{"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"},{"id":3069,"value":"md`### braid ([riffleShuffle, riffleShuffle2, countingSort, riffleShuffle3, countingSort])`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":3072,"value":"md`### braid ([ fisherYatesShuffle, riffleShuffle2, riffleShuffle2])`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2715,"value":"{\n const res = braid ([ fisherYatesShuffle, riffleShuffle2, riffleShuffle2])\n return plot(res, makePlotSettings({braid:res}))\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3076,"value":"md`### braid ([ riffleShuffle3, countingSort, riffleShuffle3, cyclesort, fisherYatesShuffle])`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":2116,"value":"md`### Assignments`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":19,"value":"mutable values = genValues()","pinned":false,"hidden":false,"mode":"ojs"},{"id":2582,"value":"svalues = d3.range(values.length)","pinned":false,"hidden":false,"mode":"ojs"},{"id":2113,"value":"md`### Functions`","pinned":false,"hidden":false,"mode":"ojs"},{"id":249,"value":"$2e","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"id":2035,"value":"genValues = () => d3.shuffle(d3.range(params.numValues))","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"id":7,"value":"md`### Imports`","pinned":false,"hidden":false,"mode":"ojs"},{"id":10,"value":"d3 = require('d3@5')","pinned":false,"hidden":false,"mode":"ojs"},{"id":2916,"value":"import {radio, select, slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"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"},{"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"},{"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"}],"files":"$W2f","stdlib":"1","titling":"auto"}