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

    static func digit(k: Int, n: Int) -> Int {
        var nn = n
        var digits: [Int] = []
        while (nn > 0) {
            digits = [nn % 10] + digits
            nn = nn / 10
        }
        if (digits.count - k >= 0 && digits.count - k < digits.count) {
            return digits[digits.count - k]
        } else {
            return 0
        }
    }

    static func SortByDigit(a: inout [Int], l: Int, r: Int, k: Int) {
        let R = 10
        var count: [Int] = Array(repeating: 0, count: R)
        var pos: [Int] = Array(repeating: 0, count: R)
        var b: [Int] = Array(repeating: 0, count: a.count)

        var j: Int = 0

        for i in l ... r {
            j = digit(k: k, n: a[i])
            count[j] = count[j] + 1
        }

        var i = l
        for j in 0 ..< R {
            pos[j] = i
            i = i + count[j]
        }

        for i in l ... r {
            j = digit(k: k, n: a[i])
            b[pos[j]] = a[i]
            pos[j] = pos[j] + 1
        }

        for i in l ... r {
            a[i] = b[i]
        }
    }

    static func run() {
        var a : [Int] = [331, 401, 420, 30, 321, 220, 1, 402, 322, 343]
        SortByDigit(a: &a, l: 0, r: a.count-1, k: 2)
        print(a.map({ (x) in String(x)} ).joined(separator: ", "))
    }
}