Table of content

Radix sort in Rust

If you know about Counting sort and Bucket sort , you should know that both sorts can break through the special sorting method that compares the sorting complexity $O(n log n) $ limit.

Radix sort is also a special integer sorting method , and the performance can also reach the breakthrough limit. The difference is that the first two are sorted by only one key value, while the Radix sort is sorted by multiple key values.

For example, to sort a group of integers ranging from 0 - 999, if sorted by Counting sort, you need to create an "array of 1000 elements" to calculate the number of occurrences of each integer;

If you use a Radix sort based on 10, Then only need to use the single digit, ten digit, and hundred digits as the key value to sort three times.

Usually, the Sorting subroutine of Radix sort will use Counting sort or Bucket sort, and the base 10 key-value range is only 0 - 9. This small range of integers is very suitable for Counting sort as a sorting subroutine, saving the configuration. int arr[1000]The time-space of the count array.

The basic features of Radix sort are as follows:
  • Integer sorting : integers are used as sorted key values.
  • Distributive sorting : Instead of pairwise comparisons, the key-value distribution is sorted. Linear execution time is available in specific situations.
  • Stability : Radix sort with LSD is a stable sorting method; through optimization, MSD can also be a stable sorting method.
Steps


The common Radix sort is sorted according to each digit of the integer. According to the order of the digits, there are two types:

  • Least significant digit (LSD) : Sorts from the lowest valid key value (the smallest number of bits to the largest).
  • Most significant digit (MSD) : Sorts from the most significant key value (maximum number of digits to small).
The simple LSD Radix sort steps are as follows:
  • LSD of each key : Get the minimum number of bits (LSD) for each data key.
  • Sorting subroutine : Sorts the data according to the size of the digit.
  • Repeating : Take the next valid digit and repeat step two to the maximum number of digits (MSD).

The steps for MSD Radix sort are similar, but the data key values are reversed.

  • MSD of each key : Get the maximum number of bits (MSD) for each data key.
  • Sorting subroutine : Sorts the data according to the size of the digit.
  • Repeating : Take the next valid digit and repeat step two until the minimum digit (LSD).

Since the MSD Radix sort sorts the maximum number of digits first, there will be a result of 8 > 126. This order is usually called Lexicographical order. Like a dictionary, the more the previous alphabet sorting weight, the more important the basic version of MSD Radix sort is. Stable ordering.

use crate::sorting::counting_sort;

/// Radix sort for sorting unsigned integers.

/// * `arr` - Collection of value to be sorted in place.

pub fn radix_sort(arr: &mut [i32]) { // 1. Choose 10 as our radix. let radix = 10; // 2. Started from least significant digit (rightmost). let mut digit = 1; // 3. Find the maximum value to determine break point of the loop. let max_value = arr // 3 .iter() .max() .unwrap_or(&0) .clone(); // 4. Sorting subroutine (use counting sort). while digit <= max_value { counting_sort(arr, 0, 9, |t| (t / digit % radix) as usize); digit *= radix; } }

#[cfg(test)]

mod base { use super::*; base_cases!(radix_sort); }

Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions