# 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 Author by

### Shaayaan Sayed

Updated on July 09, 2022

• 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 almost 10 years
@MitchWheat: so perhaps what I should have said is "a bug", not "the bug".
• 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 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 almost 10 years
yes, it fixes the stackoverflow, but the array is still not sorted correctly...hardly exhaustive...
• 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 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 almost 10 years
You need to partition up to and including `ei`. `length` is a red herring.
• Shaayaan Sayed almost 10 years
ei is not sorting it properly. what could be the issue?
• 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)