Published by Dimitris Kougioumtzis · Updated
Partition around a pivot, then retain only the partition containing the requested zero-based rank.
Partition and continue only in the side containing the requested rank, leaving irrelevant intervals unordered.
When to use Quickselect
Medians and order statistics without a full sort.
Choosing an alternative
Quicksort orders both sides; quickselect does not.
Worked example: input and state changes
Example input
9,1,7,1 | 2
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 9, 1, 7, 1 ], "active": [] }Step 3: Partition around pivot 1.
State at this checkpoint
{ "values": [ 9, 1, 7, 1 ], "active": [ 2, 3 ] }Step 5: Partition around pivot 9.
State at this checkpoint
{ "values": [ 1, 1, 7, 9 ], "active": [ 1, 3 ] }Step 8: Partition around pivot 7.
State at this checkpoint
{ "values": [ 1, 1, 7, 9 ], "active": [ 1, 2 ] }Step 10: Selected rank 2: value = 7.
State at this checkpoint
{ "values": [ 1, 1, 7, 9 ], "active": [ 2 ] }
Expected final state
Selected rank 2: value = 7.
Complexity and input bounds
Family: Selection. Time complexity: O(n²) worst; O(n) expected.
Space complexity: O(1) iterative selection state.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
2–24 comma-separated integers between 0 and 99. Follow with | zero-based rank (0 through length-1).
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
This deterministic pivot has a quadratic worst case; distinguish playground rank numbering from source indices.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | // Requires nonempty a and 0 <= k < n. Partitions a in place and returns the zero-based kth smallest value. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, n, k) { let l = 0; let r = n - 1; while (l <= r) { let pivot = a[r]; let pos = l; for (let j = l; j < r; j++) { if (a[j] < pivot) { let t = a[pos]; a[pos] = a[j]; a[j] = t; pos++; } } let pivotTemp = a[pos]; a[pos] = a[r]; a[r] = pivotTemp; if (pos == k) { return a[pos]; } if (pos < k) { l = pos + 1; } else { r = pos - 1; } } return -1; } |
Source
Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.
- Algorithm 65: find
C. A. R. Hoare (1961). Research paper.