**Radix Sort Implementation in Java**

Radix Sort is a fascinating algorithm that sorts elements based on individual digits, making it particularly useful for integers. In this blog post, we will explore the implementation of Radix Sort in Java, providing a detailed explanation and illustrative examples.

**Overview**

Radix Sort processes elements digit by digit, from the least significant digit (LSD) to the most significant digit (MSD) or vice versa. It’s a non-comparative sorting algorithm that exploits the structure of numeric data. Radix Sort is often employed when the range of possible values is known and small, allowing for efficient bucketing and sorting.

Here’s a step-by-step explanation of how Radix Sort works:

**Least Significant Digit (LSD) Radix Sort:**- The algorithm starts by sorting elements based on their least significant digit.
- After the first pass, the elements are partially sorted based on the rightmost digit.

**Intermediate Passes:**- Radix Sort continues with additional passes, each time sorting based on the next significant digit towards the most significant digit.
- The process iterates until the entire number or string is considered.

**Most Significant Digit (MSD) Radix Sort:**- The final pass considers the most significant digit, resulting in a fully sorted array.

**Bucketing or Counting Sort:**- At each pass, Radix Sort uses a stable sorting algorithm, often a variant of counting sort, to distribute elements into buckets based on the digit being considered.
- Elements within each bucket are then collected to form the sorted array.

**Complexity:**- Radix Sort has a time complexity of O(nk), where n is the number of elements and k is the maximum number of digits in the input.

**Stable Sorting:**- Radix Sort is inherently stable, meaning that the relative order of equal elements is preserved throughout the sorting process.

**Java Implementation**

Let’s delve into a Java implementation of Radix Sort:

```
import java.util.Arrays;
public class RadixSort{
public static void main(String[] args) {
int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("Original Array: " + Arrays.toString(array));
// Call the sort method to perform Radix Sort
sort(array);
System.out.println("Sorted Array: " + Arrays.toString(array));
}
public static void sort(int[] array) {
// Find the maximum number to determine the number of digits
int max = Arrays.stream(array).max().orElse(0);
int exp = 1;
while (max / exp > 0) {
countingSort(array, exp);
exp *= 10;
}
}
public static void countingSort(int[] array, int exp) {
int n = array.length;
int[] output = new int[n];
int[] count = new int[10];
// Initialize the counting array
Arrays.fill(count, 0);
// Count occurrences of each digit at the current place value
for (int i : array) {
count[(i / exp) % 10]++;
}
// Update the counting array to represent cumulative count
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build the output array using the counting array information
for (int i = n - 1; i >= 0; i--) {
output[count[(array[i] / exp) % 10] - 1] = array[i];
count[(array[i] / exp) % 10]--;
}
// Copy the sorted array back to the original array
System.arraycopy(output, 0, array, 0, n);
}
}
```

**Walkthrough of the Implementation**

**Main Radix Sort Method:**

- The
`sort`

method initiates the Radix Sort process by finding the maximum number and iterating through each digit place value.

**Counting Sort Method:**

- The
`countingSort`

method performs counting sort for each digit place value. - It counts occurrences, updates the counting array for cumulative counts, and builds the output array.

**Example**

Consider an example array: `{170, 45, 75, 90, 802, 24, 2, 66}`

.

**First Iteration (Least Significant Digit):**

- Sorting by the least significant digit (1’s place):
`{170, 90, 802, 2, 24, 45, 75, 66}`

.

**Second Iteration (Next Significant Digit):**

- Sorting by the next significant digit (10’s place):
`{802, 2, 24, 45, 66, 170, 75, 90}`

.

**Third Iteration (Most Significant Digit):**

- Sorting by the most significant digit (100’s place):
`{2, 24, 45, 66, 75, 90, 170, 802}`

.

**Output:**

```
Original Array: [170, 45, 75, 90, 802, 24, 2, 66]
Sorted Array: [2, 24, 45, 66, 75, 90, 170, 802]
```

**Complexity**

Complexity | Best Case | Average Case | Worst Case |
---|---|---|---|

Time Complexity | O(nk) | O(nk) | O(nk) |

Space Complexity | O(n + k) | O(n + k) | O(n + k) |

**Explanation:**

**Time Complexity:****Best Case: O(nk) –**Occurs when the number of digits (k) is small, and the elements are evenly distributed across buckets.**Average Case: O(nk) –**Remains the same as the best case since Radix Sort’s time complexity is dominated by the number of digits.**Worst Case: O(nk) –**Even in the worst case, Radix Sort maintains its linear time complexity, making it efficient for various scenarios.

**Space Complexity:**- O(n + k) – The space complexity is determined by the size of the input array (n) and the range of values (k). It includes the auxiliary space used for counting sort and creating buckets.

**Conclusion**

Radix Sort’s unique approach to sorting by digits provides efficiency, especially for integers. Understanding its implementation in Java opens the door to utilizing this algorithm in scenarios where its linear time complexity shines.

**Latest Posts:**

- Merging Two Sorted Arrays in JavaTitle: Merging Two Sorted Arrays in Java Merging two sorted arrays into a single array is a common operation in… Read more: Merging Two Sorted Arrays in Java
- Frequency of Elements in an ArrayTitle: Frequency of Elements in an Array Using Java Counting the frequency of elements in an array is a fundamental… Read more: Frequency of Elements in an Array
- Calculate the sum of diagonals in a matrixTitle: Calculate the sum of diagonals in a matrix In this blog post, we’ll delve into the world of matrices… Read more: Calculate the sum of diagonals in a matrix
- Binary Search in JavaBinary search is a powerful algorithm used to efficiently find a target value in a sorted array. In this blog… Read more: Binary Search in Java
- Removing Duplicate Elements in Array using JavaRemoving Duplicate Elements in Array using Java Arrays are fundamental in Java, but duplicate elements can clutter your data. In… Read more: Removing Duplicate Elements in Array using Java
- Transpose a 2D Array in JavaTitle: Transpose a 2D Array in Java In Java, transposing a 2D array involves converting its rows into columns and… Read more: Transpose a 2D Array in Java