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

import Foundation

struct AuD_03_09_QuickSort {

    static func Quicksort(lst: [Int]) -> [Int] {
        guard let first = lst.first else {
            return []
        }
        let pivot = first
        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: ","))
    }

}