-
Notifications
You must be signed in to change notification settings - Fork 3
/
Main.java
53 lines (41 loc) · 1.6 KB
/
Main.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package com.mcodes;
public class Main {
public static void main(String[] args) {
int[] radixArray = {4725, 4586, 1330, 8792, 1594, 5729};
radixSort(radixArray, 10, 4);
for (int item : radixArray) {
System.out.println(item);
}
}
public static void radixSort(int[] input, int radix, int width) {
for (int i = 0; i < width; i++) {
radixSingleSort(input, i, radix);
}
}
public static void radixSingleSort(int[] input, int position, int radix) {
int numItems = input.length;
int[] countArray = new int[radix];
// How many values have a specific value at the position being looked at
for (int value : input) {
countArray[getDigit(position, value, radix)]++;
}
// Below are extra steps to make it a stable sort
// Adjust the count array
for (int j = 1; j < radix; j++) {
countArray[j] += countArray[j - 1];
}
int[] temp = new int[numItems];
// Write the values into a temporary array
for (int tempIndex = numItems - 1; tempIndex >= 0; tempIndex--) {
temp[--countArray[getDigit(position, input[tempIndex], radix)]] = input[tempIndex];
}
// Copy temp array back into input array
for (int tempIndex = 0; tempIndex < numItems; tempIndex++) {
input[tempIndex] = temp[tempIndex];
}
}
public static int getDigit(int position, int value, int radix) {
// Returns the digit for each position
return value / (int) Math.pow(radix, position) % radix;
}
}