flavour404 flavour404 - 2 years ago 416
Javascript Question

JavaScript quicksort

I have been looking around the web for a while and I am wondering if there is a 'stable' defacto implementation of quicksort that is generally used? I can write my own but why reinvent the wheel...

Answer Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download