counting sort

See On Github

Data

Contributor

Generic placeholder thumbnail

by jcla1

 in go

Tags

distribution sort, sorting, stable sort

Source Code

package countingsort


// Warning: Only works with slices that
//          have non-negative entries!
func CountingSort(arr []int) []int {
    maximum := max(arr)
    aux := make([]int, maximum+1)

    for _, v := range arr {
        aux[v] += 1
    }

    ordered := make([]int, 0, len(arr))

    for i, v := range aux {
        for j := 0; j < v; j++ {
            ordered = append(ordered, i)
        }
    }

    return ordered
}

func max(arr []int) int {
    if len(arr) < 1 {
        return 0
    }

    maximum := arr[0]

    for _, v := range arr {
        if v > maximum {
            maximum = v
        }
    }

    return maximum
}
package countingsort

import "testing"

func TestCountingSort(t *testing.T) {
    arrs := [][]int{[]int{2, 1, 3, 4, 1, 2, 1, 5, 4}, []int{2, 3, 7, 5, 1, 4, 10}}

    var result []int

    for _, arr := range arrs {
        result = CountingSort(arr)
        if !isSorted(result) {
            t.Errorf("CountingSort(%v) = %v", arr, result)
        }
    }
}

func isSorted(arr []int) bool {
    for i := 1; i < len(arr); i++ {
        if arr[i-1] > arr[i] {
            return false
        }
    }

    return true
}