Counting Sort

Here's is sort algorithm to use for an array of integers or structures that are keyed by an integer. Particularly useful when the range of integers is in the order of the size of the input.

The main idea is to determine the frequency of occurrence of the integers and use that to determine the sorted order.

An example: say we get the array {1,3,1,2}.

First determine the range of the integers, max and min, 1 and 3 for this input.

Next create an array, call it the counts array, that is the size of the integer range+1, so 3 (3-1+1) in this case.
Iterate over the input array, incrementing the appropriate entry in counts. The count of a given input value will be placed at counts[value - min]. For the given input, counts[0] will hold the count for the value 1.

This results in the counts array: {2,1,1}

Now determine the cumulative counts, which is essentially counts[i] = counts[i-1]+counts[i].

This results in the cumulative counts array: {2,3,4}

Create an output array for the sorted input.

Now, iterate over the input in reverse order.

At each step, retrieve the cumulative count for the value in the input array. The value will be placed at the output array index corresponding to the retrieved count - 1. Then decrement the cumulative count value.

In the first step, the value 2 is retrieved and a cumulative count of 3. The value should be placed at index 2 (3-1) in the output.

In the next iteration, the value 1 and the cumulative count 2; so this '1' is placed at index 1 (2-1) of the output.

Continuing, the value 3 and the cumulative count 4; placing it at index 3 of the output.

Finally, the value 1 for the second time and a cumulative count of 1 (since the count was decremented the first time it was seen); so this '1' is placed at index 0 of the output.

, See how iterating in reverse preserves the order of equal elements making the sort 'stable'

The resulting sorted array is {1,1,2,3}

func CountingSort(in []int) []int {
    // find the min/max values
    min := slices.Min(in)
    max := slices.Max(in)
    // create the count array
    counts := make([]int, max-min+1)
    for _, v := range in {
        counts[v-min]++
    }
    // determine cumulative counts
    for i := 1; i < len(counts); i++ {
        counts[i] = counts[i-1] + counts[i]
    }
    // create the output array
    out := make([]int, len(in))
    for i := range in {
        v := in[len(in)-1-i]
        out[counts[v-min]-1] = v
        counts[v-min]--
    }
    return out
}

Can it be made more efficient? Leave your comments and suggestions below.

Thanks!

The code for this post and all posts in this series can be found here

The above is the detailed content of Counting Sort. For more information, please follow other related articles on the PHP Chinese website!