Permute Sort

by nwellcome

JavaScript

function permuteArray(arr) {
    var p = [];
    var pi = [];
    var dir = [];
    for (i = 0; i < arr.length; i++) {
        dir[i] = -1;
        p[i] = i;
        pi[i] = i;
    }
    permute(0, p, pi, dir, arr);
}

function permute(n, p, pi, dir, arr) {
    if (n >= p.length) {
        var indexStr = "";
        var arrStr = "";
        var isSorted = true;
        for (var i = 0; i < p.length; i++) {
            if (isSorted && i > 0) {
                isSorted = arr[p[i]] > arr[p[i-1]];
            }
            indexStr += p[i] + " ";
            arrStr += arr[p[i]] + " ";
        }
        if (isSorted) {
            alert("[" + indexStr + "] [" + arrStr + "] " + (isSorted ? "Sorted!" : "Not Sorted"));
        }
        return;
    }
    permute(n + 1, p, pi, dir, arr);
    for (var i = 0; i < n; i++) {
        var z = p[pi[n] + dir[n]];
        p[pi[n]] = z;
        p[pi[n] + dir[n]] = n;
        pi[z] = pi[n];
        pi[n] = pi[n] + dir[n];
        permute(n + 1, p, pi, dir, arr);
    }
    dir[n] = -dir[n];
}

permuteArray([4,1,8,2]);