I'm implementing a quicksort algorithm in Java that uses a fixed pivot (the last element of the array). It works for smaller arrays, but I encounter a StackOverflowError when sorting arrays larger than 100,000 elements. Here's my code:
public class QuicksortFixedPivot {
public int partition(int[] array, int first, int last) {
int pivot = array[last];
int i = first - 1;
for (int j = first; j < last; j++) {
if (array[j] <= pivot) {
i++;
swap(array, i, j);
}
}
swap(array, i + 1, last);
return i + 1;
}
private void quickSort(int[] array, int first, int last) {
if (first < last) {
int pivot = partition(array, first, last);
quickSort(array, first, pivot - 1);
quickSort(array, pivot + 1, last);
}
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void sort(int[] v) {
quickSort(v, 0, v.length - 1);
}
}
Problem:
I get a StackOverflowError during the recursive calls in quickSort, especially with large arrays. Sometimes it occurs after printing the sorted array, indicating the recursion doesn't stop as expected.
Questions:
What causes the StackOverflowError in this implementation?
How can I optimize my quicksort algorithm for larger datasets without this error?
Are there specific strategies to improve the performance of a fixed-pivot quicksort?
To handle already sorted or reverse sorted data:
public int partition(int [] array, int first, int last){
int middle = (first+last)/2; // use middle element for pivot
swap(array, middle, last);
int pivot = array[last];
int i = first - 1;
for (int j = first; j < last; j++){
if (array[j]<= pivot){
i++;
swap(array, i, j);
}
}
swap(array, i+1, last);
return i+1;
}
Stack usage can be reduced to O(log2(n)) by recursing on smaller partition, looping for larger partition. Worst case time complexity is still O(n^2).
private void quickSort(int [] array, int first, int last){
while (first < last){
int pivot = partition(array, first, last);
if((pivot - first) <= (last - pivot){
quickSort(array, first, pivot - 1);
first = pivot + 1;
} else {
quickSort(array, pivot + 1, last);
last = pivot - 1;
}
}
If there are a lot of duplicates, then Lomuto degrades towards worst case, while Hoare improves towards best case. Example code (the names will need to be changed):
@SuppressWarnings("empty-statement")
public int partition(int[] a, int lo, int hi)
{
if(lo >= hi)
return;
int p = a[lo+(hi-lo)/2];
int i = lo-1;
int j = hi+1;
int t;
while(true){ // partition
while(a[++i] < p);
while(a[--j] > p);
if(i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
return j;
}
private void quickSort(int [] array, int first, int last){
while (first < last){
int split = partition(array, first, last);
if((split - first) <= (last - split){
quickSort(array, first, split);
first = split + 1;
} else {
quickSort(array, split + 1, last);
last = split;
}
}