Radix Sort method works, but not sure if it’s correct



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

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


Source: stackoverflow