Sorting algorithms: partial quicksort usage

General Usage
,
1

Hi,

Im trying to understand the partial quicksort algorithm. I expected it work so that if I specify alg=PartialQuickSort(3) the algorithm sorts so that indexes 1,2,3 contains the smallest elements and the rest (4,…,n) is in unspecified order. I just tried the algorithm and the results are the following:

julia> arr = rand(10)
10-element Array{Float64,1}:
 0.0771121
 0.375159 
 0.537209 
 0.0500928
 0.578713 
 0.156671 
 0.829953 
 0.552534 
 0.81353  
 0.804142 

julia> ps = sort(arr, alg=PartialQuickSort(3))
10-element Array{Float64,1}:
 0.0500928
 0.0771121
 0.156671 
 0.375159 
 0.537209 
 0.552534 
 0.578713 
 0.804142 
 0.81353  
 0.829953 

julia> sort(arr, alg=PartialQuickSort(3)) == sort(arr)
true

Which is a little weird? Or is it? I expected it work like c++ STL function std::partial_sort - cppreference.com partial_sort.

2

Julia’s sort-implementation uses InsertionSort if the argument has less than 22 elements, no matter what algorithm you specify (see e.g. here):

julia> arr = rand(22);

julia> sort(arr, alg=PartialQuickSort(3)) == sort(arr)
false
3

I’m stupid or something.
But I cannot make this example to work, even for more than 22 elements

x = rand(100)
xx = sort(x; alg=PartialQuickSort(50))

The final length of xx is 100, and not 50 :slightly_frowning_face:

4

Did you see the first post?

the algorithm sorts so that indexes 1,2,3 contains the smallest elements and the rest (4,…,n) is in unspecified order

Also see this section in the manual:

the output array is only sorted up to index k

1 Like
5

ah…:smiley:
now I got it