Given an array and an integer n, I would like to find n smallest elements of the array without sorting the whole array. Is there a pre-built function for this?

A possibility is using `quantile`

from the standard module `Stastitics`

:

```
julia> using Random
julia> x = randn(10)
10-element Array{Float64,1}:
-0.6379363809698851
-0.0090041220949053
0.17604345125452092
0.5721850349320371
-0.2539294101111369
1.9437627078528767
-1.8550277670889552
-0.6364790671658096
-0.33151525139752047
-0.6843143431198958
julia> using Statistics
julia> quantile(x, (0:2)./length(x))
3-element Array{Float64,1}:
-1.8550277670889552
-0.8013856855168016
-0.6472119733998872
```

(EDIT: the first attempt was wrong: start with 0, not 1)

How about `PartialQuickSortâ€™

```
using Base.Sort
function smallestn(a, n)
sort(a; alg=Sort.PartialQuickSort(n))[1:n]
end
```

1 Like

Yes, partial sort is whatâ€™s needed, and there are in fact `partialsort!`

and `partialsort`

functions.

Oh, right there and I missed it! Good eye.

You can use `Heap`

structure from `DataStructures.jl`

which can solve this sort of tasks very efficiently.

https://juliacollections.github.io/DataStructures.jl/latest/heaps/#Functions-using-heaps-1

1 Like