# Rosalind: PS — Partial Sort
# https://rosalind.info/problems/ps/
#
# Given: A positive integer n, an array A[1..n] of integers, and a positive
# integer k.
# Return: The k smallest elements of a sorted array A.

let a = [4, -6, 7, 8, -9, 100, 12, 13, 56, 17]
let k = 3

# Only the first k elements are wanted, so a heap of size k is the usual answer:
# it keeps the work at n log k rather than n log n. With k = 3 out of 10 the
# distinction is academic, so this takes the direct route and sorts. The shape
# of the answer is the same; PS and MED together are the pair worth comparing,
# since MED shows the selection that avoids the full sort.
let smallest = slice(sort(a), 0, k)
let result = smallest |> map(|v| str(v)) |> join(" ")

println("Result:   " + result)
println("Expected: -9 -6 4")

fn test_ps_k_smallest() {
    assert result == "-9 -6 4", "PS: got " + result
    assert len(smallest) == k, "PS: expected " + str(k) + " values, got " + str(len(smallest))
}