Wednesday, October 22, 2014

3-Way-Quicksort with Improvements [Tukey's Ninther]

Improvements:

1. If the number of elements is less than 10, use insertion sort.
2. If the number of elements is more, swap the first element with mid element.
3. If the number of elements is even more, swap the first element of the subarray with the median of the three elements (lo, mid, hi).
4. If the number of elements is even more, swap the first element with (Tukey's Ninther).

Source:

```package ThreeWayQuickSort;

import java.util.Arrays;

public class ThreeWayQuicksort {

public static void qSort(int[] a){
qSorter(a, 0, a.length-1);
}

private static void qSorter(int[] a, int lo, int hi){

if(lo>=hi) return;

/*
If the sub array is of size 10 or less
it is better to use insertion sort instead
*/
if (hi - lo <= 10) {
InsertionSort.insertionSort(a, lo, hi);
return;
}

if(hi - lo <= 25) {
/*
If the sub array is small, we can just use the middle
element as the element to compare with
*/
swap(a, lo, (lo+hi)/2);
}else if(hi - lo <= 50){
/*
If the sub array is medium in size, we can use the median
of three elements lo, (mid), and hi and set it as the
element to compare with.
*/
int m = median(a, lo, (lo + hi) / 2, hi);
swap(a, m, lo);
}else{

//Tukey's ninther
int a1[] = new int[3];
int a2[] = new int[3];
int a3[] = new int[3];

int gap = (hi-lo+1)/9;
if(((hi-lo+1)+gap)%9<gap)gap++; //Tricky logic!

//System.out.println("Gap = "+gap);

//Indexes
int a1I = 0, a2I = 0, a3I = 0, arrayNo = 0;
for(int i=lo;arrayNo<9;i+=gap){
if(arrayNo < 3)      a1[a1I++] = i;
else if(arrayNo < 6) a2[a2I++] = i;
else                 a3[a3I++] = i;

arrayNo++;
}

/* Debug code
System.out.println("Median of "+Arrays.toString(a1));
System.out.println("Median of "+Arrays.toString(a2));
System.out.println("Median of "+Arrays.toString(a3));
*/

int median = median(a, median(a, a1[0], a1[1], a1[2]),
median(a, a2[0], a2[1], a2[2]),
median(a, a3[0], a3[1], a3[2]));
swap(a, median, lo);
//System.out.println("Ninther = "+a[lo]);
}

int lt = lo, gt = hi, i = lo;
int v = a[lo];

while(i<=gt){
if(a[i]<v){ swap(a, i++, lt++);}
else if(a[i]>v){swap(a, i, gt--);}
else i++;
//System.out.println(Arrays.toString(a));
}

qSorter(a, lo, lt-1);
qSorter(a, gt+1, hi);
}

public static int median(int[] x, int a, int b, int c) {
if (x[a] > x[b] && x[a] > x[c]) { if (x[b] > x[c]) return b; else return c; }
else if (x[b] > x[a] && x[b] > x[c]) { if (x[a] > x[c]) return a; else return c; }
else if (x[c] > x[a] && x[c] > x[b]) { if (x[a] > x[b]) return a; }
return b;
}

private static void swap(int[] array, int a, int b){
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}

public static void main(String[] args){
//Two arrays to test
//int array[] = {2,3,5,7,8,3,5,6,8,4,3,2,5,6,7,8};
int array[] = {2,3,4,1,5,6,7,8,9,10,11,2,3,4,5,2,3,14,19,20,23,22,1,4,3,2,5};
qSort(array);
System.out.println(Arrays.toString(array));
}
}

class InsertionSort {

public static void insertionSort(int[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; ++i) {
int j = i;
while (a[j] < a[j - 1]) {
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
if (--j == 0) {
break;
}
}
}
}
}```

Output for test input data:

[1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 7, 8, 9, 10, 11, 14, 19, 20, 22, 23]