javaalgorithmsortingdata-structuresquicksort

My quicksort algorithm is very slow so what can I do to make it faster?


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?


Solution

  • 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;
            }
        }