Quicksort Algorithm throws StackOverflowException

Question

For a homework assignment, I have to write an implementation of the QuickSort algorithm and use this to sort a list with 100k numbers in some random order.

In the first part of the assignment, I have to use the first item of the array as the pivot element. This indeed returns a sorted list. However, for the second part of the assignment I have to use the last item as the pivot, which results in a StackOverflowException. When I try it in a smaller collection of 8 records, it DOES work correctly. I've been looking at my code but I can't figure out where I'm making a mistake. Any help would be greatly appreciated. My code is as follows:

public class QuickSort {

    private QuickSortStrategyEnum quickSortStrategy;

    public QuickSort(QuickSortStrategyEnum quickSortStrategy) {

        this.quickSortStrategy = quickSortStrategy;
    }

    public List<Integer> sortIntegerArray(List<Integer> arrayList, int left, int right) {

        if ( left >= right ) {
            return arrayList;
        }

        int i = partition(arrayList, left, right);

        if (i <= right) {

            int pivotNew = partition(arrayList, i, right);
            int pivotIndex = arrayList.indexOf(pivotNew);

            arrayList = sortIntegerArray(arrayList, left , pivotIndex - 1);
            arrayList = sortIntegerArray(arrayList, pivotIndex + 1, right);
        }

        return arrayList;
    }

    private int partition(List<Integer> arrayList, int left, int right) {

        int pivot = getPivot(arrayList, left, right);
        int i = left + 1;

        for (int j = i; j <= right; j++) {

            if (arrayList.get(j) < pivot) {

                Collections.swap(arrayList, j, i);
                i++;
            }
        }

        Collections.swap(arrayList, left, i - 1);
        return i;
    }

    private int getPivot(List<Integer> arrayList, int left, int right) {

        int pivot = 0;

        switch (quickSortStrategy) {

            case FIRST:
            pivot = arrayList.get(left);
            break;

            case LAST:
            pivot = arrayList.get(right);
            break;
        }
        return pivot;
    }

}

It would help to know what method/line throws the exception. — David Harkness
– David Harkness, Commented Apr 15, 2012 at 18:59

Louis Wasserman · Accepted Answer · 2012-04-15 18:12:14Z

5

Hint: What can happen if right == left + 1?

answered Apr 15, 2012 at 18:12

Louis Wasserman

200k26 gold badges367 silver badges437 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Peter Lawrey Over a year ago

+1 stepping through the code in a debugger would be useful. ;)

David Harkness Over a year ago

Beyond partition doing a bunch of busy-work, I don't see a problem with this condition. I'm only stepping through it in my head, though. :)

Tejas Patil · Accepted Answer · 2012-04-15 19:25:13Z

1

Along with the fact that David Harkness pointed out, there are problems with the partition logic. Try this out: (after removing things pointed by David Harkness)

private int partition(List<Integer> arrayList, int left, int right) {

    int pivot = getPivot(arrayList, left, right);
    int i = left - 1; 

    for (int j = left; j < right; j++) {
        if (arrayList.get(j) <= pivot) {
            i++;
            Collections.swap(arrayList, j, i);
        }
    }

    Collections.swap(arrayList, i+1, right);
    return i+1;
}

It will work for case when pivot is last element. Not for First element.

Read, understand the working on paper, dry run things out, write pseudo code and then say hello to Eclipse. Dont hurry to implement things.

answered Apr 15, 2012 at 19:25

Tejas Patil

6,1892 gold badges26 silver badges40 bronze badges

3 Comments

Jesse van Assen Over a year ago

If left is the first element (0), you make the index i -1, which causes Collections.swap(arrayList, j, i); to throw an IndexOutOfBoundsException. In Sander's code, the line is int i = left + 1;. Is this a copy-paste error?

Sander Over a year ago

Aaah you're right :) I dove into trying to program a solution too soon, before actually understanding the process. Now I understand how it works and can continue with this solution. I can't upvote you unfortunately as I haven't got enough points but thanks a lot!

Tejas Patil Over a year ago

@JessevanAssen Observe that before calling Collections.swap (arrayList, j, i), I incremented i. I have tested my code and it works

David Harkness · Accepted Answer · 2012-04-15 19:06:15Z

1

These two lines look fishy:

int pivotNew = partition(arrayList, i, right);
int pivotIndex = arrayList.indexOf(pivotNew);

Look at what partition returns and compare it to how you use its result.

answered Apr 15, 2012 at 19:06

David Harkness

36.6k11 gold badges119 silver badges136 bronze badges

1 Comment

Sander Over a year ago

Hmm you're right here, fixed this now. :) Unfortunately I haven't got enough points yet to upvote you..

Collectives™ on Stack Overflow

Quicksort Algorithm throws StackOverflowException

3 Answers 3

2 Comments

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related