# Find n smallest values in an array

**URL:** https://discourse.julialang.org/t/find-n-smallest-values-in-an-array/42125
**Category:** New to Julia
**Tags:** question
**Created:** [June 26, 2020, 8:02pm UTC](https://discourse.julialang.org/t/find-n-smallest-values-in-an-array/42125 "2020-06-26T20:02:19Z")
**Posts on this page:** 6
**Page:** 1

<div class="post-metadata">

### Author: ![Vasily\_Ilin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vasily_ilin/32/7836_2.png) [@Vasily\_Ilin](https://discourse.julialang.org/u/Vasily_Ilin)
#### Post date: [June 26, 2020, 8:02pm UTC](https://discourse.julialang.org/t/find-n-smallest-values-in-an-array/42125/1 "2020-06-26T20:02:19Z")

</div>

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?

---

<div class="post-metadata">

### Author: ![heliosdrm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/heliosdrm/32/3851_2.png) [@heliosdrm](https://discourse.julialang.org/u/heliosdrm)
#### Post date: [June 26, 2020, 8:19pm UTC](https://discourse.julialang.org/t/find-n-smallest-values-in-an-array/42125/2 "2020-06-26T20:19:16Z")

</div>

A possibility is using `quantile` from the standard module `Stastitics`:

```julia
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)

---

<div class="post-metadata">

### Author: ![contradict](https://avatars.discourse-cdn.com/v4/letter/c/ac91a4/32.png) [@contradict](https://discourse.julialang.org/u/contradict)
#### Post date: [June 26, 2020, 8:21pm UTC](https://discourse.julialang.org/t/find-n-smallest-values-in-an-array/42125/3 "2020-06-26T20:21:46Z")

</div>

How about [`PartialQuickSort’](https://docs.julialang.org/en/v1/base/sort/#Base.Sort.PartialQuickSort)

```julia
using Base.Sort

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

```

---

<div class="post-metadata">

### Author: ![Vasily\_Pisarev](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vasily_pisarev/32/7929_2.png) [@Vasily\_Pisarev](https://discourse.julialang.org/u/Vasily_Pisarev)
#### Post date: [June 26, 2020, 8:38pm UTC](https://discourse.julialang.org/t/find-n-smallest-values-in-an-array/42125/4 "2020-06-26T20:38:07Z")

</div>

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

---

<div class="post-metadata">

### Author: ![contradict](https://avatars.discourse-cdn.com/v4/letter/c/ac91a4/32.png) [@contradict](https://discourse.julialang.org/u/contradict)
#### Post date: [June 26, 2020, 8:59pm UTC](https://discourse.julialang.org/t/find-n-smallest-values-in-an-array/42125/5 "2020-06-26T20:59:55Z")

</div>

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

---

<div class="post-metadata">

### Author: ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)
#### Post date: [June 27, 2020, 5:48am UTC](https://discourse.julialang.org/t/find-n-smallest-values-in-an-array/42125/6 "2020-06-27T05:48:32Z")

</div>

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](https://juliacollections.github.io/DataStructures.jl/latest/heaps/#Functions-using-heaps-1)