Stackoverflow with Quicksort Java implementation

Question

Having some problems implementing quicksort in java. I get a stackoverflow error when I run this program and I'm not exactly sure why. If anyone can point out the error, it would be great.

si is the starting index. ei is the ending index.

public static void qsort(int[] a, int si, int ei){

    //base case
    if(ei<=si || si>=ei){}


    else{ 
        int pivot = a[si]; 
        int length = ei - si + 1; 
        int i = si+1; int tmp; 

        //partition array 
        for(int j = si+1; j<length; j++){
            if(pivot > a[j]){
                tmp = a[j]; 
                a[j] = a[i]; 
                a[i] = tmp; 

                i++; 
            }
        }

        //put pivot in right position
        a[si] = a[i-1]; 
        a[i-1] = pivot; 

        //call qsort on right and left sides of pivot
        qsort(a, 0, i-2); 
        qsort(a, i, a.length-1); 
    }
}

Yogi

Which line throws the exception? – Boron

the last two lines. the two that call quicksort on the right and left sides of pivot. – Yogi

The base case looks pretty standard, if the subarray size is 0 or 1. – Paleontology

The right and left side of the or condition look to be one and the same thing tho. ei <= si is logically the exact same as si >= ei. – Boron

i have it in the main method as: qsort(ar, 0, ar.length-1); where ar is an array i created. – Yogi

Answer 1

First you should fix the bounds of the qsort recursive call as suggested by Keith, since otherwise you're always sorting the whole array over and over again. The you must adjust your partition loop: j is an index, going from the beginning of the subarray to the end of it (including the last element). So you must loop from si + 1 to ei (including ei).

So this is the corrected code. I ran a few test cases and it seems to sort just fine.

    public static void qsort(int[] a, int si, int ei){
    //base case
    if(ei<=si || si>=ei){}

    else{ 
        int pivot = a[si]; 
        int i = si+1; int tmp; 

        //partition array 
        for(int j = si+1; j<= ei; j++){
            if(pivot > a[j]){
                tmp = a[j]; 
                a[j] = a[i]; 
                a[i] = tmp; 

                i++; 
            }
        }

        //put pivot in right position
        a[si] = a[i-1]; 
        a[i-1] = pivot; 

        //call qsort on right and left sides of pivot
        qsort(a, si, i-2); 
        qsort(a, i, ei); 
    }
}

Blasius

Answer 2

int partition(int array[], int too_big_index, int too_small_index)
{
     int x = array[too_big_index];
     int i = too_big_index;
     int j = too_small_index;
     int temp;
     do
     {                 
         while (x <array[j])
        {
              j --;
        } 
         while (x >array[i])
         {
              i++;
         } 
          if (i < j)
         { 
                 temp = array[i];    
                 array[i] = array[j];
                 array[j] = temp;
         }
     }while (i < j);     
     return j;           // middle  
}

void QuickSort(int num[], int too_big_index, int too_small_index)
{
      // too_big_index =  beginning of array
      // too_small_index = end of array

     int middle;
     if (too_big_index < too_small_index)
    {
          middle = partition(num, too_big_index, too_small_index);
          QuickSort(num, too_big_index, middle);   // sort first section
          QuickSort(num, middle+1, too_small_index);    // sort second section
     }
     return;
}



void main()
{
    int arr[]={8,7,13,2,5,19,1,40,12,34};

    QuickSort(arr,0,9);
    for(int i=0;i<10;i++)
         System.out.println(arr[i]);
}

Archle

Answer 3

You might have an unbounded recursion bug on your hands. Not sure from my quick scan of it, but...

Even if you don't, you're still going to use lots of stack with this implementation. Enough to cause a stack overflow. What happens if you call it with 1 million items that are already sorted? You'll partition them into 1 and 999,999 items, then recurse. So you'll need 1 million stack frames to make this work.

There are lots of ways to solve this, including recursing on the smaller of the two ranges and iterating on the larger of the two, or implementing the stack yourself in a heap datastructure, etc. You probably want to do even better than that, though, as the deep stack also means you're blowing past the O(n lg n) sorting bound.

