Geek algorithm training notes (10), ten classical sort count sort, radix sort

directory

Non-comparison class sorting

Finally, we come to the last two algorithms, the linear time complexity algorithm of the non-comparison class, counting sort and radix sort. On an article also mentioned that it is not difficult to understand these sorting algorithms, time and space complexity analysis is also very simple, but very demanding to to sort the data requirement, mentioned in the previous bucket sort is applicable to the sorting of the external, the so-called external sorting is data stored in an external disk, the data quantity is big, the memory is limited, Unable to load all the data into memory.

Counting sort is actually a special case of bucket sort. When the n numbers that we want to sort are on a small scale, for example, the maximum is k, we can divide the data into k buckets. The data values in each bucket are the same, saving the sorting time in the bucket.

Counting sort scenario

For example, the gaokao scoring system will show our scores and the ranking of our province. If your province has half a million examinees, how do you get the ranking through quick ranking?

❝

The full score of examinees is 900 and the minimum score is 0. This data range is very small, so we can divide it into 901 buckets with scores ranging from 0 to 900. According to the scores of the examinees, we divided the 500,000 examinees into these 901 buckets. The data in the bucket are all examinees with the same score, so there is no need to sort. We just need to scan each bucket in turn, output the examinees in the bucket in turn into an array, and achieve a sort of 500,000 examinees. Because only scan traversal is involved, the time complexity is O(n).

❞

So the idea of counting sort is that it’s very similar to bucket sort, except that the granularity of the bucket is different.

Radix sort scenario

Suppose we have 100,000 mobile phone numbers, and we want to sort the 100,000 mobile phone numbers from the smallest to the largest. What is the quick sorting method?

❝

For bucket sort, count sort, mobile phone number has 11 bits, the range is too large, obviously not suitable for these two sorting algorithms. Mobile phone numbers have a rule like this: suppose you want to compare the size of two mobile phone numbers A and B, if in the first few digits, a is already larger than B, then you don’t need to look at the last few digits. The idea is to sort the phone number by the last digit, then by the second to last, and so on, and finally by the first digit. After 11 sequences, the phone numbers were in order.

❞

This is the algorithm idea of radix sort, radix sort to the data to sort is required, need to be separated into independent “bits” to compare, and there is a progressive relationship between the bits, if “A” data high than “B” data, the rest of the low bits do not need to compare. In addition, the data range of each bit should not be too large, so that the linear sorting algorithm can be used to sort, otherwise, the time complexity of radix sort cannot be O(n).

Count sorting

Algorithm thought

A temporary array is used to count the number of occurrences of the element. For example, temp[I] = m indicates that the number of occurrences of element I is m. Finally, the temporary array is aggregated from small to large, so that the aggregated data is in order.

Dynamic graph demonstration

As can be seen from the figure, counting sort needs to create a temporary array to store, first through the original array one by one, and then through the temporary array one by one.

Code implementation

public class CountSort {



    public static int[] countSort(int[] arr) {

        if (arr == null || arr.length < 2) {

            return arr;

        }



        int length = arr.length;

        int max = arr[0];

        int min = arr[0];

        // The maximum and minimum values of the array

        for (int i = 1; i < arr.length; i++) {

            if(arr[i] < min) {

                min = arr[i];

            }



            if(max < arr[i]) {

                max = arr[i];

            }



        }



        // Create a temporary array of size Max

        int[] temp = new int[max + 1];

        // Count the number of occurrences of element I

        for (int i = 0; i < length; i++) {

            temp[arr[i]]++;

        }



        // Add the temporary array to the original array

        int k = 0;

        for (int i = 0; i <= max; i++) {

            for (int j = temp[i]; j > 0; j--) {

                arr[k++] = i;

            }

        }



        return arr;

    }





    public static void main(String[] args) {

        int[] arr = {21.4.12.42.46.23.27.11.6.5.33.29.41.46.40.13.31};

        arr = countSort(arr);

        System.out.print("After sorting array:");

        for (int i=0; i<arr.length; i++) {

            System.out.print(arr[i] + "，");

        }



    }



}



Copy the code

Time complexity analysis

O(n+k)

Spatial complexity analysis

O(n+k)

Stability analysis

stable

Suitable conditions

Count sort can only be used in scenarios where the data range is small. If the data range “K” is much larger than the data to be sorted “N”, count sort is not suitable. Moreover, counting sort can only sort non-negative integers. If the data to be sorted is of another type, it is converted to a non-negative integer without changing its relative size.

For example, take the examinee. If the score is accurate to the last decimal place, we need to multiply all the scores by 10, round them up, and then put them in 9,010 buckets. For example, if there are negative numbers in the range [-1000, 1000], then we need to increment each number by 1000 to a non-negative integer, because the bottom of the array cannot be negative.

Radix sort

Algorithm thought

One, ten, a hundred… The numeric size of the bit sorts the array, and finally summarizes the overall ordered array.

Dynamic graph demonstration

If the number is less than two digits, it can be compared with ten digits:

The first time is in accordance with the units digit, the resulting array is a digit order;

The second time according to the ten digit row, the array is all ordered;

Code implementation

import java.util.ArrayList;



public class RadixSort {



    public static int[] radixSort(int[] arr) {

        if(arr == null || arr.length < 2) return arr;



        int n = arr.length;

        int max = arr[0];

        / / Max

        for (int i = 1; i < n; i++) {

            if (max < arr[i]) {

                max = arr[i];

            }

        }



        // Calculate the maximum number of digits

        int num = 1;

        while (max / 10 > 0) {

            num++;

            max = max / 10;

        }



        // Create 10 buckets

        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(10);

        // Initialize the bucket

        for (int i = 0; i < 10; i++) {

            bucketList.add(new ArrayList<Integer>());

        }



        // Sort each run, starting with the ones digit

        for (int i = 1; i <= num; i++) {

            for (int j = 0; j < n; j++) {



                // The i-th bit of each number is an array

                int radio = (arr[j] / (int)Math.pow(10,i-1)) % 10;

                // Put it in the appropriate bucket

                bucketList.get(radio).add(arr[j]);



            }



            // merge back to the original array

            int k = 0;

            for (int j = 0; j < 10; j++) {

                for (Integer t : bucketList.get(j)) {

                    arr[k++] = t;

                }

                // Remove the data from the bucket after merging

                bucketList.get(j).clear();

            }

        }

        return arr;

    }



    public static void main(String[] args) {

        int[] arr = {21.4.12.42.46.23.27.11.6.5.33.29.41.46.40.13.31};

        arr = radixSort(arr);

        System.out.print("After sorting array:");

        for (int i=0; i<arr.length; i++) {

            System.out.print(arr[i] + "，");

        }



    }



}

Copy the code

Time complexity analysis

O(n*k), where k is the number of buckets

Spatial complexity analysis

O(n+k), where k is the number of buckets

Stability analysis

Stability.

Suitable conditions

It is necessary to divide independent “bits” for comparison, and there is a progressive relationship between the bits. If the high point of “A” data is larger than that of “B” data, the remaining low points need not be compared. In addition, the data range of each bit should not be too large, so that the linear sorting algorithm can be used to sort, otherwise, the time complexity of radix sort cannot be O(n).

Welcome to like to share in the look, pay attention to the public number “Forrest Gump code road” to see more content, there are problems can add my wechat private I correct, each major platform will also be synchronized but some typesetting may not be the same ~

Resources: Geek Algorithm Bootcamp, Data structures and the Beauty of algorithms