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 Summary

    Constructors
    Constructor
    Description
    Radix()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    sort(int[] elements)
    Sorts the elements in-place silently.
    void
    sort(int[] elements, boolean trace)
    Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Radix

      public Radix()

  • Method Details

    • sort

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

    • sort

      public void sort(int[] elements, boolean trace)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.
      trace - If true, logs the internal state during execution.