ejemplos - javascript español

Implementación rápida del algoritmo de clasificación estable en JavaScript

Question

Estoy buscando ordenar una matriz de aproximadamente 200-300 objetos, ordenando una clave específica y un orden determinado (asc / desc). El orden de los resultados debe ser consistente y estable.

¿Cuál sería el mejor algoritmo para usar y podría proporcionar un ejemplo de su implementación en javascript?

¡Gracias!

Answer 1

¿Funcionará la función de ordenamiento incorporada? http://www.w3schools.com/jsref/jsref_sort.asp

Answer 2

A continuación se ordena la matriz suministrada, aplicando la función de comparación suministrada, devolviendo la comparación de índice original cuando la función de comparación devuelve 0:

function stableSort(arr, compare) {
    var original = arr.slice(0);

    arr.sort(function(a, b){
        var result = compare(a, b);
        return result === 0 ? original.indexOf(a) - original.indexOf(b) : result;
    });

    return arr;
}

El siguiente ejemplo ordena una matriz de nombres por apellido, conservando el orden de los mismos apellidos:

var names = [
 { surname: "Williams", firstname: "Mary" },
 { surname: "Doe", firstname: "Mary" }, 
 { surname: "Johnson", firstname: "Alan" }, 
 { surname: "Doe", firstname: "John" }, 
 { surname: "White", firstname: "John" }, 
 { surname: "Doe", firstname: "Sam" }
]

function stableSort(arr, compare) {
    var original = arr.slice(0);

    arr.sort(function(a, b){
        var result = compare(a, b);
        return result === 0 ? original.indexOf(a) - original.indexOf(b) : result;
    });
 
    return arr;
}

stableSort(names, function(a, b) { 
 return a.surname > b.surname ? 1 : a.surname < b.surname ? -1 : 0;
})

names.forEach(function(name) {
 console.log(name.surname + '', '' + name.firstname);
});

Answer 3

Aquí hay una implementación estable. Funciona mediante el uso del género nativo, pero en los casos en que los elementos se pueden comparar como iguales, se rompen vínculos utilizando la posición del índice original.

function stableSort(arr, cmpFunc) {
    //wrap the arr elements in wrapper objects, so we can associate them with their origional starting index position
    var arrOfWrapper = arr.map(function(elem, idx){
        return {elem: elem, idx: idx};
    });

    //sort the wrappers, breaking sorting ties by using their elements orig index position
    arrOfWrapper.sort(function(wrapperA, wrapperB){
        var cmpDiff = cmpFunc(wrapperA.elem, wrapperB.elem);
        return cmpDiff === 0 
             ? wrapperA.idx - wrapperB.idx
             : cmpDiff;
    });

    //unwrap and return the elements
    return arrOfWrapper.map(function(wrapper){
        return wrapper.elem;
    });
}

una prueba no exhaustiva

var res = stableSort([{a:1, b:4}, {a:1, b:5}], function(a, b){
    return a.a - b.a;
});
console.log(res);

Otra respuesta aludió a esto, pero no publicó el código.

pero no es rápido según mi benchmark . Modifiqué una clase de fusión impl para aceptar una función de comparador personalizado, y fue mucho más rápido.

Answer 4

Aquí se explica cómo puede extender el objeto Array predeterminado de JS con un método prototipo que utiliza MERGE SORT . Este método permite clasificar una clave específica (primer parámetro) y un orden determinado (''asc'' / ''desc'' como segundo parámetro)

Array.prototype.mergeSort = function(sortKey, direction){
  var unsortedArray = this;
  if(unsortedArray.length < 2) return unsortedArray;

  var middle = Math.floor(unsortedArray.length/2);
  var leftSubArray = unsortedArray.slice(0,middle).mergeSort(sortKey, direction);
  var rightSubArray = unsortedArray.slice(middle).mergeSort(sortKey, direction);

  var sortedArray = merge(leftSubArray, rightSubArray);
  return sortedArray;

  function merge(left, right) {
    var combined = [];
    while(left.length>0 && right.length>0){
      var leftValue = (sortKey ? left[0][sortKey] : left[0]);
      var rightValue = (sortKey ? right[0][sortKey] : right[0]);
      combined.push((direction === ''desc'' ? leftValue > rightValue : leftValue < rightValue) ? left.shift() : right.shift())
    }
    return combined.concat(left.length ? left : right)
  }
}

