View Single Post
  #1 (permalink)  
Old May 27th, 2016, 03:46 AM
Choucrouteman Choucrouteman is offline
Registered User
Points: 10, Level: 1
Points: 10, Level: 1 Points: 10, Level: 1 Points: 10, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: May 2016
Posts: 2
Thanks: 0
Thanked 0 Times in 0 Posts
Default Quicksort with duplicate values

Hi,

I have the feeling the messages on this forum are not read much, but anyway, someone might be interested.
I tested the 4 sort test algorithms aroung page 126 (selection sort, insertion sort, merge sort, quick sort) and I believe a big limition lies in quick sort implementation on page 128 - 129 : it doesn't work if original array contains duplicate values.

The fix I found is to count how many times the "pivot value" is found in array and then not only copy this pivot value between left and right values, but copy it as many times as needed.

Here's my version of the quick sort implementation, tested with arrays with duplicate values:

Code:
protected void quickSortRec(int[] toSort) {

        if (toSort.length > 1) {

            int pivotIndex = toSort.length / 2;

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

            // Calculate size of "less" array
            // Decide arbitrarily to keep pivot value in "less"
            for (int value : toSort) {
                if (value < pivotValue) {
                    lessSize++;
                } else if (value == pivotValue) {
                    nbPivot ++;
                }
            }

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

            lessSize = 0;
            int moreSize = 0;

            for (int value : toSort) {
                if (value < pivotValue) {
                    less[lessSize++] = value;
                } else if (value > pivotValue) {
                    more[moreSize++] = value;
                }
            }

            quickSortRec(less);
            quickSortRec(more);

            System.arraycopy(less, 0, toSort, 0, lessSize);
            for (int i = 0; i < nbPivot; i ++) {
                toSort[lessSize + i] = pivotValue;
            }
            System.arraycopy(more, 0, toSort, lessSize + nbPivot, moreSize);
        }
    }
I believe it is mandatory for a sort algorithm, even simple, to handle such case...

Hope this helps, comments welcome!

Cheers

Olivier
Reply With Quote