30:T445,shellSort = { let input = makeInput(); yield* pauser(display(input, { immediate: true })); let gaps = [1]; for (let i = 0; i < Math.floor(Math.sqrt(input.length)); i++) { gaps.push(Math.pow(i, 2) + 1); } gaps.reverse(); for (let gap of gaps) { // Do a gapped insertion sort for this gap size. // The first gap elements a[0..gap-1] are already in gapped order // keep adding one more element until the entire array is gap sorted for (let i = gap; i < input.length; i += 1) { // add a[i] to the elements that have been gap sorted // save a[i] in temp and make a hole at position i let temp = input[i]; let j; // shift earlier gap-sorted elements up until the correct location for a[i] is found for (j = i; j >= gap && input[j - gap] > temp; j -= gap) { input[j] = input[j - gap] yield display(input, {pos: i, highlight:new Set([j, j-gap])}); } // put temp (the original a[i]) in its correct location input[j] = temp } } yield display(input, {done: true}); }31:T468,heapSort = { let input = makeInput(); yield* pauser(display(input, { immediate: true })); function swap(data, i, j) { var tmp = data[i]; data[i] = data[j]; data[j] = tmp; } function* heapSort(arr) { yield* putArrayInHeapOrder(arr); for (let end = arr.length - 1; end > 0; end--) { yield display(input, {pos: end, highlight:new Set([end])}); swap(arr, 0, end); yield* siftElementDownHeap(arr, 0, end); } } function* putArrayInHeapOrder(arr) { for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) { yield* siftElementDownHeap(arr, i, arr.length); } } function* siftElementDownHeap(heap, i, max) { while (i < max) { let i_big = i; let c1 = 2 * i + 1; let c2 = c1 + 1; if (c1 < max && heap[c1] > heap[i_big]) i_big = c1; if (c2 < max && heap[c2] > heap[i_big]) i_big = c2; if (i_big == i) return; yield display(input, {pos: i, highlight:new Set([i])}); swap(heap, i, i_big); i = i_big; } } yield* heapSort(input); yield display(input, {done: true}); }32:T422,function display(inputs, {pos, done, highlight,immediate} = {}) { if (!highlight) highlight = new Set([]); let svg = d3.select(DOM.svg(width, height)); let margin = { bottom: 20, top: 10, left: 10, right: 10 }; let y = d3.scaleLinear() .domain([1, n]).nice() .range([height - margin.bottom, margin.top]); let x = d3.scaleLinear() .domain([1, n]).nice() .range([margin.left, width - margin.right]); svg.selectAll('bar') .data(inputs) .enter() .append('rect') .attr('fill', (d, i) => { if (done) return 'darkblue'; return highlight.has(i) ? 'orange' : '#999'; }) .attr("x", (d, i) => x(i) + 1) .attr("width", d => x(2) - x(1) - 1) .attr("y", d => y(d)) .attr("height", d => y(0) - y(d)); if (pos !== undefined) { svg.append('g') .attr('transform', `translate(${x(pos + 0.5)}, ${height - margin.bottom + 20})`) .append('text') .attr("text-anchor", "middle") .text(pos); } return immediate ? svg.node() : Promises.delay(100, svg.node()); }33:[] 2e:{"title":"Sorting","cells":[{"id":0,"value":"md`# Sorting\n\nCheck out [the overview](https://beta.observablehq.com/@tmcw/sorting-overview) for all of these without the expanded code!`","pinned":false,"hidden":false,"mode":"ojs"},{"id":3,"value":"md`## [Gnome sort](https://en.wikipedia.org/wiki/Gnome_sort)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"gnomeSort = {\n let input = makeInput();\n let pos = 0;\n yield* pauser(display(input, {pos, immediate: true}));\n while (pos < input.length) {\n if (pos == 0 || input[pos] >= input[pos - 1]) {\n pos = pos + 1;\n } else {\n let a = input[pos];\n let b = input[pos - 1];\n input[pos] = b;\n input[pos - 1] = a;\n pos = pos - 1;\n yield display(input, {pos, highlight:new Set([pos, pos-1])});\n }\n }\n yield display(input, {done: true});\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":79,"value":"md`## [Bubble sort](https://en.wikipedia.org/wiki/Bubble_sort)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":82,"value":"bubbleSort = {\n let input = makeInput();\n yield* pauser(display(input, { immediate: true }));\n for (let i = 0; i < input.length; i++) {\n for (let j = 1; j < input.length; j++) {\n if (input[j - 1] > input[j]) {\n let a = input[j];\n let b = input[j - 1];\n input[j] = b;\n input[j - 1] = a;\n yield display(input, {pos: i, highlight:new Set([j, j-1])});\n }\n }\n }\n yield display(input, {done: true});\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":103,"value":"md`## [Shell sort](https://en.wikipedia.org/wiki/Shellsort)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":101,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":145,"value":"md`## [Cocktail shaker sort](https://en.wikipedia.org/wiki/Cocktail_shaker_sort)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":138,"value":"cocktailSort = {\n let input = makeInput();\n yield* pauser( display(input, { immediate: true }));\n let swapped = false;\n do {\n swapped = false;\n let i;\n for (i = 0; i < input.length - 1; i++) {\n if (input[i] > input[i + 1]) {\n let a = input[i];\n let b = input[i + 1];\n input[i] = b;\n input[i + 1] = a;\n swapped = true;\n yield display(input, {pos: i, highlight:new Set([i, i+1])});\n }\n }\n if (!swapped) {\n break;\n }\n swapped = false;\n for (i = input.length - 1; i > 0; i--) {\n if (input[i] > input[i + 1]) {\n let a = input[i];\n let b = input[i + 1];\n input[i] = b;\n input[i + 1] = a;\n swapped = true;\n yield display(input, {pos: i, highlight:new Set([i, i+1])});\n }\n }\n } while (swapped);\n yield display(input, {done: true});\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":148,"value":"md`## [Selection sort](https://en.wikipedia.org/wiki/Selection_sort)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":151,"value":"selectionSort = {\n let input = makeInput();\n yield* pauser(display(input, { immediate: true }));\n for (let j = 0; j < input.length; j++) {\n let min = j;\n for (let i = j + 1; i < input.length; i++) {\n if (input[i] < input[min]) {\n min = i;\n }\n }\n if (min !== j) {\n let a = input[j];\n let b = input[min];\n input[j] = b;\n input[min] = a;\n yield display(input, {pos: j, highlight:new Set([min, j])});\n }\n }\n yield display(input, {done: true});\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":184,"value":"md`# [Quicksort](https://en.wikipedia.org/wiki/Quicksort)\n\nQuicksort is a good example of the \\`yield*\\` operator. It's a recursive sorting algorithm that uses an internal function to do its work - but we're still able to yield intermediate values to visualize the algorithm thanks to \\`yield*\\`, which allows the outer generator (quickSort) to yield values yielded by the inner generator (quicksort).\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":161,"value":"quickSort = {\n let input = makeInput();\n yield* pauser(display(input, { immediate: true }));\n \n function* quicksort(left, right) {\n if (left < right) {\n let pivot = input[left + Math.floor((right - left) / 2)],\n leftNew = left,\n rightNew = right;\n \n do {\n while (input[leftNew] < pivot) {\n leftNew++;\n }\n while (pivot < input[rightNew]) {\n rightNew--;\n }\n if (leftNew <= rightNew) {\n let temp = input[leftNew];\n input[leftNew] = input[rightNew];\n input[rightNew] = temp;\n leftNew++;\n rightNew--;\n }\n yield display(input, {pos: pivot, highlight:new Set([leftNew, pivot, rightNew])});\n } while (leftNew <= rightNew);\n yield* quicksort(left, rightNew);\n yield* quicksort(leftNew, right);\n }\n }\n \n yield* quicksort(0, input.length - 1);\n \n yield display(input, {done: true});\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":210,"value":"md`# [Heapsort](https://en.wikipedia.org/wiki/Heapsort)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":160,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":254,"value":"md`Wondering how all of these charts only start sorting when you scroll to them? Check out the [pauser notebook](https://beta.observablehq.com/@tmcw/pauser) for the details.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":216,"value":"import {pauser} from \"@tmcw/pauser\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":22,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":121,"value":"n = 20","pinned":false,"hidden":false,"mode":"ojs"},{"id":130,"value":"height = 200","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"function makeInput() {\n let input = [];\n for (let i = 1; i <= n; i++) {\n input.push(i);\n }\n input.sort(() => Math.random() - 0.5);\n return input;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"d3 = require('d3')","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}