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

Choucrouteman May 18th, 2018 10:24 AM

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);
    }



All times are GMT -4. The time now is 07:29 PM.

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