In computer science, radix selection is a non-comparative selection algorithm, the selection analog of most-significant-digit (MSD) radix sort. It enables selecting the k-th largest or smallest element of an unsorted array, or the top k elements which do not have to be in sorted order. While the simplest implementation of radix selection is as an in-place algorithm, out-of-place parallel variants have also been developed for GPUs.
In-place radix selection In-place radix selection 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, swapping with (or, more efficiently, 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 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 Top-k sampling
References
