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); 
    }
}

Solution 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); 
    }
}

Solution 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]);
}

Comments

[Keith Randall]

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

[Mitch Wheat]

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

[Keith Randall]

@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.

[Mitch Wheat]

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

[Keith Randall]

@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".

[Shaayaan Sayed]

@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.

[Keith Randall]

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

[Shaayaan Sayed]

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

[Ayusman]

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)