/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 4, Listen: Immer einer nach dem anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_04_04_QuickSortFunctional {

    static func Quicksort(lst: [Int]) -> [Int] {
        if (lst.count <= 1) {
            return lst
        } else {
            let pivot = lst[0]
            let l1 = lst.filter( { x in x < pivot } )
            let l2 = lst.filter( { x in x == pivot } )
            let l3 = lst.filter( { x in x > pivot } )
            return Quicksort(lst: l1) + l2 + Quicksort(lst: l3)
        }
    }

    static func run () {
        let lst = [-1, 5, 7, 7, 3, 4, -2, 3, 6, 7, -7, 9, 3, 8, 5, -1, 0, 2, 3, 7, -4, 6, 5]
        print(Quicksort(lst: lst).map( { i in String(i)} ).joined(separator: ","))
    }

}