Puede probar esto usted mismo al soltar el fragmento de arriba en la consola de su navegador y luego intentar:

var x = [2,76,23,545,67,-9,12];
x.mergeSort(); //[-9, 2, 12, 23, 67, 76, 545]
x.mergeSort(undefined, ''desc''); //[545, 76, 67, 23, 12, 2, -9]

O ordene basado en un campo específico en una matriz de objetos:

var y = [
  {startTime: 100, value: ''cat''},
  {startTime: 5, value: ''dog''},
  {startTime: 23, value: ''fish''},
  {startTime: 288, value: ''pikachu''}
]
y.mergeSort(''startTime'');
y.mergeSort(''startTime'', ''desc'');

Answer 5

Así que necesitaba un tipo estable para mi aplicación React + Redux, y la respuesta de Vjeux aquí me ayudó. Sin embargo, mi solución (genérica) parece diferente a las otras que veo hasta ahora, así que la estoy compartiendo en caso de que alguien más tenga un caso de uso coincidente:

• Realmente solo quiero tener algo similar a la API sort() , donde puedo pasar una función de comparación.
• A veces puedo ordenar en el lugar, y a veces mis datos son inmutables (porque Redux) y necesito una copia ordenada en su lugar. Entonces necesito una función de clasificación estable para cada caso de uso.
• ES2015.

Mi solución es crear una matriz de indices tipeados, luego usar una función de comparación para ordenar estos índices en función de la matriz ordenada. Luego, podemos usar los indices ordenados para ordenar la matriz original o crear una copia ordenada en una sola pasada. Si eso es confuso, piénselo de esta manera: donde normalmente pasaría una función de comparación como:

(a, b) => { 
  /* some way to compare a and b, returning -1, 0, or 1 */ 
};

Ahora usa en su lugar:

(i, j) => { 
  let a = arrayToBeSorted[i], b = arrayToBeSorted[j]; 
  /* some way to compare a and b, returning -1 or 1 */
  return i - j; // fallback when a == b
}

La velocidad es buena; básicamente es el algoritmo de clasificación incorporado, más dos pasos lineales al final y una capa adicional de sobrecarga indirecta del puntero.

Feliz de recibir comentarios sobre este enfoque. Aquí está mi implementación completa de esto:

/**
 * - `array`: array to be sorted
 * - `comparator`: closure that expects indices `i` and `j`, and then
 *   compares `array[i]` to `array[j]` in some way. To force stability,
 *   end with `i - j` as the last "comparison".
 * 
 * Example:
 * ```
 *  let array = [{n: 1, s: "b"}, {n: 1, s: "a"}, {n:0, s: "a"}];
 *  const comparator = (i, j) => {
 *    const ni = array[i].n, nj = array[j].n;
 *    return ni < nj ? -1 :
 *      ni > nj ? 1 :
 *        i - j;
 *  };
 *  stableSortInPlace(array, comparator);
 *  // ==> [{n:0, s: "a"}, {n:1, s: "b"}, {n:1, s: "a"}]
 * ```
 */
function stableSortInPlace(array, comparator) {
  return sortFromIndices(array, findIndices(array, comparator));
}

function stableSortedCopy(array, comparator){
  let indices = findIndices(array, comparator);
  let sortedArray = [];
  for (let i = 0; i < array.length; i++){
    sortedArray.push(array[indices[i]]);
  }
  return sortedArray;
}

function findIndices(array, comparator){
  // Assumes we don''t have to worry about sorting more than 
  // 4 billion elements; if you know the upper bounds of your
  // input you could replace it with a smaller typed array
  let indices = new Uint32Array(array.length);
  for (let i = 0; i < indices.length; i++) {
    indices[i] = i;
  }
  // after sorting, `indices[i]` gives the index from where
  // `array[i]` should take the value from, so to sort
  // move the value at at `array[indices[i]]` to `array[i]`
  return indices.sort(comparator);
}

