Monday, April 16, 2012

Quicksort Algorithm throws StackOverflowException

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

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

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


No comments:

Post a Comment