-2

It works fine for 10 to 50 random item lists, but when I hit 1000 it gets unstable, and sometimes stack overflow occurs, 1000 is even worse. code as followed :

public class InPlaceQuickSort {
    int array[] = {};

    public InPlaceQuickSort(int[] consArray) {
        array = consArray;
    }

    public void qsort(int left, int right) {
        int oldRight = right;
        int oldLeft = left;
        int pivot = left;
        while (array[left] <= array[pivot]) { // increase left pointer until bigger than pivot 
            left = left + 1;
            if (left >= array.length) {
                break;
            }
        }
        while (array[right] > array[pivot]) { // decrease right pointer until smaller than pivot 
            right = right - 1;
            if (right == 0) {
                break;
            }
        }
        if (right <= left) {
            swap(pivot,right); // right change to pivot
            if ((oldRight - right) >= 2) { // here we do right chunk if there are 
                qsort(right+1, oldRight);
            }
            if ((right - oldLeft) > 2) { // here we do left chunk if there are 
                qsort(0, right - 1);
            }
        } else {
            swap(left, right); // swap both anomoly 
            qsort(pivot, oldRight);
        }
    } 

    private void swap(int n1, int n2) {
        int tmp = array[n1];
        array[n1] = array[n2];
        array[n2] = tmp;
    }

}
Steyrix
  • 2,796
  • 1
  • 9
  • 23
AkiZukiLenn
  • 337
  • 3
  • 14
  • Does this answer your question? [Quicksort: Iterative or Recursive](https://stackoverflow.com/questions/12553238/quicksort-iterative-or-recursive) – Abhijit Sarkar Nov 26 '20 at 12:00
  • 1
    Your code makes one recursive call per swap. This is much more than necessary. Do a complete partitioning iteratively and only then make recursive calls for the two parts. – Henry Nov 26 '20 at 12:05
  • Thank you guys, after I put back the partitioning part, and the swapping part into one while loop and only do recursive call afterward, it works around 900 items now. – AkiZukiLenn Nov 26 '20 at 15:03

2 Answers2

0

Here is my correction, and it works for 900 items.

public class InPlaceQuickSort {
int array [] = {} ;

public InPlaceQuickSort (int[]consArray) {
    array = consArray ;
}

public void qsort( int left, int right) {
    int oldRight = right ;
    int oldLeft = left ;
    int pivot= left ;
    while(right>left){
        while(array[left]<=array[pivot]){ // increase left pointer until bigger than pivot 
            left = left + 1 ;
            if(left==array.length){
                break ;
            }
        }
        while(array[right]>array[pivot]){ // decrease right pointer until smaller than pivot 
            right = right - 1 ;
            if(right<left){
                break ;
            }
            if(right==0){
                break ;
            }
        }
        if(right<left){
            break ;
        }else{
            swap(left,right);
        }
    }
    swap(pivot,right); // right change to pivot
    boolean part = false;
    int x = 0 ; 
    int y = 0 ;
    if ((oldRight-right)>=2){ // here we do right chunk if there are 
        part = true ; 
        x = right + 1 ;
        y = oldRight ;
    }
    if(right-oldLeft>2){ // here we do left chunk if there are 
        part = true ;
        x = oldLeft ;
        y = right-1 ;
    }     
    if(part){
        qsort(x, y);
    }
}
private void swap(int n1, int n2) {
    int tmp = array[n1];
    array[n1] = array[n2];
    array[n2] = tmp;
}

}

AkiZukiLenn
  • 337
  • 3
  • 14
0

The default maximum stack depth in Java is 999.

Ironically, the maximum depth is used (as the worst time complexity hit) for quick sort if the data is already sorted.

Try increasing the maximum stack depth by setting this VM parameter:

-Xss 9999
Bohemian
  • 412,405
  • 93
  • 575
  • 722