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;

}

}

## No comments:

## Post a Comment