Radix selection
| Class | Selection algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | , where is the number of keys, and is the key length. |
In computer science, radix selection is a non-comparative selection algorithm, the selection analog of most-significant-digit (MSD) radix sort.[1] It is an in-place algorithm for selecting the k-th largest or smallest element of an unsorted array, or top k elements which do not have to be in sorted order.[1][2][3][4] Its worst-case running time is , where is the number of keys, and is the key length.[1]
How radix selection works
MSD Radix Select works on array elements one digit at a time, starting from the most significant digit (MSD). For instance, if an array of integers is being sorted, then the most significant digit of each array element is examined, counting how many 9's there are, 8's there are, 7's and so on, until 0's - for decimal number representation.
Once it is known how many elements have a 9 in the most significant digit, and 8 in the most significant digit and so on, the size of these bins is known, and the starting and ending array index for each of these bins can be computed. Since we are selecting a k-th element of the array, then it's know which bin the k-th element is in. This is the only bin that needs to be populated with its elements, in its target location. The rest of the array elements are not needed and can be ignored.
To gather all of the array elements that belong in the target bin (with the k-th element inside it) we start on the left side of the array, looking for an element that belongs in the target bin. Once we find one, we look inside the target bin for the first element that does not belong in this bin. The element outside of the bin is then written into the bin, overwriting the element that does not belong. This process continues until all array elements to the left of the bin have been moved inside the bin.
Now, the array to the right of the target bin is scanned for elements that belong inside the bin, until the end of the array has been reached. As elements that belong are found they are moved inside the bin by scanning inside the bin for elements that don't belong and pairing them up with elements outside the bin which belong.
Once the target bin has all of the elements that belong in it has been assembled, by moving (and not swapping) elements from the outside of the bin that belong in the bin, the bin is processed in the same way recursively using the next most significant digit. This process continues until either the target bin (with the k-th index inside it) has a single element or all of the digits have been used and we have run out of digits. Then the k-th element of the array is returned.
See also
References
- ↑ 1.0 1.1 1.2 Alabi, Tolu; Blanchard, Jeffrey D.; Gordon, Bradley; Steinbach, Russel (July 2012). "Fast k-selection algorithms for graphics processing units" (PDF). ACM Journal of Experimental Algorithmics. 17. doi:10.1145/2133803.2345676. Archived from the original (PDF) on November 16, 2025.
- ↑ Li, Y.; Zhou, B.; Zhang, J. (2024). "RadiK: Scalable and Optimized GPU-Parallel Radix Top-K Selection". Proceedings of the 38th ACM International Conference on Supercomputing. pp. 537–548. arXiv:2501.14336. doi:10.1145/3650200.3656596. ISBN 979-8-4007-0610-3. Search this book on
- ↑ Leckey, Kevin; Neininger, Ralph; Sulzbach, Henning (1 February 2019). "Process convergence for the complexity of Radix Selection on Markov sources". Stochastic Processes and their Applications. 129 (2): 507–538. arXiv:1605.02352v2. doi:10.1016/j.spa.2018.03.009.
- ↑ Zhang, Christina. "Accelerating top-k computation on GPU. NVIDIA" (PDF). Retrieved January 1, 2020.
This article "Radix selection" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Radix selection. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
