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);
}
}

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.

3
Contributors
3
Replies
15
Views
4 Years
Discussion Span
Last Post by JamesCherrill

why your code don't run ... how do you know it doesn't run?
does it compile? do you get a compile time exception? do you get a run time exception?

does it seem to do nothing? might be stuck in an infinite loop somewhere. did you debug your code?

also: it seems you don't have a main method in there. how did you expect it to run?

it's also bad practice and ill-adviced to give a method a constructor-like name.

Edited by stultuske

I do not get any run-time or a compile time exceptions. I do have a main method, I just didn't think it would be useful for solving this.

``````import java.util.*;

public class QuickSortTest
{
public static void main(String[] args)
{
QuickSort qs = new QuickSort();

int[] random = {28, 46, 2, 26, 11, 23, 9, 25, 39, 47, 29, 31, 10,
4, 40, 3, 42, 21, 6, 38, 22, 8, 41, 18, 27, 33, 45,
30, 1, 24, 36, 43, 14, 17, 49, 19, 44, 34, 5, 37,
32, 48, 16, 50, 35, 12, 15, 7, 20, 13};

qs.QuickSort(random, 0, random.length, true);
for(int i = 0; i < random.length; i++)
System.out.println(random[i]);
}
}
``````

That's a stupid amount of test data for code that isn't working yet.
Start with one two or three elements. Add some print statements to your code to see which loops/class are being executed with which values.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.