As homework I had to implement many sorting algorithms including radix sort in Java. The task is to sort double
s in the range [0-1) that are rounded to the 10th decimal point.
I thought of 2 ways on doing radix sort, one using counting sort and another one using buckets. They both work but they are extremely slow compared to quick sort. On average quick sort takes 0.068 seconds on a 800,000 doubles array, and both radix sorts are around 0.36 second. Any suggestions on how I can optimize any of the algorithms?
Using counting sort:
public class RadixSort implements Sorter {
private static final long BIG_NUM = (long) Math.pow(10, 10);
@Override
public void sort(double[] ar) {
Container[] containers = new Container[ar.length];
for (int i = 0; i < ar.length; i++) {
containers[i] = new Container(ar[i]);
}
for (long j = BIG_NUM; j >= 10; j = j / 10) {
for (int i = 0; i < ar.length; i++) {
double temp = containers[i].source * j;
if (j != BIG_NUM) {
temp = Math.floor(temp);
}
long temp2 = (long) (temp % 10) + 1;
containers[i].forCountingSort = temp2;
}
containers = countingSort(containers, 10);
}
for (int i = 0; i < ar.length; i++) {
ar[i] = containers[i].source;
}
}
private Container[] createOutput(Container[] org) {
Container[] output = new Container[org.length];
for (int i = 0; i < org.length; i++) {
output[i] = new Container();
}
return output;
}
/**
* @param containers array of container objects.
* @param maxVal max value for the contingsort range;
* @return new Container[] array partly sorted with Countingsort.
*/
public Container[] countingSort(Container[] containers, int maxVal) {
int[] c = new int[maxVal];
Container[] b = createOutput(containers);
for (int j = 0; j < containers.length; j++) {
if (containers[j].forCountingSort != 0)
c[(int) containers[j].forCountingSort - 1]++;
}
for (int j = 1; j < c.length; j++) {
c[j] += c[j - 1];
}
for (int j = containers.length - 1; j >= 0; j--) {
if (containers[j].forCountingSort != 0) {
b[c[(int) containers[j].forCountingSort - 1] - 1].forCountingSort = containers[j].forCountingSort;
b[c[(int) containers[j].forCountingSort - 1] - 1].source = containers[j].source;
c[(int) containers[j].forCountingSort - 1]--;
}
}
return b;
}
/*
Object to keep track of the original double while using counting sort;
*/
public static class Container {
long forCountingSort;
double source;
public Container(double source) {
this.source = source;
}
@Override
public String toString() {
return "source: " + source + "int: " + forCountingSort;
}
public Container() {
}
}
}
Using buckets:
public class newRadixSort implements Sorter {
private static final long BIG_NUM = (long) Math.pow(10, 10);
private ArrayList<Double>[] buckets = getBuckets();
@Override
public void sort(double[] ar) {
/* iterates over the array 10*n times,
each iteration in the inside loop it puts the double int a bucket according
to it's corresponding digit.
*/
for (long j = BIG_NUM; j >= 10; j = j / 10) {
for (int i = 0; i < ar.length; i++) {
int index = (int) ((ar[i] * j) % 10);
buckets[index].add(ar[i]);
}
/*
merges all the bucket's into the output array
and empty the buckets for reuse
*/
for (int n = 0; n < ar.length; n++) {
for (int k = 0; k < buckets.length; k++) {
for (int h = 0; h < buckets[k].size(); h++) {
ar[n] = buckets[k].get(h);
n++;
}
buckets[k] = new ArrayList<>();
}
}
}
}
}
/**
* creates 10 buckets for the sorting
*
* @return ArrayList<Double>[] with 10 buckets.
*/
public ArrayList<Double>[] getBuckets() {
ArrayList<Double>[] al = new ArrayList[10];
for (int i = 0; i < al.length; i++) {
al[i] = new ArrayList<>();
}
return al;
}
}