3f:null 40:["$","title",null,{"children":"Sorts | whiteand | Observable"}] 46:T41a,function* heapsort(arr, comparator) { function swap(i, j) { const t = arr[i]; arr[i] = arr[j]; arr[j] = t; } // heapify for (let i = 0; i < arr.length; i++) { let cur = i; while (cur >= 0) { const parent = (cur / 2) | 0; if (comparator(arr[parent], arr[cur]) >= 0) break; swap(cur, parent); cur = parent; } if (i % 10 === 0) yield arr; } yield arr; // sort for (let i = 1; i < arr.length; i++) { swap(0, arr.length - i); let cur = 0; while (cur < arr.length - i) { const leftChild = cur * 2; const rightChild = cur * 2 + 1; let maxInd = cur; if ( leftChild < arr.length - 1 - i && comparator(arr[maxInd], arr[leftChild]) < 0 ) { maxInd = leftChild; } if ( rightChild < arr.length - i - 1 && comparator(arr[maxInd], arr[rightChild]) < 0 ) { maxInd = rightChild; } if (cur === maxInd) break; swap(cur, maxInd); cur = maxInd; } yield arr; } }47:T518,function* mergeSort(arr, comparator) { const SORT = 0; const MERGE = 1; const tasks = [arr.length, 0, SORT]; function swap(i, j) { const t = arr[i]; arr[i] = arr[j]; arr[j] = t; } while (tasks.length > 0) { const command = tasks.pop(); if (command === SORT) { const start = tasks.pop(); const end = tasks.pop(); if (start >= end - 1) continue; if (start === end - 2) { if (comparator(arr[start], arr[end - 1]) > 0) { swap(start, end - 1); yield arr; } continue; } const mid = Math.floor((start + end) / 2); tasks.push(end, mid, start, MERGE, end, mid, SORT, mid, start, SORT); } else if (command === MERGE) { const start = tasks.pop(); const mid = tasks.pop(); const end = tasks.pop(); const res = []; let left = start; let right = mid; while (left < mid && right < end) { if (comparator(arr[left], arr[right]) <= 0) { res.push(arr[left++]); } else { res.push(arr[right++]); } } while (left < mid) res.push(arr[left++]); while (right < end) res.push(arr[right++]); for (let i = start; i < end; i++) { arr[i] = res[i - start]; yield arr; } } } }48:T5d5,function* quickSort(arr, comparator) { const db = {}; function compare(first, second) { if (db[first] && db[first][second]) { return db[first][second]; } if (db[second] && db[second][first]) { return 1 - db[second][first]; } const c = comparator(first, second); if (!db[first]) { db[first] = {}; } db[first][second] = c; return c; } const intervals = [[0, arr.length]]; let isPop = true; while (intervals.length > 0) { const [start, end] = intervals.pop(); if (start >= end) continue; if (start + 1 === end) { if (compare(arr[start], arr[end]) > 0) { const t = arr[start]; arr[start] = arr[end]; arr[end] = t; } continue; } let left = start; let right = end - 1; let isLeftMoving = compare(arr[left], arr[right]) <= 0; while (left < right) { if (isLeftMoving) { while (compare(arr[left], arr[right]) <= 0 && right > left) left++; if (left >= right) continue; const t = arr[left]; arr[left] = arr[right]; arr[right] = t; yield arr; } else { while (compare(arr[left], arr[right]) <= 0 && right > left) right--; if (left >= right) continue; const t = arr[left]; arr[left] = arr[right]; arr[right] = t; yield arr; } isLeftMoving = !isLeftMoving; } intervals.push([left, end], [start, right]); yield arr; } return arr; }49:[] 44:{"id":"623626cbdf9ecf39","slug":"sorts","title":"Sorts","thumbnail":"92d8f48e8777808a2406ef598e1a8cb0d4ef2d81cdd99c9fdcd8262c7f073c67","access_level":"public","create_time":"$D2021-04-04T17:56:58.963Z","update_time":"$D2021-04-06T07:51:46.616Z","view_time":null,"first_public_time":"$D2021-04-05T19:30:24.909Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"8a07b1959b7e4d01","login":"whiteand","name":"whiteand","avatar_url":"https://avatars-next.observableusercontent.com/321abde3bcff6c4d510747c6a6e68f506f908e09fc1f2de934738b8aa349e52b","tier":"starter_2024","bio":"Frontend developer","following":false},"version":399,"publish_version":399,"role":null,"authored":false,"authors":[{"type":"individual","id":"55a52a343b60a53d","login":"whiteand","name":"whiteand","avatar_url":"https://avatars-next.observableusercontent.com/321abde3bcff6c4d510747c6a6e68f506f908e09fc1f2de934738b8aa349e52b","tier":null,"bio":"Frontend developer","following":false}],"members":[{"type":"individual","id":"55a52a343b60a53d","login":"whiteand","name":"whiteand","avatar_url":"https://avatars-next.observableusercontent.com/321abde3bcff6c4d510747c6a6e68f506f908e09fc1f2de934738b8aa349e52b","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Sorts","cells":[{"id":0,"value":"md`# Sorts`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"data = Array.from({ length: width >>> 6 }, () => Math.random() * height)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":80,"value":"width = 960","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"height = 240","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":395,"value":"md`## Choose your one of next sorts:\n\n- heapsort\n- quicksort\n- radixSort\n- shell\n- mergeSort`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":229,"value":"customSort = heapsort // heapsort, or quicksort, radixSort, shell, mergeSort","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":343,"value":"size = width | 0","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":351,"value":"MAX_VALUE = 1000000","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"{\n const svg = d3\n .create('svg')\n .attr('width', width)\n .attr('height', height)\n\n .attr('style', 'background: #eaeaea');\n\n const arr = Array.from(\n { length: size },\n () => (Math.random() * MAX_VALUE) | 0\n );\n\n const selected = svg.selectAll('rect');\n\n const tasks = [];\n const answers = {};\n customSort([...arr], (first, second) => {\n if (tasks.length > 0) return 0;\n tasks.push([first, second]);\n return 0;\n });\n\n for (let step of customSort(arr, (a, b) => Math.sign(a - b))) {\n svg\n .selectAll('rect')\n .data(step, (d, i) => i)\n .join(enter => enter.append('rect'))\n .attr('x', (d, i, a) => (i * width) / a.length)\n .attr('y', d => height - (d / MAX_VALUE) * height)\n .attr('style', 'transition: x 0.1s; will-change: x')\n .attr('width', (d, i, a) => width / a.length)\n .attr('height', d => d)\n .attr('fill', 'blue');\n\n yield svg.node();\n }\n\n return svg.node();\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":367,"value":"$46","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":281,"value":"function* radixSort(arr) {\n let maxNum = Math.max(...arr);\n const parts = Array.from({ length: 10 }, () => []);\n let step = 1;\n while (step <= maxNum) {\n for (const x of arr) {\n const digit = Math.floor(x / step) % 10;\n parts[digit].push(x);\n }\n let target = 0;\n for (let i = 0; i < 10; i++) {\n for (let j = 0; j < parts[i].length; j++) {\n arr[target++] = parts[i][j];\n yield arr;\n }\n parts[i].length = 0;\n }\n step *= 10;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":231,"value":"$47","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":298,"value":"function* shell(arr, comparator) {\n const steps = [1, 4, 9, 20, 46, 103, 233, 525];\n steps.reverse();\n let swaps = 0;\n function swap(i, j) {\n const t = arr[i];\n arr[i] = arr[j];\n arr[j] = t;\n swaps++;\n }\n let i = 0;\n while (true) {\n swaps = 0;\n const step = steps[i++] || 1;\n for (let j = 0; j < arr.length - step; j++) {\n if (comparator(arr[j], arr[j + step]) > 0) {\n swap(j, j + step);\n yield arr;\n }\n }\n\n if (!swaps && step === 1) break;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":146,"value":"$48","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"md`## Apendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"d3 = require('d3')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W49","stdlib":"1"}} 45:"$44:body"