Counting Sort

⚠️ This post was created when I was in high school and is no longer maintained.

1. Pesudocode

algorithm CountingSort(A, B, k):
    let C [0 - k]
    For i = 1 to k do --> initial counter
        C[i] = 0
    For j = 1 to A.len do
        C[A[j]]++ --> let C[i] contains the number of elements equals to i
    For i = 1 to k do
        C[i] = C[i] + C[i-1] --> let C[i] contains the number of elements less than or equals to i
    For j = A.len downto 1 do
        B[C[A[j]]] = A[j]
        C[A[j]]--
    

Tip: the reason why the last for loop is in reversed order is that we want to maintain the original position of each element such that keeping the order of the elements that have the same value as it is after sorting.

---

2. Time Complexity

1. overall time: \(Θ(n + k)\)
2. when \(when ~ k = O(n) \\ T(n) = \Theta(n)\)

   ---

3. Stability

An important property of counting sort is that it is stable: numbers with the same value appear in the output array in the same order as they do in the input array. That is, it breaks ties between two numbers by the rule that whichever number appears first in the input array appears first in the output array.

Normally, the property of stability is important only when satellite data are carried around with the element being sorted.

---

4. Code

object CountSortAlgo {
    def CountSort(array: Array[Int], arrayBuf: Array[Int], max: Int): Array[Int] = {
        val counter = Array.fill[Int](max+1)(0)

        var i:Int = 0
        for (i <- 0 until array.length) {
            counter(array(i)) += 1
        }
        for (i <- 1 until counter.length) {
            counter(i) += counter(i-1)
        }
        for (i <- (array.length-1) to 0 by -1) {
            arrayBuf(counter(array(i))) = array(i)
            counter(array(i)) -= 1
        }
        return arrayBuf.slice(1, arrayBuf.length)

    }

    def main(args: Array[String]): Unit = {
        val array = Array(5, 10, 9, 1, 8, 5, 6, 0, 0, 0, 5, 8, 10, 3, 2, 1, 5, 8)
        val arrayBuf = Array.fill[Int](array.length+1)(0)

        println(s"\nBefore sorting: ${array.deep.mkString(" ")}")        
        println(s"\nAfter sorting: ${CountSort(array, arrayBuf, 10).deep.mkString(" ")}")
    }
}

# Python
def count_sort(array, array_buf, max_val):
    counter = [0] * (max_val + 1)

    for i in range(len(array)):
        counter[array[i]] += 1
    for j in range(1, len(counter)):
        counter[j] += counter[j-1]
    for i in range(len(array)-1, -1,-1):
        array_buf[counter[array[i]]] = array[i]
        counter[array[i]] -= 1

    return array_buf[1:] 
    # we didn't use the first element so we do slicing here


if __name__ == "__main__":
    array = [5, 10, 9, 1, 8, 5, 6, 0, 0, 0, 5, 8, 10, 3, 2, 1, 5, 8]
    array_buf = [0] * (len(array)+1)    
    ''' we don't use [0] slot so we start from [1] 
    so consequemtly, we need (len()+1) slots''' 

    print("Before sorting: ", array)
    array_sorted = count_sort(array, array_buf, 10)
    print("After sorting:  ", array_sorted)