For this assignment I'm supposed to test my quicksort class using a variety of different pivots and a variety of ArrayLists in different arrangements. The class works fine with a random pivot, or a median of three pivot, but when using the first element as my pivot, I get a stack overflow error on both tests with a nearly sorted list and a list in descending order. My test sizes are fairly large, starting at 10,000 and going to 100,000, but only these two tests give me a stack overflow error and I'm not sure why. Here's the code for my Quicksort class:

public class QuickSorter<E extends Comparable<? super E>> implements Sorter<E> {

    private PivotChooser<E> chooser;

    /**
     * QuickSorter Constructor
     * 
     * @param chooser PivotChooser object used to determine how the pivot is chosen
     */
    public QuickSorter(PivotChooser<E> chooser) {
        this.chooser = chooser;
    }

    /**
     * Quicksort Driver method. Ensures the list isn't empty before calling the
     * recursive Quicksort method
     */
    public void sort(ArrayList<E> list) {

        if (list.size() < 0)
            throw new IllegalArgumentException();

        int leftIndex = 0;
        int rightIndex = list.size() - 1;

        recursiveSort(list, leftIndex, rightIndex);

    }

    /**
     * Recursive Quicksort method
     * 
     * @param list       Unsorted, Generic list
     * @param leftIndex  The lowest index of the partition
     * @param rightIndex The highest index of the partition
     */
    private void recursiveSort(ArrayList<E> list, int leftIndex, int rightIndex) {
        
        if (leftIndex < rightIndex) {
            int partition = partition(list, leftIndex, rightIndex);

            recursiveSort(list, leftIndex, partition - 1);
            recursiveSort(list, partition + 1, rightIndex); //This is the line that seems to cause the Stack Overflow error
        }

    }

    /**
     * Quicksort Partition method that grabs the pivot from the chooser object and
     * sorts the partition
     * 
     * @param list       Unsorted, Generic list
     * @param leftIndex  The lowest index of the partition
     * @param rightIndex The highest index of the partition
     * @return The current pivot index
     */
    private int partition(ArrayList<E> list, int low, int high) {
        int pivotIndex = chooser.getPivotIndex(list, low, high);
        E pivot = list.get(pivotIndex);
        swap(list, pivotIndex, high);

        int i = low;

        for (int j = low; j <= high; j++) {
            E temp = list.get(j);
            if ((temppareTo(pivot) < 0)) {
                swap(list, i, j);
                i++;
            }
        }

        swap(list, i, high);

        return i;
    }


    /**
     * Swaps two given elements in a given ArrayList
     * 
     * @param list   The given ArrayList
     * @param index1 The first element index to swap
     * @param index2 The second element index to swap
     */
    private void swap(ArrayList<E> list, int index1, int index2) {
        E temp = list.get(index1);
        list.set(index1, list.get(index2));
        list.set(index2, temp);
    }

public class FirstPivotChooser<E extends Comparable<? super E>> implements PivotChooser<E> {

    /**
     * Returns the left-most index in a given ArrayList
     * 
     * @param list       The generic ArrayList
     * @param leftIndex  The left-most or lowest index in the list
     * @param rightIndex The right-most or highest index in the list
     * @return The left-most index
     */
    public int getPivotIndex(ArrayList<E> list, int leftIndex, int rightIndex) {

        return leftIndex;

    }
}

For this assignment I'm supposed to test my quicksort class using a variety of different pivots and a variety of ArrayLists in different arrangements. The class works fine with a random pivot, or a median of three pivot, but when using the first element as my pivot, I get a stack overflow error on both tests with a nearly sorted list and a list in descending order. My test sizes are fairly large, starting at 10,000 and going to 100,000, but only these two tests give me a stack overflow error and I'm not sure why. Here's the code for my Quicksort class:

public class QuickSorter<E extends Comparable<? super E>> implements Sorter<E> {

    private PivotChooser<E> chooser;

    /**
     * QuickSorter Constructor
     * 
     * @param chooser PivotChooser object used to determine how the pivot is chosen
     */
    public QuickSorter(PivotChooser<E> chooser) {
        this.chooser = chooser;
    }

    /**
     * Quicksort Driver method. Ensures the list isn't empty before calling the
     * recursive Quicksort method
     */
    public void sort(ArrayList<E> list) {

        if (list.size() < 0)
            throw new IllegalArgumentException();

        int leftIndex = 0;
        int rightIndex = list.size() - 1;

        recursiveSort(list, leftIndex, rightIndex);

    }

    /**
     * Recursive Quicksort method
     * 
     * @param list       Unsorted, Generic list
     * @param leftIndex  The lowest index of the partition
     * @param rightIndex The highest index of the partition
     */
    private void recursiveSort(ArrayList<E> list, int leftIndex, int rightIndex) {
        
        if (leftIndex < rightIndex) {
            int partition = partition(list, leftIndex, rightIndex);

            recursiveSort(list, leftIndex, partition - 1);
            recursiveSort(list, partition + 1, rightIndex); //This is the line that seems to cause the Stack Overflow error
        }

    }

    /**
     * Quicksort Partition method that grabs the pivot from the chooser object and
     * sorts the partition
     * 
     * @param list       Unsorted, Generic list
     * @param leftIndex  The lowest index of the partition
     * @param rightIndex The highest index of the partition
     * @return The current pivot index
     */
    private int partition(ArrayList<E> list, int low, int high) {
        int pivotIndex = chooser.getPivotIndex(list, low, high);
        E pivot = list.get(pivotIndex);
        swap(list, pivotIndex, high);

        int i = low;

        for (int j = low; j <= high; j++) {
            E temp = list.get(j);
            if ((temppareTo(pivot) < 0)) {
                swap(list, i, j);
                i++;
            }
        }

        swap(list, i, high);

        return i;
    }


    /**
     * Swaps two given elements in a given ArrayList
     * 
     * @param list   The given ArrayList
     * @param index1 The first element index to swap
     * @param index2 The second element index to swap
     */
    private void swap(ArrayList<E> list, int index1, int index2) {
        E temp = list.get(index1);
        list.set(index1, list.get(index2));
        list.set(index2, temp);
    }

public class FirstPivotChooser<E extends Comparable<? super E>> implements PivotChooser<E> {

    /**
     * Returns the left-most index in a given ArrayList
     * 
     * @param list       The generic ArrayList
     * @param leftIndex  The left-most or lowest index in the list
     * @param rightIndex The right-most or highest index in the list
     * @return The left-most index
     */
    public int getPivotIndex(ArrayList<E> list, int leftIndex, int rightIndex) {

        return leftIndex;

    }
}

• java
• arraylist
• pivot
• stack-overflow
• quicksort

• Hello Drake, the swap method is missing, and the class PivotChooser, I suggest you edit your question, and add all the relevant information so that we can help you. – Marce Puente Commented Feb 21 at 3:46

1 Answer 1

This is a common issue when implementing quicksort with recursive calls both for the left and the right partition. In case one of the two partitions has almost all the elements of the original subarray -- in the extreme: all except the pivot --, and this continues like that also in the deeper recursive calls, then the recursion depth will amount to O(