Partial Sort

Partial Sort

In computer science, partial sorting is a relaxed variant of the sorting problem. Total sorting is the problem of returning a list of items such that its elements all appear in order, while partial sorting is returning a list of the k smallest (or k largest) elements in order. The other elements (above the k smallest ones) may also be stored, as in an in-place partial sort, or may be discarded, which is common in streaming partial sorts. A common practical example of partial sorting is computing the "Top 100" of some list. A further relaxation only requires returning a list of the k smallest elements, but without requiring that these be ordered. This latter form is quite close to the selection problem, and a solution to one problem can be easily converted to a solution to the other.

In terms of indices, in a partially sorted list, for every index i from 1 to k, the ith element is in the same place as it would be in the fully sorted list: element i of the partially sorted list contains order i of the input list.

Example

Here is an example:

> x <- round(runif(20), 2)

> x

 [1] 0.18 0.23 0.03 0.97 0.41 0.87 0.79 0.16 0.11 0.85 0.96 0.74 0.56

[14] 0.34 0.75 0.03 0.34 0.39 0.01 0.71

> x <- sort(x, partial = seq(5, 20, 5))

> matrix(x, nrow=5)

     [,1] [,2] [,3] [,4]

[1,] 0.01 0.18 0.71 0.79

[2,] 0.11 0.23 0.74 0.96

[3,] 0.03 0.34 0.56 0.85

[4,] 0.03 0.34 0.41 0.87

[5,] 0.16 0.39 0.75 0.97

> 

Notice that the first five values (first column) are the 5 lowest, the next 5 are the next lowest, and so on.  (Notice also that in this example the last group consists of the 20th value by itself, which is therefore the maximum for the entire vector in the partially sorted version.)

Algorithm

function quicksortFirstK(list, left, right, k)

     if right > left

         select pivotIndex between left and right

         pivotNewIndex := partition(list, left, right, pivotIndex)

         quicksortFirstK(list, left, pivotNewIndex-1, k)

         if pivotNewIndex < left + k

             quicksortFirstK(list, pivotNewIndex+1, right, k)