Find n smallest values in an array

New to Julia
1

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?

2

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)

3

How about `PartialQuickSort’

using Base.Sort

function smallestn(a, n)
  sort(a; alg=Sort.PartialQuickSort(n))[1:n]
end
2 Likes
4

Yes, partial sort is what’s needed, and there are in fact partialsort! and partialsort functions.

5

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

6

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