Wrox Programmer Forums

Need to download code?

View our list of code downloads.

Register | FAQ | Members List | Calendar | Search | Today's Posts | Mark Forums Read
BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 2nd Ed ISBN: 978-0-470-12167-2
This is the forum to discuss the Wrox book Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition by John Mongan, Noah Suojanen, Eric Gigučre; ISBN: 9780470121672
Welcome to the p2p.wrox.com Forums.

You are currently viewing the BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 2nd Ed ISBN: 978-0-470-12167-2 section of the Wrox Programmer to Programmer discussions. This is a community of tens of thousands of software programmers and website developers including Wrox book authors and readers. As a guest, you can read any forum posting. By joining today you can post your own programming questions, respond to other developers’ questions, and eliminate the ads that are displayed to guests. Registration is fast, simple and absolutely free .
DRM-free e-books 300x50
Reply
 
Thread Tools Display Modes
  #1 (permalink)  
Old May 27th, 2016, 03:46 AM
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
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
VBA code to return values of rows that returns row numbers of duplicate values bharatmvs Excel VBA 1 December 5th, 2014 03:19 AM
Assistance with duplicate values fattmatt SQL Language 6 October 21st, 2009 05:26 AM
How Do I avoid duplicate values xsltier XSLT 3 June 4th, 2008 02:36 PM
Detecting duplicate values Europom Excel VBA 2 May 29th, 2007 08:09 AM



All times are GMT -4. The time now is 06:57 AM.


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