Introduction to the

Today we are going to introduce an algorithm that can sort without comparison: count sort.

Count sort is a space for time algorithm, we use an external count array to count the number of occurrences of each element, and finally complete the sort.

Example of a count sort

Count sorting is limited because the size of the external count array is the same as the size of the original array, so count sorting is generally only suitable for a small range of elements in the array.

Let’s take an example of ordering elements 0-9:3,4,2,5,6,2,4,9,1,3,5.

Let’s start with an animation to see how this is sorted:

The count array contains the number of occurrences from 0 to 9.

We go through the original array, and when we find the corresponding number, we give the corresponding count+1.

After all the elements count, restore the sorted array based on the value in the count array.

Java implementation of count sort

Count sorting is very simple, we mainly master the following two big steps:

1. Iterate through the original array to build the count array.
2. Rebuild the sorted array from the count value in the count array.

public class CountingSort {

    public void doCountingSort(int[] array){
        int n = array.length;

        // Store the sorted array
        int output[] = new int[n];

        // The count array is used to count the number of occurrences of each element
        int count[] = new int[10];
        for (int i=0; i<10; ++i) {
            count[i] = 0;
        }
        log.info("Initialize count :{}",count);

        // Store the number of occurrences in the original array into the count array
        for (int i=0; i<n; ++i) {
            ++count[array[i]];
        }
        log.info("Count after count :{}",count);

        // Iterate over count and insert the corresponding data into output
        int j=0;
        for(int i=0; i<10; i++){
            while(count[i]-- > 0){
                output[j++]=i;
            }
        }
        log.info(Output value :{},output);

        // Write the sorted array back to the original array
        for (int i = 0; i<n; ++i)
            array[i] = output[i];
    }

    public static void main(String[] args) {
        int[] array= {3.4.2.5.6.2.4.9.1.3.5};
        CountingSort countingSort=new CountingSort();
        log.info("The array before countingSort is :{}",array); countingSort.doCountingSort(array); }}Copy the code

The comments above should be clear.

The results are as follows:

Count is the second way of sorting

After we get the number of each element in the count array, we actually have another way of generating the result array:

// Here is a trick. We calculate the index of the first occurrence of an element in output based on the number of occurrences in count.
        // The subscripts are numbered from right to left
        for (int i=1; i<10; i++) {
            count[i] += count[i - 1];
        }
        log.info("Output subscript {}",count);
        // Build the sorted array according to the subscript in count
        // After one is inserted, the corresponding count subscript is decreased by one
        for (int i = n-1; i>=0; i--)
        {
            output[count[array[i]]-1] = array[i];
            --count[array[i]];
        }
        log.info(Output value :{},output);
Copy the code

There are two main steps:

In the first step, we calculate the index of the first occurrence of the corresponding element in output based on the number of occurrences of the element in count. The subscripts here are numbered from right to left.

The second step is to construct the sorted array based on the subscript of count. When one is inserted, the corresponding subscript of count is reduced by one.

It might not be easy to understand, but you can think about it a little bit with the output.

Time complexity of count sort

From the code above, we can see that the count sort actually does only a small number of traversals. So its time is order n.

The code address of this article:

learn-algorithm

This article has been included in www.flydean.com/algorithm-c…

The most popular interpretation, the most profound dry goods, the most concise tutorial, many tips you didn’t know waiting for you to discover!

Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!