Please explain this code to me, especially the series of for loops at the bottom
ID: 3555959 • Letter: P
Question
Please explain this code to me, especially the series of for loops at the bottom i need to know exactly what each step is doing and why it it getting mod by 10
public static void radixsort( int[] a, int n)
{ //initialize variables
int i;
int digit = 1;
//new array of size 1000, stores temporary array
int[] b = new int[n+1];
//for loop to find the maximum number
for (i = 1; i < n; i++)
if (a[i] > a[0])//a[0] is the maximum number
a[0] = a[i];
//Loops until it equals zero, happens when all numbers have been sorted for each digit
while (a[0] / digit > 0)
{ //initialize new bucket array to sort numbers by the ith digit
int[] bucket = new int[n+1];
//series of for loops to handle the algorithm;
//the digits are sorted on the basis of the ith digit given by dig=10^(i-1)
for (i = 0; i < n; i++)
bucket[(a[i] / digit) % 10]++;
for (i = 1; i < a.length; i++)
bucket[i] += bucket[i - 1];//this handles the i-1 in the exponent
for (i = a.length - 1; i >= 0; i--)
b[--bucket[(a[i] / digit) % 10]] = a[i];
for (i = 0; i < a.length; i++)
a[i] = b[i];//brings temporary array into the array
//while a[i]=b[i] exponent equals exponent times 10, handles the end of algorithm
digit=digit*10;
}
}
Explanation / Answer
In Radix sort we sort we are sorting elements based on there position in the digits
The same approach is used here also
Let me give you a dry run of radix sort which will make it clear for you
Original, unsorted list:
170, 45, 75, 90, 802, 24, 2, 66
Sorting by least significant digit (1s place) gives: [*Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.]
170, 90, 802, 2, 24, 45, 75, 66
Sorting by next digit (10s place) gives: [*Notice that 802 again comes before 2 as 802 comes before 2 in the previous list.]
802, 2, 24, 45, 66, 170, 75, 90
Sorting by most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90, 170, 802
Hope this will make it clear for you and the code written is same as the above logic