/**
 * 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_07_CountingSort {

    static func CountingSort(a: inout [Int], l: Int, r: Int) {

        if (r - l <= 1) {
            return
        }

        let M: Int = a.max(by: { (x,y) in x < y } ) ?? 0

        var count: [Int] = Array(repeating: 0, count: M+1)

        for i in l...r {
            count[a[i]] = count[a[i]] + 1
        }
        var i = l
        for j in 1 ... M {
            for _ in 1 ... count[j] {
                a[i] = j
                i = i + 1
            }
        }
    }

    static func run() {
        var a: [Int] = [6,8,9,2,3,10,7,5,1,4]
        CountingSort(a: &a, l: 0, r: a.count-1)
        print(a.map({ (x) in String(x)} ).joined(separator: ", "))
    }

}