Dual Pivot Quicksort Kicks Butt!

So while I was checking out different flavors of quicksort after taking the Coursera Algorithms class I found out about a new version of quicksort that was much faster then I had anticipated.  Java 7 had recently modified their sort function to use a new algorithm called Dual Pivot Quicksort, so I thought I’d check it out.  I found a java version and recoded it to be javascript.  It works well, but currently only sorts integers and in ascending order.  Ideally I should modify it to work the same way the normal array sort algorithm works, that way I’d be comparing apples to apples.  I believe under the hood that the V8 javascript engine has upgraded to the new dual pivot algorithm, but it does have some additional checks and improved functionality where you can pass in the sorting algorithm, which may be why it’s consistently slower then my javascript version of dual pivot quicksort that I coded up.  It’s consistently 10%-50% faster then the default array.sort() algorithm.  The default sort is going to work well enough for 90% of your sorting cases, but if you are following the 10/90 rule and have narrowed down the bottleneck in your code and want to optimize sort, then I would advise taking this code and modifying it for your needs since it will always be faster then the default array.sort().  Check it out on JSPerf http://jsperf.com/javascript-quicksort-comparisons

Technically JS Perf says it’s ±10.25% faster then the default sort the last time I ran it, but it does vary quite a bit. My guess is that it probably varies based on how random the shuffle is.  I suppose it could be because we are comparing a lion to a cheetah….the default sort sorts any object, and lets you pass in the sorting function, while the dual pivot quicksort I coded up only works on integers and in ascending order, but I’d still say it’s worth looking into, ESPECIALLY if whatever language you are coding in hasn’t rewritten their quicksort to use the new algorithm.  I made it a single variable module, and you call it with DualPivotQuicksort.sort(arr). Here’s the code.


/******** Dual Pivot QuickSort ***************/

var DualPivotQuicksort = (function() {

    var dualPivotQS = {};

    dualPivotQS.sort = function(arr, fromIndex, toIndex) {
        if(fromIndex === undefined && toIndex === undefined){
            this.sort(arr, 0, arr.length);
        } else{
            rangeCheck(arr.length, fromIndex, toIndex);
            dualPivotQuicksort(arr, fromIndex, toIndex - 1, 3);
        }
        return arr;
    }

    function rangeCheck(length, fromIndex, toIndex) {
        if (fromIndex > toIndex) {
            console.error("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
        if (fromIndex < 0) {
            console.error(fromIndex);
        }
        if (toIndex > length) {
            console.error(toIndex);
        }
    }

    function swap(arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    function dualPivotQuicksort( arr, left, right, div) {
        var len = right - left;

        if (len < 27) { // insertion sort for tiny array
            for (var i = left + 1; i <= right; i++) {
                for (var j = i; j > left && arr[j] < arr[j - 1]; j--) {
                    swap(arr, j, j - 1);
                }
            }
            return;
        }
        var third = Math.floor(len / div); //TODO: check if we need to round up or down or just nearest

        // "medians"
        var m1 = left  + third;
        var m2 = right - third;

        if (m1 <= left) {
            m1 = left + 1;
        }
        if (m2 >= right) {
            m2 = right - 1;
        }
        if (arr[m1] < arr[m2]) {
            swap(arr, m1, left);
            swap(arr, m2, right);
        }
        else {
            swap(arr, m1, right);
            swap(arr, m2, left);
        }
        // pivots
        var pivot1 = arr[left];
        var pivot2 = arr[right];

        // pointers
        var less  = left  + 1;
        var great = right - 1;

        // sorting
        for (var k = less; k <= great; k++) {
            if (arr[k] < pivot1) {
                swap(arr, k, less++);
            }
            else if (arr[k] > pivot2) {
                while (k < great && arr[great] > pivot2) {
                    great--;
                }
                swap(arr, k, great--);

                if (arr[k] < pivot1) {
                    swap(arr, k, less++);
                }
            }
        }
        // swaps
        var dist = great - less;

        if (dist < 13) {
            div++;
        }
        swap(arr, less  - 1, left);
        swap(arr, great + 1, right);

        // subarrays
        dualPivotQuicksort(arr, left,   less - 2, div);
        dualPivotQuicksort(arr, great + 2, right, div);

        // equal elements
        if (dist > len - 13 && pivot1 != pivot2) {
            for (var k = less; k <= great; k++) {
                if (arr[k] == pivot1) {
                    swap(arr, k, less++);
                }
                else if (arr[k] == pivot2) {
                    swap(arr, k, great--);

                    if (arr[k] == pivot1) {
                        swap(arr, k, less++);
                    }
                }
            }
        }
        // subarray
        if (pivot1 < pivot2) {
            dualPivotQuicksort(arr, less, great, div);
        }
    }
    return dualPivotQS;
}());

/************************************************/

Javascript Modular Design

So I just completed my update of my Facebook app My Amazon Wishlist  I converted all of my messy initialization and jquery UI event handling code into a nice neat single variable javascript module.  It is sooooo much prettier….cleaner, more modular (it’s right there in the name!), less likely to interfere with any other javascript includes.  I briefly contemplated creating javascript objects for the lists….if I were to recode it from the start that’s how I would do it, but for now I’ll leave it as is because cloning the objects is faster and it can stay as is until I decide to implement more features.  The back-end is all php objects, and has made it incredibly easy to update and add features, as well as re-use in my wordpress plugin.  I also updated from jQuery 1.8.1 to 1.10 and had to update a few deprecated function calls that were removed in 1.9 ….GO $(document).on(‘click’, ‘id’, function(){});!…I also had to replace window.parent.document calls inside an iframe with  with jQuery postmessage calls….they actually turned out quite nicely….you have to setup a listener in the parent frame, then in the iframe (or another website even..it solves the cross-domain problem). post the message to the parent.  In my case I was sending multiple pieces of data, so I put it into an array, stringified it and passed it to the parent.  One thing I would note….in the listener you should make it so that it only accepts messages from the website you expect to be sending messages.  Here’s the code from the iframe:

var msgArray = new Object();
msgArray[‘newHeight’] = $(‘#aws-item’).height().toString();
msgArray[‘listNo’] = listNo;
msgArray[‘itemNo’] = itemNo;
msgArray[‘iframeID’] = iframeID;
var message = JSON.stringify(msgArray);
parent.window.postMessage(message, ‘*’);

And so ends my first article for my new website!  I think I’ll write the next one on how I localized (L10N) my WordPress plugin http://wordpress.org/plugins/easy-amazon-wishlist/