View Single Post
  #2 (permalink)  
Old May 18th, 2018, 10:24 AM
Choucrouteman Choucrouteman is offline
Registered User
Points: 20, Level: 1
Points: 20, Level: 1 Points: 20, Level: 1 Points: 20, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: May 2016
Posts: 4
Thanks: 0
Thanked 0 Times in 0 Posts
Default

I was wrong.

The code I posted does work, but it's overcomplicated since the original algorithm did also.

Here is an adaptation of my previous code that is closer to the original algorithm and still works:

Code:
protected void quickSortRec(int[] toSort) {
        // base case
        if (toSort.length <= 1) {
            return;
        }

        int pivotIndex = toSort.length / 2;

        int pivotValue = toSort[pivotIndex];
        int lessSize = 0;

        // Calculate size of "less" array
        for (int value : toSort) {
            if (value < pivotValue) {
                lessSize++;
            }
        }

        int[] less = new int[lessSize];
        int[] more = new int[toSort.length - lessSize - 1];

        lessSize = 0;
        int moreSize = 0;

        for (int i = 0; i < toSort.length; i ++) {
            if (i == pivotIndex) continue;
            
            int value = toSort[i];
            if (value < pivotValue) {
                less[lessSize++] = value;
            } else{
                more[moreSize++] = value;
            }
        }

        quickSortRec(less);
        quickSortRec(more);

        System.arraycopy(less, 0, toSort, 0, lessSize);
        toSort[lessSize] = pivotValue;
        System.arraycopy(more, 0, toSort, lessSize + 1, moreSize);
    }
Reply With Quote