Look at the animation algorithm: sorting - cardinal sorting

brief introduction

In the previous article, we talked about count sorting, but count sorting has a limitation, because the count array is limited. If the range of elements in the array is too large, it is unrealistic to use count sorting, and its time complexity will expand.

The way to solve the large-scale element sorting is cardinality sorting.

Example of cardinality sorting

What is cardinality sorting?

Consider that although we can't directly sort all numbers in the range using the count array, we can consider n rounds of count sorting according to the number of digits, and each round only sorts one digit of the number.

Finally, you can still get the result, and you can get rid of the size limit of count array, which is cardinality sorting.

Suppose that the elements of the array are: 1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793.

Let's first look at the animation and the most intuitive cardinality sorting process:

In the above example, we first count the individual bits, then count the ten bits, and then the hundreds and thousands.

Finally, the final sorting result is generated.

java code implementation of cardinality sorting

Because cardinality sorting is actually sorting by count of digits. Therefore, we can reuse the code of count sorting written before, but we just need to make some modifications.

In addition to passing in the array, the doCountingSort method also needs to pass in the digit of sorting, which is represented by 1,101001000.

Take a look at the modified doCountingSort method:

   public void doRadixSort(int[] array, int digit){
        int n = array.length;

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

        // Count array is used to store and count the number of occurrences of each element
        int count[] = new int[10];
        Arrays.fill(count,0);
        log.info("initialization count value:{}",count);

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

        // Here is a trick. We calculate the subscript of the corresponding element that should appear in output for the first time according to the number of occurrences of the element in count.
        //The subscripts here are numbered from right to left
        for (int i=1; i<10; i++) {
            count[i] += count[i - 1];
        }
        log.info("arrangement count Corresponding output subscript:{}",count);
        // Build the sorted array according to the subscript in count
        //After inserting one, the corresponding count subscript will be subtracted by one
        for (int i = n-1; i>=0; i--)
        {
            output[count[(array[i]/digit)%10]-1] = array[i];
            count[(array[i]/digit)%10]--;
        }
        log.info("structure output Later output value:{}",output);

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

The difference is that we need to use count[(array[i]/digit)%10] to sort each bit.

In addition, in order to calculate the value of digit, we also need to get the value of the largest element in the array:

public int getMax(int[] array)
    {
        int mx = array[0];
        for (int i = 1; i < array.length; i++)
            if (array[i] > mx){
                mx = array[i];
            }
        return mx;
    }

See how to call:

    public static void main(String[] args) {
        int[] array= {1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793};
        RadixSort radixSort=new RadixSort();
        log.info("radixSort The previous array is:{}",array);
        //Get the maximum value of the array and use it to calculate digit
        int max = radixSort.getMax(array);
        //According to the number of bits, traverse to sort by count
        for (int digit = 1; max/digit > 0; digit *= 10){
            radixSort.doRadixSort(array,digit);
        }
    }

Look at the output:

Good, the results are sorted.

Time complexity of cardinality sorting

From the calculation process, we can see that the time complexity of Radix sorting is O(d*(n+b)), where B is the base number of numbers. For example, if we use base 10 above, b=10.

D is the number of rounds to cycle, that is, the maximum number of digits in the array. If the largest number in the array is represented by K, then d=logb(k).

To sum up, the time complexity of cardinality sorting is O((n+b) * logb(k)).

When k < = NC, where c is a constant, the above time complexity can be approximately equal to O(nLogb(n)).

In the case of b=n, the time complexity of Radix sorting can be approximately equal to the linear time complexity O(n).

Code address of this article:

learn-algorithm

This article has been included in http://www.flydean.com/algorithm-radix-sort/

The most popular interpretation, the most profound dry goods, the most concise tutorial, and many tips you don't know are waiting for you to find!

Welcome to my official account: "procedures and things". I understand technology and you better!

Tags: Java Algorithm Permutation array log

Posted by Democreous on Wed, 11 May 2022 15:44:24 +0300