I created some improvement to QuickSort and decide to test it against Java Arrays.sort().
The results are fascinating:
On Java 6:
- My Time / System Time = 74 / 83 = 0.891566265060241
- My Time / System Time = 75 / 79 = 0.9493670886075949
- My Time / System Time = 75 / 84 = 0.8928571428571429
On Java 7:
- My Time / System Time = 115 / 70 = 1.6428571428571428
- My Time / System Time = 101 / 76 = 1.3289473684210527
- My Time / System Time = 102 / 61 = 1.6721311475409837
As you can see my algorithm performs better on Java 6, how ever it have a dramatic drop on Java 7 witch I don't understand. May be you can find the reason why?
Edit: How does my algorithm works:
- Step 1: Take 3 numbers, sort them, use the middle number as pivot
- Step 2: Take all the numbers bigger than pivot to the right and all the numbers smaller than pivot to the left, and place pivot in it's final position in the sorted array. This actually implemented in O(N).
- Step 3: Recursively repeat step 1 and 2 for left and right sides. When you rich sub array smaller than 12 elements use network sort to sort it.
My source code
public class QuickSort {
public static void sort(int[] source) {
int buffer[] = new int[source.length];
concatenate(source, buffer, 0, source.length);
}
private static void concatenate(int[] source, int[] buffer, int low, int high) {
int count = high - low;
int lowBuffer = low;
int highBuffer = high;
if (count < 2) {
return;
}
if (count < 12) {
networkSort(source, buffer, low, count);
return;
}
int pivotIndex = bestOfThree(source, low);
int value = source[pivotIndex];
for (int i = low; i < high; i++) {
if (i == pivotIndex) {
continue;
}
if (source[i] < value) {
buffer[lowBuffer] = source[i];
source[lowBuffer] = buffer[lowBuffer];
lowBuffer++;
}
else {
highBuffer--;
buffer[highBuffer] = source[i];
}
}
buffer[lowBuffer] = source[lowBuffer] = value;
for (int i = lowBuffer; i < high; i++) {
source[i] = buffer[i];
}
concatenate(source, buffer, lowBuffer + 1, high);
concatenate(source, buffer, low, lowBuffer);
}
private static int bestOfThree(int[] source, int low) {
int a = low;
int b = a + 1;
int c = a + 2;
int median = -1;
if (source[a] >= source[b] && source[a] >= source[c]) {
if (source[b] < source[c]) {
median = c;
}
else {
median = b;
}
}
else if (source[b] >= source[a] && source[b] >= source[c]) {
if (source[a] < source[c]) {
median = c;
}
else {
median = a;
}
}
else if (source[c] >= source[a] && source[c] >= source[b]) {
if (source[a] < source[b]) {
median = b;
}
else {
median = a;
}
}
return median;
}
private static int[][] networkSort = {
{ 0, 1 },
{ 1, 2, 0, 2, 0, 1 },
{ 0, 1, 2, 3, 0, 2, 1, 3, 1, 2 },
{ 0, 1, 3, 4, 2, 4, 2, 3, 1, 4, 0, 3, 0, 2, 1, 3, 1, 2 },
{ 1, 2, 4, 5, 0, 2, 3, 5, 0, 1, 3, 4, 2, 5, 0, 3, 1, 4, 2, 4, 1, 3, 2, 3 },
{ 1, 2, 3, 4, 5, 6, 0, 2, 3, 5, 4, 6, 0, 1, 4, 5, 2, 6, 0, 4, 1, 5, 0, 3, 2, 5, 1, 3, 2, 4, 2, 3 },
{ 0, 1, 2, 3, 4, 5, 6, 7, 0, 2, 1, 3, 4, 6, 5, 7, 1, 2, 5, 6, 0, 4, 3, 7, 1, 5, 2, 6, 1, 4, 3, 6, 2, 4, 3, 5, 3, 4 },
{ 0, 1, 3, 4, 6, 7, 1, 2, 4, 5, 7, 8, 0, 1, 3, 4, 6, 7, 2, 5, 0, 3, 1, 4, 5, 8, 3, 6, 4, 7, 2, 5, 0, 3, 1, 4, 5, 7, 2, 6, 1, 3, 4, 6, 2, 4, 5, 6, 2, 3 },
{ 4, 9, 3, 8, 2, 7, 1, 6, 0, 5, 1, 4, 6, 9, 0, 3, 5, 8, 0, 2, 3, 6, 7, 9, 0, 1, 2, 4, 5, 7, 8, 9, 1, 2, 4, 6, 7, 8, 3, 5, 2, 5, 6, 8, 1, 3, 4, 7, 2, 3, 6, 7, 3, 4, 5, 6, 4, 5 },
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 3, 5, 7, 0, 2, 4, 6, 8, 10, 1, 2, 5, 6, 9, 10, 0, 4, 3, 7, 1, 5, 6, 10, 4, 8, 5, 9, 2, 6, 0, 4, 3, 8, 1, 5, 6, 10, 2, 3, 8, 9, 1, 4, 7, 10, 3, 5, 6, 8, 2, 4, 7, 9, 5, 6, 3, 4, 7, 8 }
};
private static int tmp;
private static void networkSort(int[] source, int[] buffer, int low, int count) {
int[] networkData = networkSort[count - 2];
for (int i = 0; i < networkData.length; i += 2) {
int index1 = low + networkData[i];
int index2 = low + networkData[i + 1];
if (source[index1] > source[index2]) {
tmp = source[index1];
buffer[index1] = source[index1] = source[index2];
buffer[index2] = source[index2] = tmp;
}
}
}
}
Base testing class
public abstract class Test {
protected int[][] buffer;
private final Random random = new Random();
public int numberOfTests = 100;
public int maxValue = 1000;
public int numberOfItems = 100;
protected void createBuffer() {
buffer = new int[numberOfTests][];
for (int i = 0; i < numberOfTests; i++) {
int[] list = new int[numberOfItems];
addRandomNumbers(list);
buffer[i] = list;
}
}
protected void createBuffer(int...parametes) {
buffer = new int[1][];
buffer[0] = parametes;
}
protected void addRandomNumbers(int[] list) {
for (int i = 0; i < numberOfItems; i++) {
int value = random.nextInt(maxValue);
list[i] = value;
}
}
protected int[][] cloneBuffer() {
int[][] clonedBuffer = new int[numberOfTests][];
for(int i = 0; i < buffer.length; i++){
int[] clonedList = new int[buffer[i].length];
int[] list = buffer[i];
for (int j = 0; j < list.length; j++) {
int element = list[j];
clonedList[j] = element;
}
clonedBuffer[i] = clonedList;
}
return clonedBuffer;
}
public abstract void test();
}
Performance Test
public class PerformanceTest extends Test {
private final Timer timer = new Timer();
public void test() {
createBuffer();
timer.reset();
testSystem();
timeResoult("System");
timer.reset();
testMy();
timeResoult("My List");
}
public void test(int numberOfTests) {
long myTotalTime = 0;
long systemTotalTime = 0;
for (int i = 0; i < numberOfTests; i++) {
createBuffer();
timer.reset();
testSystem();
long systemTime = timeResoult();
systemTotalTime += systemTime;
timer.reset();
testMy();
long myTime = timeResoult();
myTotalTime += myTime;
System.out.println("My Time / System Time = " + myTime + " / " + systemTime + " = \t"
+ ((double) myTime / systemTime));
}
System.out.println("My Time / System Time = " + ((double) myTotalTime / systemTotalTime));
}
private long timeResoult() {
return timeResoult(null);
}
private long timeResoult(String source) {
long time = timer.check();
if (source != null) {
System.out.println(source + ">\tTime: " + time);
}
return time;
}
private void testMy() {
int[][] buffer = cloneBuffer();
for (int i = 0; i < numberOfTests; i++) {
int[] list = buffer[i];
QuickSort.sort(list);
}
}
private void testSystem() {
int[][] buffer = cloneBuffer();
for (int i = 0; i < numberOfTests; i++) {
int[] list = buffer[i];
Arrays.sort(list);
}
}
}
Main
public static void main(String[] args) {
PerformanceTest testBasics = new PerformanceTest();
testBasics.numberOfTests = 1000;
testBasics.numberOfItems = 1000;
testBasics.maxValue = 1000000;
testBasics.test(100);
}
