Class Radix

java.lang.Object
topics.sorting.radix.Radix
All Implemented Interfaces:
SortingAlgorithm
public class Radix extends Object implements SortingAlgorithm

Radix Sort (LSD - Least Significant Digit)

A non-comparative integer sorting algorithm that groups keys by individual digits that share the same significant position and value. This implementation processes digits from the Least Significant Digit (units) to the Most Significant Digit using 10 Base-10 Queues (Buckets).

Algorithm Steps

  1. Identify the maximum value in the array to determine the max digit count (K).
  2. For each digit position (Units, Tens, Hundreds...), distribute the elements into 10 buckets based on their digit at that position.
  3. Re-collect the elements from the buckets back into the original array, preserving their stable order.
  4. Repeat for the next significant digit.

Complexity Analysis

  • Time Complexity: O(K × N) strictly in all cases, where N is the number of elements and K is the number of digits in the largest number. If K is small, it behaves almost linearly.
  • Space Complexity: O(N + Base) - Requires additional memory to store the elements inside the buckets (Queues).
  • Stability: Yes - It is strictly required to be stable for the digit-by-digit sorting logic to work correctly.
Author:
vicegd
See Also:
  • invalid reference 
    topics.sorting.SortingAlgorithm

  • Constructor Details

    • Radix

      public Radix()

  • Method Details

    • sort

      public void sort(int[] elements)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.