Find n smallest values in an array

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}:

julia> using Statistics

julia> quantile(x, (0:2)./length(x))
3-element Array{Float64,1}:

(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]
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.

1 Like