I am attempting to initialize an int[] array of 10 random numbers. Then choose a pivot value from the array. I then place this value in the first position of the array. Then call quicksort on the array, which will call a partition method. This method returns the final index of the pivot. Then quicksort is recursively called on both pieces of the array.
My partition method works, at least for the first call. But somewhere there is a mistake, and the final array ends up only partially sorted. I have added lots of print statements to make it easier to debug, but I cant figure it out. Any idea? And occasionally I get a arrayOutOfBound exception, but it is a random event and I think it has something to do with choosePivot.
import java.io.IOException;
import java.util.*;
public class test {
public static void main (String[] args) throws IOException{
//create inital random array, then print it
int[] myarray=randomArray(10);
System.out.println("original arrray:");
for (int i=0; i<myarray.length; i++)
System.out.print(myarray[i]+" ");
System.out.println("");
//move the pivot to the first position, then print again
swap(myarray, 0, choosePivot(myarray, 0, 9));
System.out.println("Swapped arrray:");
for (int i=0; i<myarray.length; i++)
System.out.print(myarray[i]+" ");
System.out.println("");
//call quicksort on full array
QuickSort(myarray, 0, 9);
//final array prints here
System.out.println("final arrray:");
for (int i=0; i<myarray.length; i++)
System.out.print(myarray[i]+" ");
System.out.println("");
}
public static void QuickSort(int[] array, int left, int right){
if (right-left <= 1)
return;
if (right>left){
int index=partition(array, left, right);
QuickSort(array, left, index-1);
QuickSort(array, index+1, right);
}
}
public static int partition(int[] array, int left, int right){
int i = left+1, j = right;
//start from each end of the array checking values.
//compares values to array[0] which holds the pivot.
//swap them as necessary
while (i<=j){
while (array[i]<array[left]){
i++;
}
while (array[j]>array[left]){
j--;
}
if (i<=j){
swap (array, i, j);
i++;
j--;
}
}
//i and j crossed, so move the pivot into it's proper spot.
if (i>j) {
swap (array, 0, j);
//prints parted array each interation, and index of pivot
System.out.println("Parted array:");
for (int k=left; k<=right; k++)
System.out.print(array[k]+" ");
System.out.println("j="+j);
//the pivot must be chosen and moved to first position again before quicksort
swap (array, left, choosePivot(array, left, j-1));
swap (array, j+1, choosePivot(array, j+1, right));
}
//prints array that will be used in recursive call
System.out.println("calling this array, all elements before j belong to first sub array. all elements after j are in second subarray:");
for (int k=left; k<=right; k++)
System.out.print(array[k]+" ");
System.out.println("j="+j);
return j;
}
//ARRAY INDEX SWAP
//simple array index swap method
public static void swap(int[] intArray, int dex1, int dex2) {
int temp = intArray[dex1];
intArray[dex1] = intArray[dex2];
intArray[dex2] = temp;
}
//RANDOM ARRAY
//method to create random int array of size n.
public static int[] randomArray (int n) {
Random randNumGenerator = new Random();
int[] array = new int[n];
for (int i = 0; i<array.length; i++) {
array[i] = (randNumGenerator.nextInt(100));
}
return array;
}
//CHOOSE PIVOT
//compare the first, last, and middle elements of the array. Return the index of the median value of these three
//this is the pivot
public static int choosePivot (int[] array, int first, int last){
int mid = (first + last ) / 2;
if (array[first]>array[mid]&&array[mid]>array[last])
return mid;
if (array[mid]>array[first]&&array[first]>array[last])
return first;
if (array[mid]>array[last]&&array[last]>array[first])
return last;
if (array[first]<array[mid]&&array[mid]<array[last])
return mid;
if (array[mid]<array[first]&&array[first]<array[last])
return first;
if (array[mid]<array[last]&&array[last]<array[first])
return last;
if (array[first]==array[last] || array[first]==array[mid] || array[mid]==array[last])
return mid;
return -1;
}
}