Java Quicksort - Stack Overflow

Question

I'm attempting to implement a version of quick sort that uses a pivot calculated as follows:

pivot = ( a[start] + a[end] + a[size/2] ) / 3

ATM it works perfectly on array's of size 6 or less, however as soon as an array size of 7 or greater is sorted the program enters an infinite loop. My understanding of recursion isn't solid as of yet, so I suspect it's falling apart there. I know it enters a loop when checking indexes 4 and 6, and then continually checks ONLY those indexes

Edit: Added the call to quickSort(), and fixed some formatting

public static void quickSort(double[] list, int start, int end){
    if (end - start > 1){
      int pivot = split(list, start, end);
      quickSort(list, start, pivot - 1);
      quickSort(list, pivot + 1, end);
    } 
    if ( (end - start) == 1){
      if (list[start] > list[end]){
        double temp = list[start];
        list[start] = list[end];
        list[end] = temp;
      }
    }
  }

  public static int split(double[] list, int start, int end){
    // splitPoint = (a[begin] + a[end] + a[size/2]) / 3
    int size = end - start + 1;
    double pivotValue = (list[start] + list[end] + list[size/2]) / 3;

    int leftPosition = start;
    int rightPosition = end;
    double temp = 0;

    while (true){
      // find a value to swap on the left side of pivot
      while ( (leftPosition <= rightPosition) && (list[leftPosition] <= pivotValue) ){
        leftPosition++;
      }

      // find a value to swap on the right side of pivot
      while ( (rightPosition >= leftPosition) && (list[rightPosition] >= pivotValue) ){
        rightPosition--;
      }
      // if positions pass each other
      if (rightPosition < leftPosition){
        break;
      } else {
        // swap values
        temp = list[leftPosition];
        list[leftPosition] = list[rightPosition];
        list[rightPosition] = temp;
      }
    }
    return rightPosition;
  }

  public static void main(String[] args){
      double[] list = {7, 6, 5, 4, 3, 2, 1};
      quickSort(list, 0, list.length-1);
  }

Stack overflow conditions are best tackled by running in an IDE, and enabling "break on exception" -- that way you can inspect the stack and see where the algorithm went wrong. Since it breaks on a relatively small case, you can just put a breakpoint at if (end - start > 1){ and just wait for one of the values to be negative. — Gus
– Gus, Commented Mar 26, 2018 at 20:46

Bax · Accepted Answer · 2018-03-26 20:44:49Z

The first step of the algorithm is :

Pick an element, called a pivot, from the array.

This expression does not do that :

(list[start] + list[end] + list[size / 2]) / 3

It just computes the average of 3 numbers one of which can be outside of the partition being sorted (see start +).
So given this array : {1,2,3,4,5,6,7}, start = 4 and end = 6 the picked item will be (5 + 7 + 2)/3 = 4.(6)7 and this is not an element of the partition {5,6,7}.
What you should do is pick a number within the start...end range as the index of the pivot.

start +

I believe the pivot you were actually thinking about (the average of the first, last and middle elements of the partition) is :

(list[start] + list[end] + list[start + (size / 2)]) / 3.0

Although this expression does not pick an element from the partition it will pick a value which is not bigger/smaller than all values in the partition and it will work.

Working solution with a /3 pivot :

void quickSort(double[] list, int start, int end) {
    int size = end - start + 1;
    // this is the 'classic' pivot
    // double pivotValue = list[start + (end - start) / 2];
    double pivotValue = (list[start] + list[end] + list[start + (size / 2)]) / 3.0;
    int leftPosition = start;
    int rightPosition = end;

    while (leftPosition <= rightPosition) {
        while (list[leftPosition] < pivotValue) {
            leftPosition++;
        }
        while (list[rightPosition] > pivotValue) {
            rightPosition--;
        }

        if (leftPosition <= rightPosition) {
            exchange(list, leftPosition, rightPosition);
            leftPosition++;
            rightPosition--;
        }
    }
    if (start < rightPosition)
        quickSort(list, start, rightPosition);
    if (leftPosition < end)
        quickSort(list, leftPosition, end);
}

void exchange(double[] list, int i, int j) {
    double temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

Collectives™ on Stack Overflow

Java Quicksort - Stack Overflow

1 Answer 1

start +

Working solution with a /3 pivot :

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

start +

Working solution with a /3 pivot :

Comments

Your Answer

Sign up or log in

Post as a guest

Related