java quick sort
create a method to test that your quicksort( int [ ] a ), insertion sort and removeDuplicates( int [ ] methods work sufficiently.
the code is below and it needs a method to test it
public class QuicksortTester {
public static void quicksort(Comparable[] a) {
quicksort(a, 0, a.length - 1);
}
static void quicksort(Comparable[] a, int low, int high) {
int CUTOFF = 10;
if (low + CUTOFF > high)
insertionSort(a, low, high);
else {
int middle = (low + high) / 2;
if (a[middle].compareTo(a[low]) <>
swapReferences(a, low, middle);
if (a[high].compareTo(a[low]) <>
swapReferences(a, low, high);
if (a[high].compareTo(a[middle]) <>
swapReferences(a, middle, high);
swapReferences(a, middle, high - 1);
Comparable pivot = a[high - 1];
int i, j;
for (i = low, j = high - 1;;) {
while (a[++i].compareTo(pivot) <>
;
while (pivot.compareTo(a[--j]) <>
;
if (i >= j)
break;
swapReferences(a, i, j);
}
swapReferences(a, i, high - 1);
quicksort(a, low, i - 1);
quicksort(a, i + 1, high);
}
}
public static final void swapReferences(Object[] a, int index1, int index2) {
Object tmp = a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
private static void insertionSort(Comparable[] a, int low, int high) {
for (int p = low + 1; p <= high;="" p++)="">
Comparable tmp = a[p];
int j;
for (j = p; j > low && tmp.compareTo(a[j - 1]) < 0;="">
a[j] = a[j - 1];
a[j] = tmp;
}
}
static int removeDuplicates(int arr[], int n)
{
// Return, if array is empty
// or contains a single element
if (n==0 || n==1)
return n;
int[] temp = new int[n];
// Start traversing elements
int j = 0;
for (int i=0; i
// If current element is not equal
// to next element then store that
// current element
if (arr[i] != arr[i+1])
temp[j++] = arr[i];
// Store the last element as whether
// it is unique or repeated, it hasn't
// stored previously
temp[j++] = arr[n-1];
// Modify original array
for (int i=0; i
arr[i] = temp[i];
return j;
}
}