30:[] 2e:{"title":"d3.quickselect","cells":[{"id":0,"value":"# d3.quickselect\n\n[d3.quickselect](https://d3js.org/d3-array/sort#quickselect) partially reorders an array in the quickest way possible. Orders of magnitude faster that the native [*array*.sort](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort), it shines when used to extract a median, or quantiles, on large arrays (like for example image pixel data).","pinned":false,"hidden":false,"mode":"md"},{"id":12,"value":"But first, let’s see what it does on a small scale example. The function’s signature is the following: \n\nd3.quickselect(*array*, *k*[, *left*[, *right*[, *compare*]]])\n\nLet’s populate an array with 10 values, and quickselect the 3 smallest values (using *k*=2, as the pivot is inclusive):","pinned":false,"hidden":false,"mode":"md"},{"id":14,"value":"numbers = [16, 15, 18, 10, 17, 14, 13, 19, 11, 12]","pinned":true,"hidden":false,"mode":"ojs"},{"id":16,"value":"d3.quickselect(numbers.slice(), 2)","pinned":true,"hidden":false,"mode":"ojs"},{"id":39,"value":"*k* is called the middle index, or pivot index. The first elements of the array, on the left of *k*, are now 10, 11 and 12, the three smallest values. They are not arranged in any specific order: what matters is that any element on the left of the pivot is now smaller or equal to any element on its right.\n\nInternally, d3-array uses this technique to quickly compute the [median](https://d3js.org/d3-array/summarize#median) (and any other quantile) of an array.\n\nNote that, to be memory-efficient, quickselect changes the array in-place — we use *array*.slice in the examples to ensure the original arrays aren’t modified, so you can play with the code.","pinned":false,"hidden":false,"mode":"md"},{"id":103,"value":"d3.quickselect will work on an array of strings:","pinned":false,"hidden":false,"mode":"md"},{"id":93,"value":"d3.quickselect([...\"how to select an array of strings\"], 10)","pinned":true,"hidden":false,"mode":"ojs"},{"id":147,"value":"After *k*, the next arguments to d3.quickselect are *left* and *right*, defining the interval in which the selection will be applied. The algorithm runs strictly between those two indices, and all the other elements are left untouched. Of course *k* must lie between *left* and *right*:","pinned":false,"hidden":false,"mode":"md"},{"id":340,"value":"left = 4","pinned":true,"hidden":false,"mode":"ojs"},{"id":347,"value":"k = 6 // must be between >= left and <= right","pinned":true,"hidden":false,"mode":"ojs"},{"id":344,"value":"right = 8 // inclusive!","pinned":true,"hidden":false,"mode":"ojs"},{"id":374,"value":"input = [0, 4, 1, 6, 7, 5, 8, 2, 9, 3]","pinned":true,"hidden":false,"mode":"ojs"},{"id":351,"value":"result = d3.quickselect(input.slice(), k, left, right)","pinned":true,"hidden":false,"mode":"ojs"},{"id":405,"value":"Visually the reordering looks like this; the blue area is the part of the array that is reordered, the red area contains the top values post reordering, anything gray will not be affected:","pinned":false,"hidden":false,"mode":"md"},{"id":382,"value":"{\n const step = 20;\n const indexa = new Map(input.map((d, i) => [d, i]));\n const indexb = new Map(result.map((d, i) => [d, i]));\n return svg``;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":368,"value":"*result* is now partially ordered in the range *result*[*left*] … *result*[*k*], so we can pull out the smallest elements of the *input*[*left*] … *input*[*right*] range:","pinned":false,"hidden":false,"mode":"md"},{"id":357,"value":"result.slice(left, k + 1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":136,"value":"d3.quickselect can also use a [comparator](https://observablehq.com/@d3/d3-ascending). But before we indicate the comparator, *left* and *right* must be specified. In the following example, we want to select the whole interval, with *left*=0 being the first index of the array, and *right*=3 being the last (*i.e.* length-1).","pinned":false,"hidden":false,"mode":"md"},{"id":108,"value":"d3.quickselect(\n [\n { item: \"Soup\", note: 4, emoji: \"🍜\" },\n { item: \"Cabbage\", note: 1, emoji: \"🥬\" },\n { item: \"Cake\", note: 5, emoji: \"🍰\" },\n { item: \"Ice Cream\", note: 3, emoji: \"🍦\" }\n ],\n 2, // k\n 0, // left\n 3, // right\n (a, b) => a.note - b.note // comparator\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":7,"value":"---\n\n## Appendix\n\nThanks to [Michael Pishchagin](https://observablehq.com/@mblsha) and [Julian Burgess](https://observablehq.com/@aubergene) for proofreading and suggestions.","pinned":false,"hidden":false,"mode":"md"},{"id":8,"value":"d3 = require(\"d3-array@3\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W30","stdlib":"1","titling":"auto"}