Radix Sort

Radix Sort is a non-comparison-based sorting algorithm that sorts integers by grouping them by individual digits and sorting from least significant digit (LSD) to most significant digit (MSD). It has a time complexity of O(kn), where k is the number of digits in the largest number and n is the number of elements to be sorted.

Algorithm

The Radix Sort algorithm consists of the following steps:

1. Find the maximum element in the array to determine the number of digits in the largest number.
2. For each digit position, from the least significant digit to the most significant digit, perform a counting sort on the array.
3. Repeat step 2 for all digits, starting from the least significant digit to the most significant digit.

Example

To demonstrate the Radix Sort algorithm, consider the following array of integers:

1int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};

Step 1: Find the maximum element

The maximum element in the array is 802, so the number of digits in the largest number is 3.

Step 2: Perform counting sort on each digit position

• For the least significant digit (1's place):

  • Counting sort: [170, 90, 802, 2, 24, 45, 75, 66]

• For the tens place:

  • Counting sort: [802, 2, 24, 45, 66, 170, 75, 90]

• For the hundreds place:

  • Counting sort: [2, 24, 45, 66, 75, 90, 170, 802]

Step 3: The array is now sorted

The sorted array is [2, 24, 45, 66, 75, 90, 170, 802].

Java Implementation

Here is a Java implementation of the Radix Sort algorithm:

1${code}

xxxxxxxxxx

}

class Main {

  public static void main(String[] args) {

    int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};

    radixSort(arr);

    System.out.println("Sorted Array:");

    for (int i : arr) {

      System.out.print(i + " ");

    }

  }

​

  public static void radixSort(int[] arr) {

    int max = getMax(arr);

​

    for (int exp = 1; max / exp > 0; exp *= 10) {

      countSort(arr, exp);

    }

  }

​

  public static int getMax(int[] arr) {

    int max = arr[0];

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

      if (arr[i] > max) {

        max = arr[i];

      }

    }

    return max;

  }

​

  public static void countSort(int[] arr, int exp) {