![Radix Sort [Java]](https://media.licdn.com/dms/image/v2/D5612AQFig2HsDkXS6g/article-cover_image-shrink_720_1280/article-cover_image-shrink_720_1280/0/1674138395290?e=2147483647&v=beta&t=z5Bndt2P2fVcDP2CZ5l4-oglyc0s3zn4lWLVT_hL_UA)
Radix Sort [Java]
Radix sort is an integer sorting algorithm that sorts data with integer keys by grouping the keys by the individual digits which share the same significant position and value. Radix sort works by sorting the elements in the list by the least significant digit and iteratively sorting by each more significant digit. It is a non-comparative sorting algorithm, which means it does not compare elements to determine their sort order. Radix sort is efficient for large data sets because it only makes one pass through the data, and it is a stable sort, meaning that elements with the same key maintain their relative order.
Code:
import java.lang.Math;
import java.util.*;
class Radix {
public static void main(String[] args) {
/* First, I've created 10 queues for storing
the sorted order of the numbers for each place
value and then to form a new order of values
for each pass, to finally get the sorted order
of the numbers. */
Queue<Integer> q0 = new LinkedList<Integer>();
Queue<Integer> q1 = new LinkedList<Integer>();
Queue<Integer> q2 = new LinkedList<Integer>();
Queue<Integer> q3 = new LinkedList<Integer>();
Queue<Integer> q4 = new LinkedList<Integer>();
Queue<Integer> q5 = new LinkedList<Integer>();
Queue<Integer> q6 = new LinkedList<Integer>();
Queue<Integer> q7 = new LinkedList<Integer>();
Queue<Integer> q8 = new LinkedList<Integer>();
Queue<Integer> q9 = new LinkedList<Integer>();
/* Getting user input for the number of values
to be sorted. */
System.out.println("Enter the number of values to be sorted: ");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
/* Getting the numbers to be sorted from the
user, and then storing it in an array using a
for loop. I've used this array to store the new
order of the numbers for each pass till we
finally get the sorted values of the number. */
System.out.println("Enter the values to be sorted: ");
int arr[] = new int[n];
for (int i = 0; i < n; i++){
Scanner cs = new Scanner(System.in);
arr[i] = cs.nextInt();
}
/* Finding the largest element (max) in the
array. */
int max = arr[0];
for (int i = 1; i < n; i++){
if (arr[i] > max){
max = arr[i];
}
}
/*Calculating the number of digits in max (c)
because we have to go through all the
significant places of all numbers. Therefore
the loop should go up to 'c' times. */
int c = 0;
while (max != 0){
max /= 10;
c++;
}
/* Declaring variables to be used later in the
code. */
int a, q, z = 0, Q0, Q1, Q2, Q3, Q4, Q5, Q6, Q7, Q8, Q9;
/* Loop to go through each significant place
one by one. */
for (int j = 0; j < c; j++){
/* Loop to go through each number one by
one. */
for (int k = 0; k < n; k++){
/* Finding the digit (a) in the
significant place of each number to be
sorted. */
a = arr[k];
a = a/((int)Math.pow(10,j));
a = a % 10;
/* Storing that number in a queue based
on that digit 'a' (i.e.), store that
number in queue 0 if 'a' is 0 or store
that number in queue 1 if 'a' is 1 and
so on.... */
if (a == 0){
q0.add(arr[k]);
}
if (a == 1){
q1.add(arr[k]);
}
if (a == 2){
q2.add(arr[k]);
}
if (a == 3){
q3.add(arr[k]);
}
if (a == 4){
q4.add(arr[k]);
}
if (a == 5){
q5.add(arr[k]);
}
if (a == 6){
q6.add(arr[k]);
}
if (a == 7){
q7.add(arr[k]);
}
if (a == 8){
q8.add(arr[k]);
}
if (a == 9){
q9.add(arr[k]);
}
}
/* Findig the size of each queue. */
Q0 = q0.size();
Q1 = q1.size();
Q2 = q2.size();
Q3 = q3.size();
Q4 = q4.size();
Q5 = q5.size();
Q6 = q6.size();
Q7 = q7.size();
Q8 = q8.size();
Q9 = q9.size();
/* Getting the values from those queues in
order, (i.e.) q0, q1, q2 and so on....
and then storing the new order in that same
array. */
for (q = 0; q < Q0; q++){
arr[z] = q0.remove();
z++;
}
for (q = 0; q < Q1; q++){
arr[z] = q1.remove();
z++;
}
for (q = 0; q < Q2; q++){
arr[z] = q2.remove();
z++;
}
for (q = 0; q < Q3; q++){
arr[z] = q3.remove();
z++;
}
for (q = 0; q < Q4; q++){
arr[z] = q4.remove();
z++;
}
for (q = 0; q < Q5; q++){
arr[z] = q5.remove();
z++;
}
for (q = 0; q < Q6; q++){
arr[z] = q6.remove();
z++;
}
for (q = 0; q < Q7; q++){
arr[z] = q7.remove();
z++;
}
for (q = 0; q < Q8; q++){
arr[z] = q8.remove();
z++;
}
for (q = 0; q < Q9; q++){
arr[z] = q9.remove();
z++;
}
z = 0;
/* Printing the new order for each pass. */
int r = j+1;
if (j < c-1){
System.out.println("Pass " + r + " sorted values: ");
for (int f = 0; f < n; f++){
System.out.print(arr[f] + " ");
}
System.out.println(" ");
}
}
/* Printing the final sorted order of the
numbers. */
System.out.println("Final sorted values: ");
for (int f = 0; f < n; f++){
System.out.print(arr[f] + " ");
}
}
}
The above code is an implementation of Radix sort in Java. Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping the keys by the individual digits which share the same significant position and value.
The code starts by creating 10 different queues, one for each digit (q0, q1, q2, ..., q9). It then prompts the user to enter the number of values to be sorted and the values themselves. It then finds the maximum value in the input array, and uses it to determine the number of digits in the largest number.
The main sorting algorithm is in the nested for-loop, starting at line 49. The outer for-loop runs for the number of digits in the largest number, and the inner for-loop runs for the number of values to be sorted. In each iteration, the code takes the current value from the input array, divides it by 10 raised to the current digit place (jth place) and finds the remainder when divided by 10 to get the current digit. Then it adds the current value to the queue corresponding to the current digit (q0, q1, q2, etc.).
The next set of for-loops starting at line 67, empties the queues and adds the values to the original array in order of the digits.
Finally, the sorted array is printed on the console.
This implementation of Radix sort is efficient for large data sets because it only makes one pass through the data, and it is a stable sort, meaning that elements with the same key maintain their relative order.
Sample Output:
Enter the number of values to be sorted:
8
Enter the values to be sorted:
170
45
75
90
802
24
2
66
Pass 1 sorted values:
170 90 802 2 24 45 75 66
Pass 2 sorted values:
802 2 24 45 66 170 75 90
Final sorted values:
2 24 45 66 75 90 170 802
Excellent
Amazing Vifert Daniel. Keep up the good work. Looking forward to see more thoughts/solutions from you.
Interesting..
Way to go, Vifert Daniel! Keep up the good work. #happylearning #javaprogramming