{"history":[],"article":{"id":"33f80fc2-e60c-4710-9fe1-429ba2c0a72a","title":"Quickselect","slug":"quickselect","content":":::summary\n**Name:** Quickselect \n**Class:** [Selection algorithm](https://bliptext.com/articles/selection-algorithm) \n**Data:** [Array](https://bliptext.com/articles/array-data-structure) \n**Best -time:** O(n) \n**Average -time:** O(n) \n**Time:** O(n2) \n**Space:** O(1) \n:::\n\n# \nIn [computer science](https://bliptext.com/articles/computer-science), **quickselect** is a [selection algorithm](https://bliptext.com/articles/selection-algorithm) to find the kth smallest element in an unordered list, also known as the kth [order statistic](https://bliptext.com/articles/order-statistics).\nLike the related [quicksort](https://bliptext.com/articles/quicksort) sorting algorithm, it was developed by [Tony Hoare](https://bliptext.com/articles/tony-hoare), and thus is also known as **Hoare's selection algorithm**.\nLike quicksort, it is efficient in practice and has good average-case performance, but has poor worst-case performance.\nQuickselect and its variants are the selection algorithms most often used in efficient real-world implementations.\nQuickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot.\nHowever, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side – the side with the element it is searching for.\nThis reduces the average complexity from O(n\\log n) to O(n), with a worst case of O(n^2).\nAs with quicksort, quickselect is generally implemented as an [in-place algorithm](https://bliptext.com/articles/in-place-algorithm), and beyond selecting the kth element, it also partially sorts the data.\nSee [selection algorithm](https://bliptext.com/articles/selection-algorithm) for further discussion of the connection with sorting.\n\n# Algorithm\nIn quicksort, there is a subprocedure called that can, in linear time, group a list (ranging from indices to ) into two parts: those less than a certain element, and those greater than or equal to the element.\nHere is pseudocode that performs a partition about the element :\n**function** partition(l**is**t, left, right, pivotIndex) **is**\npivotValue := list[pivotIndex]\nswap list[pivotIndex] and list[right] // Move pivot to end\nstoreIndex := left\n**for** i **from** left **to** right − 1 **do**\n**if** list[i] < pivotValue **then**\nswap list[storeIndex] and list[i]\nincrement storeIndex\nswap list[right] and list[storeIndex] // Move pivot to its final place\n**return** storeIndex\nThis is known as the [Lomuto partition scheme](https://bliptext.com/articles/quicksort), which is simpler but less efficient than [Hoare's original partition scheme](https://bliptext.com/articles/quicksort).\nIn quicksort, we recursively sort both branches, leading to best-case O(n\\log n) time.\nHowever, when doing selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in an unsorted order and all those following it in an unsorted order.\nTherefore, a single recursive call locates the desired element in the correct partition, and we build upon this for quickselect:\n// Returns the k-th smallest element of list within left..right inclusive\n// (i.e. left <= k <= right).\n**function** select(l**is**t, left, right, k) **is**\n**if** left = right **then** // If the list contains only one element,\n**return** list[left] // **return** that element\npivotIndex := ...\n// select a pivotIndex between left and right,\n// e.g., left + floor(rand % (right − left + 1))\npivotIndex := partition(list, left, right, pivotIndex)\n// The pivot is in its final sorted position\n**if** k = pivotIndex **then**\n**return** list[k]\n**else if** k < pivotIndex **then**\n**return** select(list, left, pivotIndex − 1, k) **else**\n**return** select(list, pivotIndex + 1, right, k)\nNote the resemblance to quicksort: just as the minimum-based selection algorithm is a partial selection sort, this is a partial quicksort, generating and partitioning only O(\\log n) of its O(n) partitions.\nThis simple procedure has expected linear performance, and, like quicksort, has quite good performance in practice.\nIt is also an [in-place algorithm](https://bliptext.com/articles/in-place-algorithm), requiring only constant memory overhead if [tail call](https://bliptext.com/articles/tail-call) optimization is available, or if eliminating the [tail recursion](https://bliptext.com/articles/tail-recursion) with a loop:\n**function** select(l**is**t, left, right, k) **is**\n**loop**\n**if** left = right **then**\n**return** list[left]\npivotIndex := ...\n// select pivotIndex between left and right\npivotIndex := partition(list, left, right, pivotIndex)\n**if** k = pivotIndex **then**\n**return** list[k]\n**else if** k < pivotIndex **then**\nright := pivotIndex − 1\n**else**\nleft := pivotIndex + 1\n\n# Time complexity\nLike quicksort, quickselect has good average performance, but is sensitive to the pivot that is chosen.\nIf good pivots are chosen, meaning ones that consistently decrease the search set by a given fraction, then the search set decreases in size exponentially and by induction (or summing the [geometric series](https://bliptext.com/articles/geometric-series)) one sees that performance is linear, as each step is linear and the overall time is a constant times this (depending on how quickly the search set reduces).\nHowever, if bad pivots are consistently chosen, such as decreasing by only a single element each time, then worst-case performance is quadratic: O(n^2).\nThis occurs for example in searching for the maximum element of a set, using the first element as the pivot, and having sorted data.\nHowever, for randomly chosen pivots, this worst case is very unlikely: the probability of using more than Cn comparisons, for any sufficiently large constant C, is superexponentially small as a function of C.\n\n# Variants\nThe easiest solution is to choose a random pivot, which yields [almost certain](https://bliptext.com/articles/almost-certain) linear time.\nDeterministically, one can use median-of-3 pivot strategy (as in the quicksort), which yields linear performance on partially sorted data, as is common in the real world.\nHowever, contrived sequences can still cause worst-case complexity; [David Musser](https://bliptext.com/articles/david-musser) describes a \"median-of-3 killer\" sequence that allows an attack against that strategy, which was one motivation for his [introselect](https://bliptext.com/articles/introselect) algorithm.\nOne can assure linear performance even in the worst case by using a more sophisticated pivot strategy; this is done in the [median of medians](https://bliptext.com/articles/median-of-medians) algorithm.\nHowever, the overhead of computing the pivot is high, and thus this is generally not used in practice.\nOne can combine basic quickselect with median of medians as fallback to get both fast average case performance and linear worst-case performance; this is done in [introselect](https://bliptext.com/articles/introselect).\nFiner computations of the average time complexity yield a worst case of for random pivots (in the case of the median; other k are faster).\nThe constant can be improved to 3/2 by a more complicated pivot strategy, yielding the [Floyd–Rivest algorithm](https://bliptext.com/articles/floyd-rivest-algorithm), which has average complexity of for median, with other k being faster.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T22:35:04.317Z","updated_at":"2025-01-25T22:35:04.317Z","search_vector":"'quickselect':1","search_content":" \n**Name:** Quickselect \n**Class:** [Selection algorithm](https://bliptext.com/articles/selection-algorithm) \n**Data:** [Array](https://bliptext.com/articles/array-data-structure) \n**Best -time:** O(n) \n**Average -time:** O(n) \n**Time:** O(n2) \n**Space:** O(1) \n \n\n# \nIn [computer science](https://bliptext.com/articles/computer-science), **quickselect** is a [selection algorithm](https://bliptext.com/articles/selection-algorithm) to find the kth smallest element in an unordered list, also known as the kth [order statistic](https://bliptext.com/articles/order-statistics).\nLike the related [quicksort](https://bliptext.com/articles/quicksort) sorting algorithm, it was developed by [Tony Hoare](https://bliptext.com/articles/tony-hoare), and thus is also known as **Hoare's selection algorithm**.\nLike quicksort, it is efficient in practice and has good average-case performance, but has poor worst-case performance.\nQuickselect and its variants are the selection algorithms most often used in efficient real-world implementations.\nQuickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot.\nHowever, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side – the side with the element it is searching for.\nThis reduces the average complexity from O(n\\log n) to O(n), with a worst case of O(n^2).\nAs with quicksort, quickselect is generally implemented as an [in-place algorithm](https://bliptext.com/articles/in-place-algorithm), and beyond selecting the kth element, it also partially sorts the data.\nSee [selection algorithm](https://bliptext.com/articles/selection-algorithm) for further discussion of the connection with sorting.\n\n# Algorithm\nIn quicksort, there is a subprocedure called that can, in linear time, group a list (ranging from indices to ) into two parts: those less than a certain element, and those greater than or equal to the element.\nHere is pseudocode that performs a partition about the element :\n**function** partition(l**is**t, left, right, pivotIndex) **is**\npivotValue := list[pivotIndex]\nswap list[pivotIndex] and list[right] // Move pivot to end\nstoreIndex := left\n**for** i **from** left **to** right − 1 **do**\n**if** list[i] < pivotValue **then**\nswap list[storeIndex] and list[i]\nincrement storeIndex\nswap list[right] and list[storeIndex] // Move pivot to its final place\n**return** storeIndex\nThis is known as the [Lomuto partition scheme](https://bliptext.com/articles/quicksort), which is simpler but less efficient than [Hoare's original partition scheme](https://bliptext.com/articles/quicksort).\nIn quicksort, we recursively sort both branches, leading to best-case O(n\\log n) time.\nHowever, when doing selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in an unsorted order and all those following it in an unsorted order.\nTherefore, a single recursive call locates the desired element in the correct partition, and we build upon this for quickselect:\n// Returns the k-th smallest element of list within left..right inclusive\n// (i.e. left <= k <= right).\n**function** select(l**is**t, left, right, k) **is**\n**if** left = right **then** // If the list contains only one element,\n**return** list[left] // **return** that element\npivotIndex := ...\n// select a pivotIndex between left and right,\n// e.g., left + floor(rand % (right − left + 1))\npivotIndex := partition(list, left, right, pivotIndex)\n// The pivot is in its final sorted position\n**if** k = pivotIndex **then**\n**return** list[k]\n**else if** k < pivotIndex **then**\n**return** select(list, left, pivotIndex − 1, k) **else**\n**return** select(list, pivotIndex + 1, right, k)\nNote the resemblance to quicksort: just as the minimum-based selection algorithm is a partial selection sort, this is a partial quicksort, generating and partitioning only O(\\log n) of its O(n) partitions.\nThis simple procedure has expected linear performance, and, like quicksort, has quite good performance in practice.\nIt is also an [in-place algorithm](https://bliptext.com/articles/in-place-algorithm), requiring only constant memory overhead if [tail call](https://bliptext.com/articles/tail-call) optimization is available, or if eliminating the [tail recursion](https://bliptext.com/articles/tail-recursion) with a loop:\n**function** select(l**is**t, left, right, k) **is**\n**loop**\n**if** left = right **then**\n**return** list[left]\npivotIndex := ...\n// select pivotIndex between left and right\npivotIndex := partition(list, left, right, pivotIndex)\n**if** k = pivotIndex **then**\n**return** list[k]\n**else if** k < pivotIndex **then**\nright := pivotIndex − 1\n**else**\nleft := pivotIndex + 1\n\n# Time complexity\nLike quicksort, quickselect has good average performance, but is sensitive to the pivot that is chosen.\nIf good pivots are chosen, meaning ones that consistently decrease the search set by a given fraction, then the search set decreases in size exponentially and by induction (or summing the [geometric series](https://bliptext.com/articles/geometric-series)) one sees that performance is linear, as each step is linear and the overall time is a constant times this (depending on how quickly the search set reduces).\nHowever, if bad pivots are consistently chosen, such as decreasing by only a single element each time, then worst-case performance is quadratic: O(n^2).\nThis occurs for example in searching for the maximum element of a set, using the first element as the pivot, and having sorted data.\nHowever, for randomly chosen pivots, this worst case is very unlikely: the probability of using more than Cn comparisons, for any sufficiently large constant C, is superexponentially small as a function of C.\n\n# Variants\nThe easiest solution is to choose a random pivot, which yields [almost certain](https://bliptext.com/articles/almost-certain) linear time.\nDeterministically, one can use median-of-3 pivot strategy (as in the quicksort), which yields linear performance on partially sorted data, as is common in the real world.\nHowever, contrived sequences can still cause worst-case complexity; [David Musser](https://bliptext.com/articles/david-musser) describes a \"median-of-3 killer\" sequence that allows an attack against that strategy, which was one motivation for his [introselect](https://bliptext.com/articles/introselect) algorithm.\nOne can assure linear performance even in the worst case by using a more sophisticated pivot strategy; this is done in the [median of medians](https://bliptext.com/articles/median-of-medians) algorithm.\nHowever, the overhead of computing the pivot is high, and thus this is generally not used in practice.\nOne can combine basic quickselect with median of medians as fallback to get both fast average case performance and linear worst-case performance; this is done in [introselect](https://bliptext.com/articles/introselect).\nFiner computations of the average time complexity yield a worst case of for random pivots (in the case of the median; other k are faster).\nThe constant can be improved to 3/2 by a more complicated pivot strategy, yielding the [Floyd–Rivest algorithm](https://bliptext.com/articles/floyd-rivest-algorithm), which has average complexity of for median, with other k being faster.","revisionCount":0},"hasMore":false,"nextCursor":null}

History