056_kth_smallest.sio

//@ run-pass
// HumanEval 056: Kth Smallest Element
//
// Find the kth smallest element in an unsorted array using partial
// selection sort. k is 1-indexed (k=1 means the smallest).
// Performs k passes of selection to avoid full sort.

struct Buf { data: [i64; 256] }

fn kth_smallest(arr: [i64; 256], n: i64, k: i64) -> i64 with Mut, Panic {
    // Copy to working buffer to avoid modifying input
    var buf = Buf { data: [0; 256] }
    var c: i64 = 0
    while c < n {
        buf.data[c] = arr[c]
        c = c + 1
    }

    // Partial selection sort: find minimum k times
    var pass: i64 = 0
    while pass < k {
        var min_idx = pass
        var j: i64 = pass + 1
        while j < n {
            if buf.data[j] < buf.data[min_idx] {
                min_idx = j
            }
            j = j + 1
        }
        // Swap
        let tmp = buf.data[pass]
        buf.data[pass] = buf.data[min_idx]
        buf.data[min_idx] = tmp
        pass = pass + 1
    }

    buf.data[k - 1]
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: [3, 1, 4, 1, 5, 9], k=1 -> 1
    var a1: [i64; 256] = [0; 256]
    a1[0] = 3
    a1[1] = 1
    a1[2] = 4
    a1[3] = 1
    a1[4] = 5
    a1[5] = 9
    assert(kth_smallest(a1, 6, 1) == 1)

    // Test 2: [3, 1, 4, 1, 5, 9], k=3 -> 3
    // sorted: [1, 1, 3, 4, 5, 9]
    assert(kth_smallest(a1, 6, 3) == 3)

    // Test 3: [7, 2, 8, 5], k=2 -> 5
    // sorted: [2, 5, 7, 8]
    var a3: [i64; 256] = [0; 256]
    a3[0] = 7
    a3[1] = 2
    a3[2] = 8
    a3[3] = 5
    assert(kth_smallest(a3, 4, 2) == 5)

    // Test 4: single element [42], k=1 -> 42
    var a4: [i64; 256] = [0; 256]
    a4[0] = 42
    assert(kth_smallest(a4, 1, 1) == 42)

    // Test 5: [10, 20, 30, 40, 50], k=5 -> 50
    var a5: [i64; 256] = [0; 256]
    a5[0] = 10
    a5[1] = 20
    a5[2] = 30
    a5[3] = 40
    a5[4] = 50
    assert(kth_smallest(a5, 5, 5) == 50)

    // Test 6: [50, 40, 30, 20, 10], k=3 -> 30
    var a6: [i64; 256] = [0; 256]
    a6[0] = 50
    a6[1] = 40
    a6[2] = 30
    a6[3] = 20
    a6[4] = 10
    assert(kth_smallest(a6, 5, 3) == 30)

    println("056_kth_smallest: ALL TESTS PASSED")
    0
}