javascriptquicksort

How to implement a stable QuickSort algorithm in JavaScript


How can I write a stable implementation of the Quicksort algorithm in JavaScript?


Solution

  • You can easily "stabilize" an unstable sort using a decorate-sort-undecorate pattern

    function stableSort(v, f)
    {
        if (f === undefined) {
            f = function(a, b) {
                a = ""+a; b = ""+b;
                return a < b ? -1 : (a > b ? 1 : 0);
            }
        }
        var dv = [];
        for (var i=0; i<v.length; i++) {
            dv[i] = [v[i], i];
        }
        dv.sort(function(a, b){
                  return f(a[0], b[0]) || (a[1] - b[1]);
                });
        for (var i=0; i<v.length; i++) {
            v[i] = dv[i][0];
        }
    }
    

    the idea is to add the index as last sorting term so that no two elements are now "the same" and if everything else is the same the original index will be the discriminating factor.