I have been working on different variations of the Radix Sort. At first I used chaining, which was really slow. Then I moved onto using a count sort while using val % (10 * pass), and most recently turning it into the respective bytes and count sorting those, which allows me to sort by negative values also.
I wanted to try it with multithreading, and can only get it to work about half the time. I was wondering if someone can help look at my code, and see where I'm going wrong with the threading. I have each thread count sort each byte. Thanks:
public class radixSort {
public int[] array;
public int arraySize, arrayRange;
public radixSort (int[] array, int size, int range) {
this.array = array;
this.arraySize = size;
this.arrayRange = range;
}
public int[] RadixSort() {
Thread[] threads = new Thread[4];
for (int i=0;i<4;i++)
threads[i] = new Thread(new Radix(arraySize, i));
for (int i=0;i<4;i++)
threads[i].start();
for (int i=0;i<4;i++)
try {
threads[i].join();
} catch (InterruptedException e) {
e.printStackTrace();
}
return array;
}
class Radix implements Runnable {
private int pass, size;
private int[] tempArray, freqArray;
public Radix(int size, int pass) {
this.pass = pass;
this.size = size;
this.tempArray = new int[size];
this.freqArray = new int[256];
}
public void run() {
int temp, i, j;
synchronized(array) {
for (i=0;i<size;i++) {
if (array[i] <= 0) temp = array[i] ^ 0x80000000;
else temp = array[i] ^ ((array[i] >> 31) | 0x80000000);
j = temp >> (pass << 3) & 0xFF;
freqArray[j]++;
}
for (i=1;i<256;i++)
freqArray[i] += freqArray[i-1];
for (i=size-1;i>=0;i--) {
if (array[i] <= 0) temp = array[i] ^ 0x80000000;
else temp = array[i] ^ ((array[i] >> 31) | 0x80000000);
j = temp >> (pass << 3) & 0xFF;
tempArray[--freqArray[j]] = array[i];
}
for (i=0;i<size;i++)
array[i] = tempArray[i];
}
}
}
}
