/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 2, Qualität von Algorithmen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_02_03_QuickSelect {

    static func QuickSelect(M: [Int], k: Int) -> Int {
        let ri =  (M.count == 1) ? 0 : Int(arc4random_uniform(UInt32(M.count-1)))
        let x = M[ri]
        let MLess = M.filter( { (y) in y < x } )
        let MGreater = M.filter( { (y) in y > x } )
        let countLE = MLess.count + 1
        if (countLE == k) {
            return x
        } else if (k < countLE) {
            return QuickSelect(M: MLess, k: k)
        } else {
            return QuickSelect(M: MGreater, k: k - countLE)
        }
    }

    static func run() {
        let L = [0,791,35,81,5,75,1,534,7,88,57,3,45,2,4]
        var LSorted: [Int] = [0,791,35,81,5,75,1,534,7,88,57,3,45,2,4].sorted()

        // zum Vergleich von der API sortiert
        print(LSorted.map( { (i)  in String(i) } ).joined(separator: ","))

        let sortedByQuickselect =
                L.indices.map( { (i) in QuickSelect(M: L, k: i+1) } )

        print( sortedByQuickselect.map( { (i)  in String(i) } ).joined(separator: ",") )
    }
}