//: Playground - noun: a place where people can play

import UIKit

var str = "Hello, playground"

func max(a:[Int], n:Int) -> Int
{
    var m = a[0]
    for i in 0...(n - 1) {
        if (a[i] > m) {
            m = a[i]
        }
    }
    return m
}

// modified countsort to sort by the frequecy of the least significant bit
// count[fi]++ where fi = (input[i] / x) % 10
func countSort(inout a:[Int], n:Int, x:Int)
{
    // output array and frequency array 10 is used to represent digits 0-9
    var outp = [Int](count: n, repeatedValue: 0)
    var freq = [Int](count: 10, repeatedValue: 0)


    // build a frequency list freq by counting the least significant digit represented by (input[i] / x) % 10
    for i in 0...(n - 1) {

        var fi = (a[i] / x) % 10
        freq[fi]++
    }

    // Change count[i] so that count[i] now contains actual position of
    // this value in output array
    for i in 1...(freq.count - 1) {
        freq[i] += freq[i - 1]
    }


    // build output of the list calculating the freqency table index (fi) where i -> n...0
    for (var i = (n - 1); i >= 0; i--) {

        // calculate the position of the least significant digit index in the frequency table
        var fi = (a[i] / x) % 10

        outp[freq[fi] - 1] = a[i]
        freq[fi]--
    }

    // copy temp array to new array
    for i in 0...(n - 1) {
        a[i] = outp[i]
    }
}

func radixSort(inout a:[Int], n:Int)
{
    var m = max(a, n)

    // repeatadly count sort on the least significant digit on each pass
    for var x = 1;  m/x > 0; x *= 10 {
        countSort(&a, n, x)
    }
}

var a = [170,45, 4, 170, 45, 75, 90, 802, 24, 2, 66, 1000]
radixSort(&a, a.count)