// If I''m not mistaken this is O(2n) - each value is moved
// only once (not counting the vacancy temporaries), and 
// we also walk through the whole array once more to check
// for each cycle.
function sortFromIndices(array, indices) {
  // there might be multiple cycles, so we must
  // walk through the whole array to check.
  for (let k = 0; k < array.length; k++) {
    // advance until we find a value in
    // the "wrong" position
    if (k !== indices[k]) {
      // create vacancy to use "half-swaps" trick,
      // props to Andrei Alexandrescu
      let v0 = array[k];
      let i = k;
      let j = indices[k];
      while (j !== k) {
        // half-swap next value
        array[i] = array[j];
        // array[i] now contains the value it should have,
        // so we update indices[i] to reflect this
        indices[i] = i;
        // go to next index
        i = j;
        j = indices[j];
      }
      // put original array[k] back in
      // and update indices
      array[i] = v0;
      indices[i] = i;
    }
  }
  return array;
}

Answer 6

Como busca algo estable, el tipo de combinación debería funcionar.

http://www.stoimen.com/blog/2010/07/02/friday-algorithms-javascript-merge-sort/

El código se puede encontrar en el sitio web de arriba:

function mergeSort(arr)
{
    if (arr.length < 2)
        return arr;

    var middle = parseInt(arr.length / 2);
    var left   = arr.slice(0, middle);
    var right  = arr.slice(middle, arr.length);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

EDITAR:

De acuerdo con esta post , parece que Array.Sort en algunas implementaciones utiliza un tipo de fusión.

Answer 7

El recuento de ordenaciones es más rápido que la ordenación combinada (se realiza en el tiempo O (n)) y está destinado a ser utilizado en enteros.

Math.counting_sort = function (m) {
    var i
    var j
    var k
    var step
    var start
    var Output
    var hash
    k = m.length
    Output = new Array ()
    hash = new Array ()
    // start at lowest possible value of m
    start = 0
    step = 1
    // hash all values
    i = 0
    while ( i < k ) {
        var _m = m[i]
        hash [_m] = _m
        i = i + 1
    }
    i = 0
    j = start
    // find all elements within x
    while ( i < k ) {
        while ( j != hash[j] ) {
            j = j + step
        }
        Output [i] = j
        i = i + 1
        j = j + step
    }
    return Output
}

Ejemplo:

var uArray = new Array ()<br/>
var sArray = new Array ()<br/><br/>
uArray = [ 10,1,9,2,8,3,7,4,6,5 ]<br/>
sArray = Math.counting_sort ( uArray ) // returns a sorted array

Answer 8

Es posible obtener una clasificación estable a partir de una función de clasificación no estable.

Antes de ordenar, obtienes la posición de todos los elementos. En su condición de clasificación, si ambos elementos son iguales, entonces ordena por posición.

Tada! Tienes un tipo estable.

He escrito un artículo sobre esto en mi blog si desea saber más sobre esta técnica y cómo implementarla: http://blog.vjeux.com/2010/javascript/javascript-sorting-table.html

Answer 9

Puede usar el siguiente relleno sintético para implementar una ordenación estable independientemente de la implementación nativa, según la afirmación hecha en esta respuesta :

// ECMAScript 5 polyfill
Object.defineProperty(Array.prototype, ''stableSort'', {
  configurable: true,
  writable: true,
  value: function stableSort (compareFunction) {
    ''use strict''

    var length = this.length
    var entries = Array(length)
    var index

    // wrap values with initial indices
    for (index = 0; index < length; index++) {
      entries[index] = [index, this[index]]
    }

    // sort with fallback based on initial indices
    entries.sort(function (a, b) {
      var comparison = Number(this(a[1], b[1]))
      return comparison || a[0] - b[0]
    }.bind(compareFunction))

    // re-map original array to stable sorted values
    for (index = 0; index < length; index++) {
      this[index] = entries[index][1]
    }
    
    return this
  }
})

// usage
const array = Array(500000).fill().map(() => Number(Math.random().toFixed(4)))

const alwaysEqual = () => 0
const isUnmoved = (value, index) => value === array[index]

// not guaranteed to be stable
console.log(''sort() stable?'', array
  .slice()
  .sort(alwaysEqual)
  .every(isUnmoved)
)
// guaranteed to be stable
console.log(''stableSort() stable?'', array
  .slice()
  .stableSort(alwaysEqual)
  .every(isUnmoved)
)

// performance using realistic scenario with unsorted big data
function time(arrayCopy, algorithm, compare) {
  var start
  var stop
  
  start = performance.now()
  algorithm.call(arrayCopy, compare)
  stop = performance.now()
  
  return stop - start
}

const ascending = (a, b) => a - b

const msSort = time(array.slice(), Array.prototype.sort, ascending)
const msStableSort = time(array.slice(), Array.prototype.stableSort, ascending)

console.log(''sort()'', msSort.toFixed(3), ''ms'')
console.log(''stableSort()'', msStableSort.toFixed(3), ''ms'')
console.log(''sort() / stableSort()'', (100 * msSort / msStableSort).toFixed(3) + ''%'')

Al ejecutar las pruebas de rendimiento implementadas anteriormente, stableSort() parece ejecutarse a aproximadamente el 57% de la velocidad de sort() en la versión 59-61 de Chrome.

El uso de .bind(compareFunction) en la función anónima envuelta dentro de stableSort() aumentó ese rendimiento relativo de aproximadamente 38% al evitar una referencia de ámbito innecesaria para compareFunction en cada llamada asignándola al contexto en su lugar.

Actualizar

Se cambió el operador ternario a cortocircuito lógico, que tiende a tener un mejor rendimiento en promedio (parece hacer una diferencia de 2-3% en la eficiencia).

Answer 10

Sé que esta pregunta ha sido respondida por un tiempo, pero tengo una buena implementación de tipo de fusión estable para Array y jQuery en mi portapapeles, así que la compartiré con la esperanza de que algunos buscadores futuros puedan encontrarla útil.

Le permite especificar su propia función de comparación al igual que la implementación normal de Array.sort .

Implementación

// Add stable merge sort to Array and jQuery prototypes
// Note: We wrap it in a closure so it doesn''t pollute the global
//       namespace, but we don''t put it in $(document).ready, since it''s
//       not dependent on the DOM
(function() {

  // expose to Array and jQuery
  Array.prototype.mergeSort = jQuery.fn.mergeSort = mergeSort;

  function mergeSort(compare) {

    var length = this.length,
        middle = Math.floor(length / 2);

    if (!compare) {
      compare = function(left, right) {
        if (left < right)
          return -1;
        if (left == right)
          return 0;
        else
          return 1;
      };
    }

    if (length < 2)
      return this;

    return merge(
      this.slice(0, middle).mergeSort(compare),
      this.slice(middle, length).mergeSort(compare),
      compare
    );
  }

  function merge(left, right, compare) {

    var result = [];

    while (left.length > 0 || right.length > 0) {
      if (left.length > 0 && right.length > 0) {
        if (compare(left[0], right[0]) <= 0) {
          result.push(left[0]);
          left = left.slice(1);
        }
        else {
          result.push(right[0]);
          right = right.slice(1);
        }
      }
      else if (left.length > 0) {
        result.push(left[0]);
        left = left.slice(1);
      }
      else if (right.length > 0) {
        result.push(right[0]);
        right = right.slice(1);
      }
    }
    return result;
  }
})();

Ejemplo de uso

var sorted = [
  ''Finger'',
  ''Sandwich'',
  ''sandwich'',
  ''5 pork rinds'',
  ''a guy named Steve'',
  ''some noodles'',
  ''mops and brooms'',
  ''Potato Chip Brand® chips''
].mergeSort(function(left, right) {
  lval = left.toLowerCase();
  rval = right.toLowerCase();

  console.log(lval, rval);
  if (lval < rval)
    return -1;
  else if (lval == rval)
    return 0;
  else
    return 1;
});

sorted == ["5 pork rinds", "a guy named Steve", "Finger", "mops and brooms", "Potato Chip Brand® chips", "Sandwich", "sandwich", "some noodles"];

Answer 11

También puedes usar Timsort:

Implementación de GPL 3 JavaScript . Empaquetado como Array.prototype.timsort. Parece ser una reescritura exacta del código de Java.

Implementación de dominio público. Como un tutorial, el código de muestra solo muestra su uso con enteros.

Timsort es un híbrido altamente optimizado de ordenación mergesort y shuffle y es el algoritmo de clasificación predeterminado en Python y en Java (1.7+). Es un algoritmo complicado, ya que utiliza diferentes algoritmos para muchos casos especiales. Pero, como resultado, es extremadamente rápido en una amplia variedad de circunstancias. Ver: https://en.wikipedia.org/wiki/Timsort

Answer 12

Tengo que ordenar matrices multidimensionales por una columna arbitraria, y luego por otra. Yo uso esta función para ordenar:

function sortMDArrayByColumn(ary, sortColumn){

    //Adds a sequential number to each row of the array
    //This is the part that adds stability to the sort
    for(var x=0; x<ary.length; x++){ary[x].index = x;}

    ary.sort(function(a,b){
        if(a[sortColumn]>b[sortColumn]){return 1;}
        if(a[sortColumn]<b[sortColumn]){return -1;}
        if(a.index>b.index){
            return 1;
        }
        return -1;
    });
}

Tenga en cuenta que ary.sort nunca devuelve cero, que es donde algunas implementaciones de la función "ordenar" toman decisiones que podrían no ser correctas.

Esto es bastante rápido, también.

Answer 13

Un simple mergeSort de http://www.stoimen.com/blog/2010/07/02/friday-algorithms-javascript-merge-sort/

var a = [34, 203, 3, 746, 200, 984, 198, 764, 9];

function mergeSort(arr)
{
    if (arr.length < 2)
         return arr;

    var middle = parseInt(arr.length / 2);
    var left   = arr.slice(0, middle);
    var right  = arr.slice(middle, arr.length);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
     var result = [];

    while (left.length && right.length) {
         if (left[0] <= right[0]) {
             result.push(left.shift());
         } else {
            result.push(right.shift());
         }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

console.log(mergeSort(a));

Answer 14

Versión algo más corta de lo mismo utilizando las funciones ES2017 como funciones de flecha y desestructuración:

Función

var stableSort = (arr, compare) => arr
  .map((item, index) => ({item, index}))
  .sort((a, b) => compare(a.item, b.item) || a.index - b.index)
  .map(({item}) => item)

Acepta la matriz de entrada y la función de comparación:

stableSort([5,6,3,2,1], (a, b) => a - b)

También devuelve una matriz nueva en lugar de ordenar en Array.sort() como la función incorporada Array.sort() .

Prueba

Si tomamos la siguiente matriz de input , inicialmente ordenada por weight :

// sorted by weight
var input = [
  { height: 100, weight: 80 },
  { height: 90, weight: 90 },
  { height: 70, weight: 95 },
  { height: 100, weight: 100 },
  { height: 80, weight: 110 },
  { height: 110, weight: 115 },
  { height: 100, weight: 120 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 100, weight: 135 },
  { height: 75, weight: 140 },
  { height: 70, weight: 140 }
]

Luego, stableSort por height usando stableSort :

stableSort(input, (a, b) => a.height - b.height)

Resultados en:

// Items with the same height are still sorted by weight 
// which means they preserved their relative order.
var stable = [
  { height: 70, weight: 95 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 70, weight: 140 },
  { height: 75, weight: 140 },
  { height: 80, weight: 110 },
  { height: 90, weight: 90 },
  { height: 100, weight: 80 },
  { height: 100, weight: 100 },
  { height: 100, weight: 120 },
  { height: 100, weight: 135 },
  { height: 110, weight: 115 }
]

Sin embargo, ordenando la misma matriz de input usando el Array.sort() (en Chrome / NodeJS):

input.sort((a, b) => a.height - b.height)

Devoluciones:

var unstable = [
  { height: 70, weight: 140 },
  { height: 70, weight: 95 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 75, weight: 140 },
  { height: 80, weight: 110 },
  { height: 90, weight: 90 },
  { height: 100, weight: 100 },
  { height: 100, weight: 80 },
  { height: 100, weight: 135 },
  { height: 100, weight: 120 },
  { height: 110, weight: 115 }
]

Recursos

• Wikipedia
• Array.sort()
• JSFiddle