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)
No comments:
Post a Comment