Stackoverflow with Quicksort Java implementation

28,526

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]);
}
Share:
28,526
Shaayaan Sayed
Author by

Shaayaan Sayed

Updated on July 09, 2022

Comments

  • Shaayaan Sayed
    Shaayaan Sayed 6 months

    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); 
        }
    }
    
  • Keith Randall
    Keith Randall almost 10 years
    @MitchWheat: so perhaps what I should have said is "a bug", not "the bug".
  • Mitch Wheat
    Mitch Wheat almost 10 years
    Call me old fashioned but I thought the point of an answer was to answer the question fully?
  • Keith Randall
    Keith Randall almost 10 years
    @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
    Mitch Wheat almost 10 years
    yes, it fixes the stackoverflow, but the array is still not sorted correctly...hardly exhaustive...
  • Keith Randall
    Keith Randall almost 10 years
    @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
    Shaayaan Sayed almost 10 years
    @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
    Keith Randall almost 10 years
    You need to partition up to and including ei. length is a red herring.
  • Shaayaan Sayed
    Shaayaan Sayed almost 10 years
    ei is not sorting it properly. what could be the issue?
  • Ayusman
    Ayusman over 7 years
    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)