p2p.wrox.com Forums

p2p.wrox.com Forums (http://p2p.wrox.com/)
-   BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 2nd Ed ISBN: 978-0-470-12167-2 (http://p2p.wrox.com/book-programming-interviews-exposed-secrets-landing-your-next-job-2nd-ed-isbn-978-0-470-12167-2-324/)
-   -   Quicksort with duplicate values (http://p2p.wrox.com/book-programming-interviews-exposed-secrets-landing-your-next-job-2nd-ed-isbn-978-0-470-12167-2/98993-quicksort-duplicate-values.html)

Choucrouteman May 27th, 2016 02:46 AM

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


All times are GMT -4. The time now is 02:27 AM.

Powered by vBulletin®
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
2013 John Wiley & Sons, Inc.