Pivot as the median of three random numbers

Question

I am working on a program that uses quick sort to sort an array to display the running time. This program selects the median of three random numbers as the pivot. However, I am not sure if I am doing something wrong because every time I run this program I get the following errors:

"java.lang.StackOverflowError", 
at java.util.Random.nextInt(Unknown Source)
at SortingItems.quickSort(SortingItems.java:31)
at SortingItems.quickSort(SortingItems.java:69)   " I get this  specific message multiple times"

This is the code:

import java.util.Random;

public class SortingItems {
    static int x = 1000;
    static int array []  = new int[x];

    public static void main(String[] args) {

       long time;

       input(x, array);
       time = System.nanoTime();
       sort(array);
       System.out.println("Running time in ascending order " + (System.nanoTime() - time));

   }

   public static void sort(int[] array) {
       quickSort(array, 0, array.length - 1);
   }

   public static void quickSort(int[] array, int low, int high) {
       if (array == null || array.length == 0)
           return;

       if (low >= high)
           return;

       // Generating random numbers from 0 to the last element of the array
       Random f = new Random();
       int first = f.nextInt(array.length - 1);

       Random s = new Random();
       int second = s.nextInt(array.length - 1);

       Random t = new Random();
       int third = t.nextInt(array.length - 1);



       // Selecting the pivot
       int pivot = Math.max(Math.min(array[first], array[second]),
                   Math.min(Math.max(array[first],array[second]), array[third]));

       int i = low;
       int j = high;

       while (i <= j) {
            while (array[i] < pivot) {
                  i++;
            }

            while (array[j] > pivot) {
                  j--;
            }

            if (i <= j) {
                 int temp = array[i];
                 array[i] = array[j];
                 array[j] = temp;
                 i++;
                 j--;

            }
      }

      if (low < j)
          quickSort(array, low, j);

      if (high > i)
          quickSort(array, i, high);

  }

  // Input in ascending order
  public static int[] input(int x, int[] array) {
       for (int k = 0; k < x; k++) {
            array[k] = k;
       }
       return array;

  }
}

@JarrodRoberson When I use the pivot as the median of the first three elements of the array rather than the median of three random numbers, the program runs just fine. Why is this? — SdlS, Dec 05 '14 at 17:43
@JarrodRoberson: The answer could've helped debug the error. Marking it as a duplicate seems excessive. — Roney Michael, Dec 05 '14 at 17:45
@SdlS: The problem is in how you were picking the median. It should've been as follows: `int first = f.nextInt(high-low) + low;` If you change how the three indices are picked so, it should work.. Right now you seem to be checking an entire large array for the pivot, and given the structure of your input data, it would cause a stack-overflow if a very high probability. — Roney Michael, Dec 05 '14 at 17:47
@Flexo: Yes please. The question seems to have been re-opened. Thanks for pointing it out! — Roney Michael, Dec 06 '14 at 17:45

score 0 · Answer 1 · answered Dec 06 '14 at 17:51

The problem seems to be with how the median is being selected here. The pivots should be chosen from between the current high and low positions and not the entire array.

Note that your test-input is in ascending order. Now, as you select three random values from the entire array of size 1000 for pivoting, when it comes to the smaller recursive cases, the arrays tend to be lopsided with a very high probability. This means that another level of recursion would be called with the same input parameters. In the long run, this is likely to cause a stack overflow with a high probability.

The following change should fix your issue:

// Generating random numbers from low to high
Random f = new Random();
int first = f.nextInt(high-low) + low;

Random s = new Random();
int second = s.nextInt(high-low) + low;

Random t = new Random();
int third = t.nextInt(high-low) + low;

Pivot as the median of three random numbers

1 Answers1