Radix sort

Abstract: Radix sort is a sort method based on “key word”, where the “key word” is each digit, the key is to understand the validity of the conclusion: low priority.

Focus on understanding the subprocess of radix sort: counting sort (for stability).

---

Introduction to Radix Sort

• Radix sort is a non – comparison sort method, it is multi – keyword sort method;
• In order to make the description of radix sort more intuitive, we only take the sorting task of non-negative integers as an example.
• In radix sort, the ones and tens digits of an integer are considered to be a keyword respectively.

There are two ways of sorting cardinality: Most significant Digital and Least Significant Digital. Common practice is low priority, high priority we only do a brief introduction, focusing on low priority.

---

High priority (not recommended)

The basic idea of radix sort (high priority)

The highest priority is more intuitive: first sort by the highest ascending order, then by the second highest order, and so on to the lowest order.

The implementation of this method uses the idea of “divide and conquer” recursive implementation, need to use recursive method to achieve, and the space complexity is large. In fact, you can start with the lowest order and work your way up to the highest. Not only is this the right thing to do, it’s easier to implement.

---

Low priority (recommended)

Let’s look at a concrete example of how low priority is sorted. For example: [329, 457, 657, 839, 436, 720, 355], uses the “low priority” algorithm of radix sort to execute the process.

• First do it in the ones placeA stable sort(Same numbers in the same order), get[720, 355, 436, 457, 657, 329, 839];
• And then we do it in the tens placeA stable sort(Same numbers in the same order), get[720, 329, 436, 839, 355, 457, 657];
• And then do it in the hundreds placeA stable sort(Same numbers in the same order), get[329, 355, 436, 457, 657, 720, 839].

Low priority effectiveness

When we compare two numbers, we always compare the highest digit first. The higher the order is, the higher the order is, the later the order is. In the case of the same high, the need to compare the lower high, and the lower high has been sorted in the previous order.

It is very important that every keyword-based sort must use stable sort, as you will see in the example above.

---

The code

Details: How to get values for each place.

• Erase the low position first;
• Take the ones place (mod 101010).

// Calculate the number of digits, first the ones place, then the tens place, then the hundreds place
int remainder = (arr[j] / divisor) % 10;
Copy the code

Complete code:

“Force buckle” problem 912

public class RadixSort {

    public void sort(int[] nums) {
        int len = nums.length;
        // Step 1: Find the largest number
        int max = nums[0];
        for (int i = 0; i < len; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            Nums [I] cannot be less than 0
            if (nums[i] < 0) {
                throw new IllegalArgumentException("This array is not suitable for counting sort"); }}// Step 2: Figure out how many digits the largest number has. This number determines how many times we need to look through the array
        int maxLen = getMaxLen(max);

        // Step 3: Use count sort on each trip
        int[] count = new int[10];
        int[] temp = new int[len];

        int divisor = 1;
        // For a few digits, the outer loop must be executed several times
        for (int i = 0; i < maxLen; i++) {
            // Count sort is used at each step to ensure that the sorting result is stable. This step requires extra space to store the result set, so the result is stored in temp
            countingSort(nums, temp, divisor, len, count);

            System.arraycopy(temp, 0, nums, 0, len);
            divisor *= 10; }}/ * * * *@paramNums raw array *@paramTemp Is an auxiliary array used during counting sorts, this time with divisor keyword based sorting results stored here *@param divisor
     * @paramLen The length of the original array (redundant variables) *@paramCount Counts the array */
    private void countingSort(int[] nums, int[] temp, int divisor, int len, int[] count) {
        // The inner loop has to look through the array
        for (int j = 0; j < len; j++) {
            // Calculate the number of digits, first the ones place, then the tens place, then the hundreds place
            int remainder = (nums[j] / divisor) % 10;
            count[remainder]++;
        }

        for (int j = 1; j < 10; j++) {
            count[j] += count[j - 1];
        }

        for (int j = len - 1; j >= 0; j--) {
            int remainder = (nums[j] / divisor) % 10;
            int index = count[remainder] - 1;
            temp[index] = nums[j];
            count[remainder]--;
        }

        // Resets array count for next use
        for (int j = 0; j < 10; j++) {
            count[j] = 0; }}/** * gets the maximum number of digits of an integer **@param num
     * @return* /
    private int getMaxLen(int num) {
        int maxLen = 0;
        while (num > 0) {
            num /= 10;
            maxLen++;
        }
        returnmaxLen; }}Copy the code

Complexity analysis:

• Time complexity: O(KN)O(KN)O(KN) where NNN is the length of the input array and KKK is the number of keywords. Take the sorting task of non-negative integer array as an example, the maximum number of bits (KKK) need to look at the array several times;
• Space complexity: O(N+K)O(N +K)O(N +K), where KKK (the number of bits of a number) is usually much smaller than NNN (the length of the input array).

---

conclusion

Radix sort is stable sort (requiring subprocesses to be stable sort as well) and occurs out of place. We continue to refine the table:

	Worst time complexity	Average time complexity	Best time complexity	Extra space complexity	The stability of	Whether to sort in place
Selection sort	$O(N^2)$	$O(N^2)$	$O(N^2)$	$O(1)$	unstable	In situ sorting
Bubble sort	$O(N^2)$	$O(N^2)$	$O(N)$	$O(1)$	stable	In situ sorting
Insertion sort	$O(N^2)$	$O(N^2)$	$O(N)$	$O(1)$	stable	In situ sorting
Hill sorting	$O(N^2)$	$O (n ^ 1.25} {) \ sim O (n ^ 1.6 1.25} {)$	(No related studies)	$O(1)$	unstable	In situ sorting
Merge sort	$O(N \log N)$	$O(N \log N)$	$O(N \log N)$	$O(N)$	stable	Out-of-place sorting
Quick sort	$O(N^2)$	$O(N \log N)$	$O(N \log N)$	$O(\log N)$	unstable	In situ sorting
Count sorting	$O(N + K)$	$O(N + K)$	$O(N + K)$	$O(N + K)$	stable	Out-of-place sorting
Radix sort	$O(KN)$	$O(KN)$	$O(N^2)$	$O(K + N)$	stable	Out-of-place sorting

Description:

• In counting sort, NNN is the length of the array, KKK is the maximum value of the array (assuming the minimum value of the array is 000);
• In radix sort, NNN is the length of the array and KKK is the largest number of bits (the number of keywords).

---

practice

1. Question 912: Sort an array (medium).

Note: Note the range of values given for the input array elements.

---

This section focuses on understanding that “radix sort” is a multi-keyword sorting method, and using concrete examples to understand that “low priority” is justified by stable sorting on each digit. In the next video, we’re going to do bucket sorting. Thank you.