p.s. the bug is here:

qsort(a, 0, i-2); 
qsort(a, i, a.length-1); 

should be

qsort(a, si, i-2);
qsort(a, i, ei);

Truc

@MitchWheat: so perhaps what I should have said is "a bug", not "the bug". – Truc

Call me old fashioned but I thought the point of an answer was to answer the question fully? – Unemployment

@MitchWheat: My fix solves the stack overflow for the one example I tried. I'm not going to exhaustively test his code for him to find any other bug which might be there. – Truc

yes, it fixes the stackoverflow, but the array is still not sorted correctly...hardly exhaustive... – Unemployment

@MitchWheat: I don't think he wants us to fix his code, he wants to understand why it is overflowing the stack. If I just wanted to fix his code, I would have written "delete everything and call Arrays.sort(a, si, ei+1) instead". – Truc

@keith, thanks for fixing the stack overflow error, but if you could address the bug in the sorting code itself that would be great as well. also, I think the second line should be qsort(a, i, j) not ei. not sure about this, even while using this I'm getting problems with the last three elements although the rest of the array is sorting fine. – Yogi

You need to partition up to and including ei. length is a red herring. – Truc

ei is not sorting it properly. what could be the issue? – Yogi

Answer 4

You can try this:

public void sort(int[] A) {
        if (A == null || A.length == 0)
            return;
        quicksort(A, 0, A.length - 1);
    }

    public void quicksort(int[] A, int left, int right) {
        int pivot = A[left + (right - left) / 2];
        int i = left;
        int j = right;
        while (i <= j) {
            while (A[i] < pivot) {
                i++;
            }
            while (A[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchange(i, j);
                i++;
                j--;
            }
        }

        if(left < j)
            quicksort(A,left,j);
        if(i < right)
            quicksort(A,i,right);
    }

    public void exchange(int i, int j){
        int temp=A[i];
        A[i]=A[j];
        A[j]=temp;
    }

    public String toString() {
        String s = "";
        s += "[" + A[0];
        for (int i = 1; i < A.length; i++) {
            s += ", " + A[i];
        }
        s += "]";
        return s;
    }

Source: Code 2 Learn: Quick Sort Algorithm Tutorial

Memorandum

I don't understand the 2 lines after the outermost while loop. Why do we have to do this? if(left < j) and if(i < right) – Alisha

Answer 5

import java.util.Arrays;


public class QuickSort {


    public static int pivot(int[] a, int lo, int hi){
        int mid = (lo+hi)/2;
        int pivot = a[lo] + a[hi] + a[mid] - Math.min(Math.min(a[lo], a[hi]), a[mid]) - Math.max(Math.max(a[lo], a[hi]), a[mid]);

        if(pivot == a[lo])
            return lo;
        else if(pivot == a[hi])
            return hi;
        return mid;
    }

    public static int partition(int[] a, int lo, int hi){

        int k = pivot(a, lo, hi);
        //System.out.println(k);
        swap(a, lo, k);
        //System.out.println(a);
        int j = hi + 1;
        int i = lo;
        while(true){

            while(a[lo] < a[--j])
                if(j==lo)   break;

            while(a[++i] < a[lo])
                if(i==hi) break;

            if(i >= j)  break;
            swap(a, i, j);
        }
        swap(a, lo, j);
        return j;
    }

    public static void sort(int[] a, int lo, int hi){
        if(hi<=lo)  return;
        int p = partition(a, lo, hi);
        sort(a, lo, p-1);
        sort(a, p+1, hi);
    }

    public static void swap(int[] a, int b, int c){
        int swap = a[b];
        a[b] = a[c];
        a[c] = swap;
    }

    public static void sort(int[] a){
        sort(a, 0, a.length - 1);
        System.out.print(Arrays.toString(a));
    }

    public static void main(String[] args) {
        int[] arr = {5,8,6,4,2,9,7,5,9,4,7,6,2,8,7,5,6};
        sort(arr);
    }
}

Try this. It will work for sure.

Oxidate

Answer 6

//Just implemented the tester class for this and it'll work

public int[] sort(int[] A, int from, int to ){

if(from<to){
    int pivot=partition(A,from,to);
    if(pivot>1)
        sort(A,from, pivot-1);

    if(pivot+1<to)
        sort(A, pivot+1, to);


}

return array;

}

public int partition(int A[ ], int from, int to){

while(from < to){
    int pivot=A[from];

    while(A[from]<pivot)
        from++;

    while(A[to]>pivot)
        to--;


    if(from<to)   
        swap(A,to,from);



}
    return to;
}

private void swap(int A[], int i, int j){
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;}

Chatelain

Answer 7

This should be quite spot on. Code below with this Image makes way more sense.

public void quickSort(long[] a){

  int startingIndex = 0;
  int endingIndex = a.length - 1;
  qsort(a, startingIndex, endingIndex);

}

private void qsort(long[] a, int startingIndex, int endingIndex){

  if (startingIndex < endingIndex){
    int middleIndex = partition(a, startingIndex, endingIndex);
    qsort(a, startingIndex, middleIndex-1);
    qsort(a, middleIndex+1, endingIndex);
  }

}

private int partition(long[] a, int startingIndex, int endingIndex){
  long pivot = a[endingIndex];
  int endWall = endingIndex;
  int wall = 0;

  while (wall < endWall){

    if (a[wall] < pivot){
      wall++;
    }
    else {
      a[endWall] = a[wall];
      a[wall] = a[endWall - 1];
      a[endWall - 1] = pivot;
      endWall--;
    }
  }
  return wall;
}

Enjoy!

Disconsolate

Answer 8

public class MyQuickSort {

    private int array[];
    private int length;

    public void sort(int[] inputArr) {

        if (inputArr == null || inputArr.length == 0) {
            return;
        }
        this.array = inputArr;
        length = inputArr.length;
        quickSort(0, length - 1);
    }

    private void quickSort(int lowerIndex, int higherIndex) {

        int i = lowerIndex;
        int j = higherIndex;
        // calculate pivot number, I am taking pivot as middle index number
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        // Divide into two arrays
        while (i <= j) {
            /**
             * In each iteration, we will identify a number from left side which 
             * is greater then the pivot value, and also we will identify a number 
             * from right side which is less then the pivot value. Once the search 
             * is done, then we exchange both numbers.
             */
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSort(lowerIndex, j);
        if (i < higherIndex)
            quickSort(i, higherIndex);
    }

    private void exchangeNumbers(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String a[]){

        MyQuickSort sorter = new MyQuickSort();
        int[] input = {24,2,45,20,56,75,2,56,99,53,12};
        sorter.sort(input);
        for(int i:input){
            System.out.print(i);
            System.out.print(" ");
        }
    }
}

Oology

Answer 9

// the partition function
public static int Sort(int arr[], int start, int end)
{
    int pivot = arr[end];
    int pIndex = start;
    for(int i = start; i< end;i++)
    {
        if(arr[i] <= pivot)
        {
            int temp = arr[i];
            arr[i] = arr[pIndex];
            arr[pIndex] = temp;
            pIndex++;
        }
    }
    int temp = arr[pIndex];
    arr[pIndex] = pivot;
    arr[end] = temp;
    return pIndex;
}
public static void quickSort(int arr[],int start,int end)
{
    if(start>=end)
        return;
    // finding the pivot element
    int pivot = Sort(arr,start,end);
    quickSort(arr,start,pivot-1);
    quickSort(arr,pivot+1,end);
    
}

Kandacekandahar

Answer 10

Quicksort is slightly sensitive to input that happens to be in the right order, in which case it can skip some swaps. Mergesort doesn't have any such optimizations, which also makes Quicksort a bit faster compared to Mergesort.

Why Quick sort is better than Merge sort

Wilone