Easy Tutorial
❮ Quick Sort 2 Node Multi Version ❯

1.8 Counting Sort

Category Algorithm

The essence of counting sort is to transform the input data values into keys stored in an additional array space. As a sorting algorithm with linear time complexity, counting sort requires that the input data must be integers with a definite range.

When the input elements are n integers between 0 and k, its running time is Θ(n + k). Counting sort is not a comparison sort, and it is faster than any comparison sort algorithm.

Since the length of the array C used for counting depends on the range of data in the array to be sorted (equal to the difference between the maximum and minimum values of the array to be sorted plus 1), this makes counting sort require a lot of time and memory for arrays with a large data range. For example: counting sort is the best algorithm for sorting numbers between 0 and 100, but it is not suitable for sorting names in alphabetical order. However, counting sort can be used in the algorithm of radix sort to sort arrays with a large data range.

Understandably, for example, if there are 10 people with different ages, and it is counted that 8 people are younger than person A, then A's age is the 9th, and this method can be used to determine the position of everyone else, thus sorting them. Of course, when there are duplicate ages, special handling is required (to ensure stability), which is why the target array needs to be filled in reverse at the end, and the count of each number needs to be reduced by 1.

The steps of the algorithm are as follows:

2. Animation Demonstration


Code Implementation

JavaScript

Example

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue+1),
        sortedIndex = 0;
    arrLen = arr.length,
    bucketLen = maxValue + 1;

    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }

    return arr;
}

Python

Example

def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]]=0
        bucket[arr[i]]+=1
    for j in range(bucketLen):
        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr

Go

Example

func countingSort(arr []int, maxValue int) []int {
    bucketLen := maxValue + 1
    bucket := make([]int, bucketLen) // Array initialized to 0

    sortedIndex := 0
    length := len(arr)

    for i := 0; i < length; i++ {
        bucket[arr[i]] += 1
    }

    for j := 0; j < bucketLen; j++ {
        for bucket[j] > 0 {
            arr[sortedIndex] = j
            sortedIndex += 1
            bucket[j] -= 1
        }
    }

    return arr
}

Java

Example

``` public class CountingSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
    // Make a copy of arr, do not change the content of the parameter
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

    int maxValue = getMaxValue(arr);

    return countingSort(arr, maxValue);
}

private int[] countingSort(int[] arr, int maxValue) {
    int bucketLen = maxValue + 1;
    int[] bucket = new int[bucketLen];

    for (int value :

Click here to share notes

Cancel

-

-

-

-1.0 Top Ten Classic Sorting Algorithms

-1.1 Bubble Sort

-1.2 Selection Sort

-1.3 Insertion Sort

-1.4 Shell Sort

-1.5 Merge Sort

-1.6 Quick Sort

-1.7 Heap Sort

-1.9 Bucket Sort

-1.10 Radix Sort

Follow on WeChat

❮ Quick Sort 2 Node Multi Version ❯