Javascript: Ordenar matriz y devolver una matriz de índices del que indica la posición de los elementos ordenados con respecto a los elementos originales

Question

Supongamos que tengo una matriz de JavaScript, así:

var test = ['b', 'c', 'd', 'a']; 

Quiero ordenar la matriz . Obviamente, sólo puede hacer esto para ordenar la matriz:

test.sort(); //Now test is ['a', 'b', 'c', 'd'] 

Pero lo que realmente quiero es una serie de índices que indican la posición de los elementos ordenados con respecto a los elementos originales. No estoy muy seguro de cómo expresar esto, así que quizás es por eso que estoy teniendo problemas para descubrir cómo hacerlo.

Si tal método se llamó sortIndices(), a continuación, lo que yo quiero es:

var indices = test.sortIndices(); 
//At this point, I want indices to be [3, 0, 1, 2]. 

'a' era en la posición 3, 'b' fue a los 0, 'c' estaba en 1 y 'd' era un 2 en la matriz original. Por lo tanto, [3, 0, 1, 2].

Una solución sería ordenar una copia de la matriz, y luego recorrer la matriz ordenada y encontrar la posición de cada elemento en la matriz original. Pero, eso se siente torpe.

¿Existe un método existente que haga lo que yo quiero? Si no, ¿cómo escribirías un método que haga esto?

Answer 1

var test = ['b', 'c', 'd', 'a']; 
var test_with_index = []; 
for (var i in test) { 
    test_with_index.push([test[i], i]); 
} 
test_with_index.sort(function(left, right) { 
    return left[0] < right[0] ? -1 : 1; 
}); 
var indexes = []; 
test = []; 
for (var j in test_with_index) { 
    test.push(test_with_index[j][0]); 
    indexes.push(test_with_index[j][1]); 
} 

Editar

Ustedes tienen razón sobre for .. in. Eso se romperá si alguien consume el prototipo de matriz, que observo molestamente a menudo. Aquí está con eso fijo, y envuelto en una función más útil.

function sortWithIndeces(toSort) { 
    for (var i = 0; i < toSort.length; i++) { 
    toSort[i] = [toSort[i], i]; 
    } 
    toSort.sort(function(left, right) { 
    return left[0] < right[0] ? -1 : 1; 
    }); 
    toSort.sortIndices = []; 
    for (var j = 0; j < toSort.length; j++) { 
    toSort.sortIndices.push(toSort[j][1]); 
    toSort[j] = toSort[j][0]; 
    } 
    return toSort; 
} 

var test = ['b', 'c', 'd', 'a']; 
sortWithIndeces(test); 
alert(test.sortIndices.join(",")); 

Answer 2

Array.prototype.sortIndices = function (func) { 
    var i = j = this.length, 
     that = this; 

    while (i--) { 
     this[i] = { k: i, v: this[i] }; 
    } 

    this.sort(function (a, b) { 
     return func ? func.call(that, a.v, b.v) : 
         a.v < b.v ? -1 : a.v > b.v ? 1 : 0; 
    }); 

    while (j--) { 
     this[j] = this[j].k; 
    } 
} 

tu caso es distinto de cómo se siente acerca de la adición de funciones para el prototipo de la matriz y la mutación de las matrices en línea, pero esto permite la clasificación de un conjunto de objetos que se pueden comparar. Se necesita una función opcional que se puede usar para ordenar, al igual que Array.prototype.sort.

Un ejemplo,

var test = [{b:2},{b:3},{b:4},{b:1}]; 

test.sortIndices(function(a,b) { return a.b - b.b; }); 

console.log(test); // returns [3,0,1,2] 

Answer 3

me acaba de llenar una matriz con los números 0..n-1, y ordenar que con una función de comparación.

var test = ['b', 'c', 'd', 'a']; 
var len = test.length; 
var indices = new Array(len); 
for (var i = 0; i < len; ++i) indices[i] = i; 
indices.sort(function (a, b) { return test[a] < test[b] ? -1 : test[a] > test[b] ? 1 : 0; }); 
console.log(indices); 

Answer 4

Dave Aaron Smith es correcto (no puedo comentar), sin embargo, creo que es interesante usar Array map() aquí.

var test = ['b', 'c', 'd', 'a']; 
// make list with indices and values 
indexedTest = test.map(function(e,i){return {ind: i, val: e}}); 
// sort index/value couples, based on values 
indexedTest.sort(function(x, y){return x.val > y.val ? 1 : x.val == y.val ? 0 : -1}); 
// make list keeping only indices 
indices = indexedTest.map(function(e){return e.ind}); 

Answer 5

Usted puede lograr esto con una sola línea usando ES6 (generando una matriz 0->N-1 índice y clasificarlos en base a los valores de entrada).

var test = ['b', 'c', 'd', 'a'] 

var result = Array.from(Array(test.length).keys()) 
        .sort((a, b) => test[a] < test[b] ? -1 : (test[b] < test[a]) | 0)