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

6 minutos de lectura

Avatar de usuario de Jeremy
jeremy

Supongamos que tengo una matriz de Javascript, así:

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

Quiero ordenar la matriz. Obviamente, puedo hacer esto para ordenar la matriz:

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

Pero lo que realmente quiero es una matriz de índices que indique la posición de los elementos ordenados con respecto a los elementos originales. No estoy muy seguro de cómo expresar esto, así que tal vez es por eso que tengo problemas para descubrir cómo hacerlo.

Si dicho método se llamara sortIndices(), entonces lo que querría es:

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

‘a’ estaba en la posición 3, ‘b’ estaba en 0, ‘c’ estaba en 1 y ‘d’ era un 2 en la matriz original. Por eso, [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.

¿Hay algún método existente que haga lo que quiero? Si no, ¿cómo haría para escribir un método que haga esto?

Avatar de usuario de Dave Aaron Smith
David Aarón Smith

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 acerca de for .. in. Eso se romperá si alguien manipula el prototipo de matriz, lo que observo con mucha frecuencia. Aquí está con eso arreglado 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(","));

  • +1 pero creo que es mejor que no uses un for .. in bucle en una matriz.

    – Tomalak

    16 de septiembre de 2010 a las 20:45

  • Eso es una buena idea. Le voy a dar una oportunidad. (Lo aceptaré una vez que lo haga funcionar).

    – Jeremy

    16 de septiembre de 2010 a las 20:49

  • @Tomalak: Estoy de acuerdo con usted acerca de .. in. He tenido muchos problemas con eso.

    – Jeremy

    16 de septiembre de 2010 a las 20:51

  • Usando for-in con un Array es casi siempre una muy mala idea.

    – extraño

    16 de septiembre de 2010 a las 23:04

  • Tenga cuidado si su matriz no está definida o es nula, puede causar un comportamiento inesperado. Aquí está mi solución Typescript function getSortIndice<T extends number>(toSort: T[]): number[] { const sortingPair: [T, number][] = toSort.map((value, index) => [value, index]); sortingPair.sort((left, right) => { return (left[0] || 0) < (right[0] || 0) ? -1 : 1; // to be able to compare undefined }); const sortIndices: number[] = sortingPair.map(([t, indice]) => indice); return sortIndices; }

    – Zen3515

    2 de octubre de 2020 a las 9:12


Simplemente llenaría una matriz con los números 0..n-1, y la ordenaría 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);

  • Esto es genial, y puede ser incluso un poco mejor (¡haga que la ordenación sea estable!) al comparar los índices (a y b) si los valores son iguales. es decir, cambiar ... test[a] > test[b] ? 1 : 0 a ... test[a] > test[b] ? 1 : a < b ? -1 : 1según: stackoverflow.com/questions/1427608/…

    –David Baird

    28 de diciembre de 2016 a las 3:20

  • También vea esta gran respuesta que proporciona una forma (ciertamente menos eficaz) de llenar la matriz en una línea. Revelación: let indices = [...Array(test.length).keys()];.

    – Jeff G.

    9 de mayo de 2020 a las 2:03


  • Aunque esta respuesta no está escrita de manera compacta, sigo creyendo que esta es la mejor respuesta, simplemente porque no cambia la estructura de matriz existente y el algoritmo en sí está desacoplado para ser reutilizado en cualquier forma de combinación y combinación.

    – viento maomao

    14 de diciembre de 2021 a las 15:22

Avatar de usuario de Matt Way
Camino mate

Puede lograr esto con una sola línea usando es6 (generando un 0->N-1 matriz de índices y ordenarla en función de 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)

console.log(result)

  • esta es la mejor respuesta aquí en mi humilde opinión. no es necesario todo ese mapeo adicional y +1 por usar Array.keys()

    – milesaron

    30 de julio de 2020 a las 20:53

  • Por que no .sort((a,b) => test[b]-test[a]) ?

    – Adán

    12 de junio a las 15:50

  • @Adam, es posible que me esté perdiendo algo, pero ¿cómo funcionaría? 'b' - 'a' = NaN por ejemplo.

    – Matt Camino

    12 de junio a las 21:41

  • @MattWay lo siento, tienes razón. Vine aquí por la misma pregunta, pero mi matriz tiene números …

    – Adán

    13 de junio a las 6:11

avatar de usuario de clerbois
clérigo

Dave Aaron Smith tiene razón, 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});

Avatar de usuario de Dexygen
Dexígeno

Esta es una versión ES6 más idiomática de la respuesta de clerbois, vea los comentarios de ellos:

return test.map((val, ind) => {return {ind, val}})
           .sort((a, b) => {return a.val > b.val ? 1 : a.val == b.val ? 0 : -1 })
           .map((obj) => obj.ind);

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;
    }
}

YMMV sobre cómo se siente al agregar funciones al prototipo Array y mutar matrices en línea, pero esto permite clasificar una matriz de cualquier objeto que se pueda comparar. Se necesita una función opcional que se puede usar para clasificar, 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]

avatar de usuario de yakin.rojinegro
yakin.rojinegro

Puede hacer esto con el objeto Mapa. Simplemente configure la clave/valor como índice/valor y use Array.from para obtener el iterador como una matriz bidimensional y luego ordene los índices, los valores o ambos.

function sorting(elements) {
  const myMap = new Map();
  elements.forEach((value, index) => {
    myMap.set(index, value);
  });
  const arrayWithOrderedIndexes = Array.from(myMap.entries()).sort((left, right) => {return left[1] < right[1] ? -1 : 1});
  myMap.clear();
  return arrayWithOrderedIndexes.map(elem => elem[0]);
}
const elements = ['value','some value','a value','zikas value','another value','something value','xtra value'];
sorting(elements);

¿Ha sido útil esta solución?