algorithm - Stackoverflow with Quicksort Java implementation -

algorithm - Stackoverflow with Quicksort Java implementation -

having problems implementing quicksort in java. stackoverflow error when run programme , i'm not sure why. if can point out error, great.

si starting index. ei 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 = 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 , left sides of pivot qsort(a, 0, i-2); qsort(a, i, a.length-1); } }

first should prepare bounds of qsort recursive phone call suggested keith, since otherwise you're sorting whole array on , on again. must adjust partition loop: j index, going origin of subarray end of (including lastly element). must loop si + 1 ei (including ei).

so corrected code. ran few test cases , seems sort fine.

public static void qsort(int[] a, int si, int ei){ //base case if(ei<=si || si>=ei){} else{ int pivot = a[si]; int = 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 , left sides of pivot qsort(a, si, i-2); qsort(a, i, ei); } }

java algorithm sorting stack-overflow quicksort