Quicksort Stack Overflow with Big array sizes and few distinct values

Question

I'm working on implementing a Quicksort algorithm which I've got to work fine with array sizes up to 100,000. Once I try to sort with a size of 1,000,000 I get a stack overflow error (which is happening to my best understanding due to the recursive functionality of my algorithm).
I know this question has been asked on here before, but none of those answers helped me at all. I've looked through my code extensively, and even modeled it off a Java textbook just to double check, still no fix.
I've been reading on here for at least an hour trying to solve this, and I read that the call stack could hold up to 8MB or so depending on the system. I'm wondering if either:

My algorithm is wrong
1,000,000 elements is too large to use for a quicksort (with this compiler).

EDIT: To anyone interested: I discovered that increasing my random interval from 1-9 to 1-n (n being the size of the sequence being sorted, ex: 1-1000000), my quicksort ran extremely faster, and of course didn't have any overflow problems.

I'm going to submit my code now, with the driver, and hopefully someone can quickly show me where I went wrong.

public class QuickSort {

    public static void main(String[] args) {

        //JUST TO TEST THAT IT WORKS
        int[]A = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; //worst case

        quickSort(A, 0, A.length-1);

        //print the array
        for (int a :A)
            System.out.print(a+" ");
        System.out.println();

    }

    /**
     * Quicksort algorithm, O(n log n) best and average case, O(n^2) worst case
     * @param S sequence to sort
     * @param a the lower bound of sequence
     * @param b upper bound of sequence
     */
    public static void quickSort(int[]S, int a, int b) {
        if (a >= b)
            return;
        int p = S[b]; //setting pivot to the last element in sequence
        int l = a;
        int r = b - 1;
        int temp;

        while (l <= r) { //once left and right have crossed this will end while
            while (l<= r && S[l] <= p) {
                l++; //move in from left side until found an element greater than the pivot
            }
            while (l <= r && S[r] >= p) {
                r--; //move in from right side until element found less than the pivot
            }
            if (l <= r) {
                //swap S[l] and S[r] //swap the left and right elements if they haven't crossed
                temp = S[l];
                S[l] = S[r];
                S[r] = temp;
                l++;
                r--;
            }
        }
        //left and right have crossed here
        //swap S[l] and S[b] //put the pivot back to the new partition spot
        temp = S[l];
        S[l] = S[b];
        S[b] = temp;
        quickSort(S, a, l-1); //call quicksort on our new sublists partitioned around our pivot
        quickSort(S, l+1, b);
        //recursive calls
    }
}

The Driver:

import java.util.Random;

public class SortingCompare {

    public static void main(String[] args) {
        Random rand = new Random();
        System.out.printf("Sorting Run Times:\n");
        System.out.printf("Array Size   Insertion Sort%5s%s\n", " ","Quick sort");

            int A[] = new int[100000];
            int n = 100000;

            for (int i = 0; i < n; i++) {
                A[i] = rand.nextInt(9) + 1; //1-9
            }
            //array is filled with random integers

            long startQuickSort = System.currentTimeMillis();
            QuickSort.quickSort(A, 0, A.length - 1);
            long quickTime = System.currentTimeMillis() - startQuickSort;

            System.out.printf("%-5d%10dms%15s%dms\n", n, insertionTime, " ", quickTime);
    }
}

I would highly recommend that you use insertionsort for partitions smaller than 1000 Elements. That is how the quicksort algorythm is used in Java Collection for example. — Christian
– Christian, Commented Feb 25, 2018 at 23:31
You recurse all the way down to single item partitions. That gives very deep stacks. — Thorbjørn Ravn Andersen
– Thorbjørn Ravn Andersen, Commented Feb 26, 2018 at 0:52
@Christian 1000 is far too high. It was traditionally 15 or 16 following Knuth and Sedgewick. The threshold below which the collections don't sort is 47. — user207421
– user207421, Commented Feb 26, 2018 at 4:32
Interesting, I found insertion sort way faster until about 15 elements or so as well. — dave99collins
– dave99collins, Commented Feb 26, 2018 at 19:08
To anyone interested: I discovered that increasing my random interval from 1-9 to 1-n (n being the size of the sequence being sorted, ex: 1-1000000), my quicksort ran extremely faster, and of course didn't have any overflow problems. — dave99collins
– dave99collins, Commented Feb 28, 2018 at 19:44

rcgldr · Accepted Answer · 2025-02-16 02:46:10Z

This is an issue related to using Lomuto partition scheme. If using Hoare partition scheme, as the number of duplicate values increases, its partitioning improves. If sorting all equal values, it does an ideal split. Example Hoare partitioning code:

void QuickSort(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;
    while(1){
        while (a[++i] < p);
        while (a[--j] > p);
        if(i >= j)
            break;
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    i = j++;
    QuickSort(a, lo, i);
    QuickSort(a, j, hi);
}

Stack space can be limited to log2(n), by doing smaller partition first, and lager partition later. This is how the original quicksort was implemented, using a program created stack, which Hoare called a "nest". For a recursive sort, then means recursing on the smaller partition and looping back for the larger partition. Example C++ code:

void QuickSort(uint64_t a[], int lo, int hi)
{
    while (lo < hi){
        uint64_t p = a[lo + (hi - lo) / 2];
        int i = lo - 1;
        int j = hi + 1;
        while (1){
            while (a[++i] < p);
            while (a[--j] > p);
            if (i >= j)
                break;
            std::swap(a[i], a[j]);
        }
        if(j - lo < hi - j){
            QuickSort(a, lo, j);
            lo = j+1;
        } else {
            QuickSort(a, j+1, hi);
            hi = j;
        }
    }
}

user207421 · Accepted Answer · 2018-02-26 04:05:52Z

1

You should sort the smaller of the two partitions first, to minimize stack usage, and use an insertion sort for partitions less than say 16 elements.

You also need to look up the Quicksort algorithm. You don't need two tests in each inner loop: they completely destroy the point of the algorithm; and the details of your implementation vary from the canonical version by Sedgewick.

edited Feb 26, 2018 at 4:05

answered Feb 25, 2018 at 23:20

user207421

312k45 gold badges324 silver badges493 bronze badges

Comments

Livio · Accepted Answer · 2025-02-15 12:58:21Z

0

You can use quicksort from Java that is optimized both for performance and memory usage, so in your code replace:

quickSort(A, 0, A.length - 1);

with:

Arrays.sort(A);

In order to run the modified code you need the following import:

import java.util.Arrays;

The class Arrays provides several helpful methods that are optimized for JVM and does not require to reinvent the wheel. Java standard libraries have been tested carefully and are continually updated to improve their performance and robustness.

edited Feb 15 at 12:58

answered Feb 25, 2018 at 23:31

Livio

9421 gold badge10 silver badges27 bronze badges

Comments

Matt Timmermans · Accepted Answer · 2025-02-15 15:48:56Z

0

In a practical implementation of quicksort, you recurse to sort the smaller partition, and then just loop the sort the larger partition. This keeps stack depth < log₂ N.

answered Feb 15 at 15:48

Matt Timmermans

60.9k3 gold badges57 silver badges106 bronze badges

Collectives™ on Stack Overflow

Quicksort Stack Overflow with Big array sizes and few distinct values

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related