Not running to completion

[Vincent Jenkins]

I'm having an issue with quicksort

Here is my main program code

public class TestProgram {
    public static void main(String args[]) {
        printTestSort();
        printCounts(10);
    }

    public static void printCounts(int runs) {
        for(int rC = 0;rC < runs;rC++){
            int inputSize = 100 * (rC + 1);
            Car[] selection = new Car[inputSize];
            Car[] insertion; // = new Car[inputSize];
            Car[] quick; // = new Car[inputSize];
            generateRand rand = new generateRand();
            selSort sS = new selSort();
            insSort iS = new insSort();
            qSort qS = new qSort();
            int[] selCounts = new int[3]; //Create array for selection counters
            int[] insCounts = new int[3]; //Create array for insertion counters
            int[] qCounts = new int[3]; //Create array for quick counters

            rand.generate(selection, inputSize);
            insertion = selection.clone();
            quick = selection.clone();

            selCounts = sS.selectionSort(selection);
            insCounts = iS.insertionSort(insertion);
            qS.quickSort(quick, 0, inputSize - 1);
            qCounts = qS.getCounts();

            System.out.println("Run #" + (rC + 1));
            System.out.println("Input Size: " + inputSize);
            System.out.println();

            System.out.println("Selection Sort:");
            System.out.println("Assignment Count - " + selCounts[0]);
            System.out.println("Comparison Count - " + selCounts[1]);
            System.out.println("Total Count - " + selCounts[2]);
            System.out.println();

            System.out.println("Insertion Sort:");
            System.out.println("Assignment Count - " + insCounts[0]);
            System.out.println("Comparison Count - " + insCounts[1]);
            System.out.println("Total Count - " + insCounts[2]);
            System.out.println();

            System.out.println("Quick Sort:");
            System.out.println("Assignment Count - " + qCounts[0]);
            System.out.println("Comparison Count - " + qCounts[1]);
            System.out.println("Total Count - " + qCounts[2]);
            System.out.println();
        }
    }
}

And here is the qsort implementation

public class qSort {
    private int aCount = 0, cCount = 0;

    public void quickSort(Car[] array, int left, int right)
    {
        if (left < right)
        {
            int pivot = findPivot(array, left, right);
            quickSort(array, left, pivot-1);
            quickSort(array, pivot+1, right);
        }
    }

    private int findPivot(Car[] array, int left, int right)
    {
        int first = left++;
        while (left <= right)
        {
            while (left <= right && array[first].compareTo(array[left]) > 0) {
                cCount++;
                left++;
            }
            while (left <= right && array[first].compareTo(array[right]) < 0) {
                cCount++;
                right--;
            }
            cCount += 2;
            if (left < right)
                swap(array, left++, right--);
        }
        swap(array, first, right);
        return right;
    }

    private void swap(Car[] array, int i, int j) {
        aCount += 3;
        Car temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public int[] getCounts() {
        int[] counts = {aCount, cCount, aCount + cCount};
        return counts;
    }
}

Also here is the Car class just for sake of completeness

public class Car implements Comparable<Car> {
    private int miles;

    public int compareTo(Car c) {
        return Integer.compare(this.miles, c.miles);
    }

    public void setMiles(int m) {
        miles = m;
    }

    public int getMiles() {
        return miles;
    }
}

The implementation will not accept the tests when using input sizes of 100, 200, 300, etc to 1000 but when I change it to 10, 20, 30, to 100 it works just fine. The 100 - 1000 example will only run like 5 runs before it stops, making it to about 500 input size. Is this just a problem with the recursive nature of qsort mixed with a user defined class or is this a problem with my actual code? Would it solve the problem to change it to an array of integers instead?

[Mohamed Sanaulla]

I guess its taking time to complete. May be you need to debug to see if its going into the algorithmic implementation. Also Quicksort takes O(n^2) time in its worst case and O(nlogn) in its average case. So you can calculate approximate time taken for the sorting based on input size - n

[Vincent Jenkins]

Mohamed Sanaulla wrote:I guess its taking time to complete. May be you need to debug to see if its going into the algorithmic implementation. Also Quicksort takes O(n^2) time in its worst case and O(nlogn) in its average case. So you can calculate approximate time taken for the sorting based on input size - n

Is it really just a matter of time? I feel like there's more issues because my CPU usage increases to nearly 100% on run. Unfortunately I have to come up with the counts for each of the types of operations so that I can graph it on a chart for class

[Vincent Jenkins]

Vincent Jenkins wrote:

Mohamed Sanaulla wrote:I guess its taking time to complete. May be you need to debug to see if its going into the algorithmic implementation. Also Quicksort takes O(n^2) time in its worst case and O(nlogn) in its average case. So you can calculate approximate time taken for the sorting based on input size - n

Is it really just a matter of time? I feel like there's more issues because my CPU usage increases to nearly 100% on run. Unfortunately I have to come up with the counts for each of the types of operations so that I can graph it on a chart for class

Ya... As I let it go nothing else happens. It just stays there forever. If I run it, it will run to like run 5 instantly and just stop. Then the next run it'll get to 7 and hang. Then 4. Then 8. It's just random where it stops. I feel as if there's a case that's forcing it to recurse forever but then that wouldn't make sense because wouldn't the stack overflow? If that's the case how would I see that it's overflowing?

[Carey Brown]

Put a print statement before line 19 in qSort().

[Vincent Jenkins]

Carey Brown wrote:Put a print statement before line 19 in qSort().

Did that and it generates about 60 prints before it stops after Run #1

[Carey Brown]

Vincent Jenkins wrote:

Carey Brown wrote:Put a print statement before line 19 in qSort().

Did that and it generates about 60 prints before it stops after Run #1

System.out.println( left + " <= " + right );

It all depends on the random data values - run it over and over until you see it hang.