Quicksort (Java) causes StackOverFlow at array.length > 60k

Question

My code works properly (to my knowledge) up until my input array size (a.length) is around 62,000 at which time I consistently get a StackOverFlowError. I previously had used 2 recursive calls to quicksort (less than, and greater than the pivot q) and then I switched to tail recursion. As you can see, I'm selecting the pivot to be the value at the end of the array. I know this isn't the best way to choose a pivot, but I still shouldn't be seeing StackOverFlowErrors with an array size this small, right? What could be causing this? Thanks in advance! Here's my code:

    public static void quicksort(int[] a, int p, int r)
    {
        int q;
        while (p < r)
        {
            q = partition(a, p, r);
            quicksort(a, p, q - 1);
            p = q + 1;
        }
    }

    public static int partition(int[] a, int p, int r)
    {
        int j = p - 1;
        int x = a[r];
        for (int i = p; i < r; i++)
        {
            if (a[i] <= x)
            {
                j++;
                swap(a, i, j);
            }
        }
        j++;
        swap(a, j, r);
        return j;
    }

    private static void swap(int[] a, int i, int j)
    {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

blackcompe · Accepted Answer · 2014-01-12 04:11:06Z

9

The worst-case input (sorted order) makes quicksort Θ(n^2). Partition always puts a single element on one side of the partition (Cormen et al.). By randomizing the sort (choosing a random pivot) no particular input elicits its worst-case behavior.

import java.util.Random;

public class Quicksort
{
     private static Random rand = new Random();

     public static void quicksort(int[] arr, int left, int right)
     {
          if (left < right)
          {
               int pivot = randomizedPartition(arr, left, right);
               quicksort(arr, left, pivot);
               quicksort(arr, pivot + 1, right);
          }
     }

     private static int randomizedPartition(int[] arr, int left, int right)
     {
          int swapIndex = left + rand.nextInt(right - left) + 1;
          swap(arr, left, swapIndex);
          return partition(arr, left, right);
     }

     private static int partition(int[] arr, int left, int right)
     {
          int pivot = arr[left];
          int i = left - 1;
          int j = right + 1;
          while (true)
          {
               do
                    j--;
               while (arr[j] > pivot);

               do
                    i++;
               while (arr[i] < pivot);

               if (i < j)
                    swap(arr, i, j);
               else
                    return j;
          }
     }

     private static void swap(int[] arr, int i, int j)
     {
          int tmp = arr[i];
          arr[i] = arr[j];
          arr[j] = tmp;
     }

     // Sort 100k elements that are in reversed sorted order
     public static void main(String[] args)
     {
          int arr[] = new int[100000];
          for (int i = 0; i < arr.length; i++)
               arr[i] = arr.length - i;

          System.out.println("First 20 elements");
          System.out.print("Before sort: ");
          for (int i = 0; i < 20; i++)
               System.out.print(arr[i] + " ");
          System.out.println();

          quicksort(arr, 0, arr.length - 1);
          System.out.print("After sort: ");
          for (int i = 0; i < 20; i++)
               System.out.print(arr[i] + " ");
          System.out.println();
     }

}

edited Jan 12, 2014 at 4:11

answered Oct 30, 2011 at 3:28

blackcompe

3,2001 gold badge21 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Phil Over a year ago

Any idea what it is about my code which causes too many recursive calls?

Phil Over a year ago

What's interesting is you apparently were able to get my implementation to sort 100k array elements in the average case scenario. That must be just due to a difference in stack limitation sizes.

blackcompe Over a year ago

I updated my post. I think you got an input that resulted in the worst case behavior, and the stack exploded!!

Phil Over a year ago

Hey blackcompe, thanks for the input! Your partition algorithm works for pretty large array sizes without any problems. Additionally, the stack depth is significantly decreased.

servn · Accepted Answer · 2011-10-30 02:27:24Z

3

Given the right input, your implementation will recurse once for every single element of the array. 60,000 recursive calls could easily be enough to overflow the stack in Java in the default configuration.

answered Oct 30, 2011 at 2:27

servn

3,08916 silver badges8 bronze badges

2 Comments

Phil Over a year ago

If my implementation recurses for every element in the stack, wouldn't I have a stack depth identical to the array size? I've monitored the maximum stack depth of this quicksort method with counters. At array size of 60k, my quicksort method reaches a recursion depth between 6,000 to 6,250.

Jens Schauder Over a year ago

a stack depth > 6k sounds like good candidate for a stack overflow to me.

Collectives™ on Stack Overflow

Quicksort (Java) causes StackOverFlow at array.length > 60k

2 Answers 2

4 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related