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

import Foundation

struct AuD_07_05_QuickSortRandom {

    static func QuickSort<A: Comparable>(a: inout [A], l: Int, r: Int) {

        func swap(i: Int, j: Int) {
            let t = a[i]
            a[i] = a[j]
            a[j] = t
        }

        func Partition(l: Int, r: Int) -> Int {
            let z = l + Int(arc4random_uniform(UInt32(r-l)))
            swap(i: z, j: r)
            let Pivot = a[r]
            var m = l
            for i in l ... r {
                if ( a[i] < Pivot) {
                    swap(i: i, j: m)
                    m = m+1
                }
            }
            swap(i: m, j: r)
            return m
        }

        if (l < r) {
            let m = Partition(l: l, r: r)
            QuickSort(a: &a, l: l, r: m-1)
            QuickSort(a: &a, l: m+1, r: r)
        }
    }

    static func run() {
        var aInt = [13, 7, 9, 12, 3, 0, 7, 30, 2, -7, 8, 12]
        QuickSort(a: &aInt, l: 0, r: aInt.count - 1)
        print(aInt.map( { s in s.description} ) . joined(separator: ", "))
    }
}