n smallest elements of array

Stream: Is there code for X?

[Adam Topaz]

Do we have some algorithm somewhere that finds the n smallest elements (with respect to some relation r) of an array? I could sort the array and take the first n elements, of course, but in my use case n is much smaller than the size of the array.

[Damiano Testa]

If your n is not much smaller than log Array.size it may not be much faster to sort first, I think.

[Adam Topaz]

Adam Topaz said:

... in my use case n is much smaller than the size of the array.

[Adam Topaz]

It's even much smaller than log of the size.

[Damiano Testa]

Ok, I consider log Array.size to be much smaller than Array.size! :lol:

[Damiano Testa]

Anyway, I have not come across it.

[Damiano Testa]

Except when n is 1: really small compared to n.

[Adam Topaz]

Yeah, me neither, thanks for confirming! Isn't "QuickSelect" a standard algorithm in the same vein as quicksort (which we do have)?

[Damiano Testa]

Btw, I was scarred by a feature of Array.qsort and I feel that I should share it: if your relation is not irreflexive, the output of .qsort need not be sorted.

#eval  -- true
  let unsorted := #[1, 1, 2, 1]
  unsorted.qsort (· ≥ ·) = unsorted

[Junyan Xu]

Quickselect is for selecting the single element at rank n.
The usual approach for the question in title would be maintaining a max-heap of size n while going through the array in a single pass, and constantly inserting the new element if it's smaller than the current max and popping out the max.

[Adam Topaz]

Ok, this should be quite easy to implement.

[Edward van de Meent]

if i understand the quickselect algorithm correctly you are (partially) sorting the array while doing it, so it actually gives the smallest k elements in the same time though?

[Adam Topaz]

if you select the right pivot, yes, so you could combine that with quickselect.

[Eric Rodriguez]

you should be able to take all items with index less than the n after quickselect, right? they won't be sorted though