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.

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 2 Years Ago 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 article has been dead for over six months. Start a new discussion instead.