Plans for an algorithm to find Kth Order Statistic from Array?

vanvoorden · February 16, 2024, 8:31pm

Hi! I just started searching through the algorithms package and I don't (yet) see if there is an algorithm for selecting the Kth Order Statistic from a Swift Array or Set. My guess is this would also be expected to run in linear time. Is this named something else in the package? Were there plans or blockers for shipping this in the future? Thanks!

vanvoorden · April 15, 2025, 11:41pm

I still was looking for any more clues on this… I found another place I would have wanted this ability. I did find the min-max functions… but this looks like it would return the k smallest or largest elements sorted. My preference would have been to either just return the Kth Order Statistic or return the k elements unsorted.

github.com/apple/swift-algorithms

Guides/MinMax.md

main

# Minima and/or Maxima

[[Source](https://github.com/apple/swift-algorithms/blob/main/Sources/Algorithms/MinMax.swift) | 
 [Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/MinMaxTests.swift)]

Returns the smallest or largest elements of this collection, sorted by a 
predicate or in the order defined by `Comparable` conformance.

If you need to sort a collection but only need access to a prefix or suffix of 
the sorted elements, using these methods can give you a performance boost over 
sorting the entire collection. The order of equal elements is guaranteed to be 
preserved.

```swift
let numbers = [7, 1, 6, 2, 8, 3, 9]
let smallestThree = numbers.min(count: 3, sortedBy: <)
// [1, 2, 3]
```

Return the smallest and largest elements of this sequence, determined by a

This file has been truncated. show original

vanvoorden · December 23, 2025, 11:16pm

I think what we are looking for would be similar to nth_element from <algorithm> in C++.

Did anyone else want this? I could work on a pitch if anyone else was waiting for that.