Please help. I wrote a quicksort with a median of either 3 or 5 to be the pivot and I can not figure out, for the life of me, why my code won't run. If the boolean isMedOf3 is true, then the partition uses a median of 3 to choose pivot else it uses a median of 5. I am stuck in infinite loop hell.
Here is my quicksort
import java.util.*;
public class QuickSort
{
static Random gen = new Random();
public void QuickSort(int[] unsortedArray, int first, int n, boolean isMedOf3)
{
int pivotIndex;
int n1, n2;
if(n > 1)
{
pivotIndex = partition(unsortedArray, first, n, isMedOf3);
n1 = pivotIndex - first;
n2 = n - n1 - 1;
QuickSort(unsortedArray, first, n1, isMedOf3);
QuickSort(unsortedArray, pivotIndex + 1, n2, isMedOf3);
}
}
private static int partition(int[] theArray, int first, int n, boolean isMedOf3)
{
int median, pivot;
if(isMedOf3)
median = MedianOfThree(theArray);
else
median = MedianOfFive(theArray);
pivot = theArray[median];
int tooBigIndex = first;
int tooSmallIndex = first + n - 1;
while(tooBigIndex <= tooSmallIndex)
{
while(tooBigIndex < median && theArray[tooBigIndex] <= pivot)
tooBigIndex++;
while(theArray[tooSmallIndex] > pivot)
tooSmallIndex--;
if(tooBigIndex < tooSmallIndex)
swap(theArray, tooBigIndex, tooSmallIndex);
}
return tooSmallIndex;
}
private static void swap(int[] theArray, int up, int down)
{
int temp = theArray[up];
theArray[up] = theArray[down];
theArray[down] = temp;
}
private static int MedianOfThree(int[] a)
{
int one = gen.nextInt(a.length-1);
int two = gen.nextInt(a.length-1);
int three = gen.nextInt(a.length-1);
if((a[one] < a[two] || a[one] < a[three]) && (a[one] > a[two] || a[one] > a[three]))
return one;
else if((a[two] < a[one] || a[two] < a[three]) && (a[two] > a[one] || a[two] > a[three]))
return two;
else
return three;
}
private static int MedianOfFive(int[] a)
{
int one = gen.nextInt(a.length);
int two = gen.nextInt(a.length);
int three = gen.nextInt(a.length);
int four = gen.nextInt(a.length);
int five = gen.nextInt(a.length);
int[] temp = {a[one], a[two], a[three], a[four], a[five]};
Arrays.sort(temp);
if(temp[2] == a[one])
return one;
else if(temp[2] == a[two])
return two;
else if(temp[2] == a[three])
return three;
else if(temp[2] == a[four])
return four;
return five;
}
}
Thank You for helping.