Is this how radix sort works? I tried it off the definition I know, works well and quick
import java.util.*;
import java.util.Arrays;
public class Radix {
static int [] Unsorted = new int [1000000];
ArrayList<Integer>[] Radix = new ArrayList[1000000];
ArrayList<Integer>[] Radix2 = new ArrayList[1000000];
ArrayList<Integer>[] Radix3 = new ArrayList[1000000];
ArrayList<Integer>[] Radix4 = new ArrayList[1000000];
ArrayList<Integer>[] Radix5 = new ArrayList[1000000];
public void setLists(){
for(int i = 0; i < Unsorted.length; i++){
Unsorted[i] = (int) ((Math.random() * 90000) + 10000);
Radix[i] = new ArrayList<>();
Radix2[i] = new ArrayList<>();
Radix3[i] = new ArrayList<>();
Radix4[i] = new ArrayList<>();
Radix5[i] = new ArrayList<>();
}
}
public void Radix(ArrayList<Integer>[] Radixes, int division){
for(int i = 0; i < Unsorted.length; i++){
int temp = (Unsorted[i] / division) % 10;
Radixes[temp].add(Unsorted[i]);
}
this.set(Radixes);
}
public void set(ArrayList<Integer>[] Radixes){
int count = 0;
for (int i = 0; i < Unsorted.length; i++) {
for (int j = 0; j < Radixes[i].size(); j++) {
Unsorted[count] = Radixes[i].get(j);
count++;
}
}
}
public void RadixSort(){
Radix(Radix, 1);
Radix(Radix2, 10);
Radix(Radix3, 100);
Radix(Radix4, 1000);
Radix(Radix5, 10000);
}
I know you’re supposed to repeat it how many ever times the length of the largest number is, but I already know all the numbers will be of length 5
Advertisement
Answer
This code seems to work, but do you realize that you are creating 5 million ArrayList objects? How could that possibly be necessary? That’s the biggest problem I see here. You only need 10 such lists, one for each digit 0-9. You don’t even need 10 per radix position, as you can reuse the same list for each position.
I also renamed your identifiers that had uppercase first letters when they should have lowercase. Only your class name should be an uppercase word.
Here’s your code with these two changes made, where an array of 10 lists is created on the fly for processing each radix position:
With these changes, I get the same sort of result, but without the gigantic amount of wasted memory of the initial version:
public class Radix {
static int[] unsorted = new int[1000000];
public void setLists() {
for (int i = 0; i < unsorted.length; i++)
unsorted[i] = (int) ((Math.random() * 90000) + 10000);
}
public void radix(int division) {
ArrayList<Integer>[] radixLists = new ArrayList[10];
for (int i = 0 ; i < radixLists.length ; i++)
radixLists[i] = new ArrayList<>();
for (int i = 0; i < unsorted.length; i++) {
int temp = (unsorted[i] / division) % 10;
radixLists[temp].add(unsorted[i]);
}
this.set(radixLists);
}
public void set(ArrayList<Integer>[] radixLists) {
int count = 0;
for (int i = 0; i < radixLists.length; i++) {
for (int j = 0; j < radixLists[i].size(); j++) {
unsorted[count] = radixLists[i].get(j);
count++;
}
}
}
public void radixSort() {
radix(1);
radix(10);
radix(100);
radix(1000);
radix(10000);
}
public static void main(String[] args) {
Radix test = new Radix();
test.setLists();
test.radixSort();
for (int i = 0; i < unsorted.length; i++)
System.out.println(unsorted[i]);
}
}
Result:
10000 10000 10000 10000 10000 10000 10000 10000 10001 10001 10001 10001 10002 10002 ... 99997 99997 99998 99998 99998 99998 99998 99998 99998 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999