Implementação rápida e estável de algoritmos de ordenação em javascript

Eu estou olhando para classificar uma matriz de cerca de 200-300 objects, classificando em uma chave específica e uma determinada ordem (asc / desc). A ordem dos resultados deve ser consistente e estável.

Qual seria o melhor algoritmo para usar, e você poderia fornecer um exemplo de sua implementação em javascript?

Obrigado!

É possível obter uma sorting estável a partir de uma function de sorting não estável.

Antes de classificar, você obtém a posição de todos os elementos. Na sua condição de sorting, se ambos os elementos forem iguais, você classifica pela posição.

Tada! Você tem um tipo estável.

Eu escrevi um artigo sobre isso no meu blog se você quiser saber mais sobre essa técnica e como implementá-la: http://blog.vjeux.com/2010/javascript/javascript-sorting-table.html

Como você está procurando algo estável, a sorting de mesclagem deve ser feita.

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

O código pode ser encontrado no site acima:

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 acordo com este post , parece que o Array.Sort em algumas implementações usa uma sorting de mesclagem.

Eu sei que esta questão foi respondida há algum tempo, mas eu tenho uma boa implementação de ordenação de mesclagem estável para Array e jQuery na minha área de transferência, então eu vou compartilhar isso na esperança de que alguns futuros pesquisadores possam achar útil.

Ele permite que você especifique sua própria function de comparação como a implementação normal do Array.sort .

Implementação

 // 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; } })(); 

Exemplo 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"]; 

Você pode usar o seguinte polyfill para implementar uma sorting estável, independentemente da implementação nativa, com base na afirmação feita nesta resposta :

 // 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) + '%') 

Versão um pouco mais curta da mesma coisa usando resources ES2017 como funções de seta e desestruturação:

Função

 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) 

Aceita a matriz de input e compara a function:

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

Ele também retorna uma nova matriz em vez de fazer uma sorting no local, como a function interna Array.sort () .

Teste

Se tomarmos o seguinte array de input , inicialmente classificado 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 } ] 

Em seguida, classifique-o por height usando stableSort :

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

Resulta em:

 // 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 } ] 

No entanto, classificando a mesma matriz de input usando o Array.sort() (no Chrome / NodeJS):

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

Retorna:

 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
  • MDN
  • JSFiddle

O seguinte classifica a matriz fornecida, aplicando a function de comparação fornecida, retornando a comparação do índice original quando a function de comparação retorna 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; } 

O exemplo abaixo classifica uma matriz de nomes por sobrenome, mantendo a ordem de sobrenomes iguais:

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

Aqui está uma implementação estável. Ele funciona usando a sorting nativa, mas nos casos em que os elementos são comparados como iguais, você quebra os vínculos usando a posição do í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; }); } 

um teste não completo

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

outra resposta aludiu a isso, mas não postou o código.

mas, não é rápido de acordo com o meu benchmark . Eu modifiquei um tipo de mesclagem impl para aceitar uma function de comparação personalizada, e foi muito mais rápido.

Você também pode usar o Timsort. Este é um algoritmo realmente complicado (mais de 400 linhas, portanto não há código fonte aqui), então veja a descrição da Wikipedia ou use uma das implementações JavaScript existentes:

Implementação da GPL 3 . Empacotado como Array.prototype.timsort. Parece ser uma reescrita exata do código Java.

Implementação de domínio público Concebido como um tutorial, o código de exemplo mostra apenas seu uso com números inteiros.

O Timsort é um híbrido altamente otimizado do tipo mergesort e shuffle sort e é o algoritmo de sorting padrão no Python e no Java (1.7+). É um algoritmo complicado, já que usa algoritmos diferentes para muitos casos especiais. Mas, como resultado, é extremamente rápido sob uma ampla variedade de circunstâncias.

Um simples 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)); 

A contagem de sorting é mais rápida do que a ordenação por mesclagem (ela é executada no tempo O (n)) e destina-se ao uso em inteiros.

 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 } 

Exemplo:

 var uArray = new Array ()
var sArray = new Array ()

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

Eu tenho que ordenar matrizes multidimensionais por uma coluna arbitrária e depois por outra. Eu uso essa function para classificar:

 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; xb[sortColumn]){return 1;} if(a[sortColumn]b.index){ return 1; } return -1; }); } 

Observe que ary.sort nunca retorna zero, que é onde algumas implementações da function “sort” tomam decisões que podem não estar corretas.

Isso também é muito rápido.

Veja como você pode estender o object Array padrão JS com um método de protótipo utilizando MERGE SORT . Este método permite classificar uma chave específica (primeiro parâmetro) e uma ordem dada (‘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) } } 

Então, eu precisava de uma sorting estável para o meu aplicativo React + Redux, e a resposta de Vjeux aqui me ajudou. No entanto, minha solução (genérica) parece diferente das outras que eu vejo aqui até agora, então estou compartilhando no caso de alguém ter um caso de uso correspondente:

  • Eu realmente só quero ter algo semelhante à API sort() , onde eu posso passar uma function de comparação.
  • Às vezes eu posso classificar no local, e às vezes meus dados são imutáveis ​​(porque o Redux) e eu preciso de uma cópia ordenada em vez disso. Então eu preciso de uma function de sorting estável para cada caso de uso.
  • ES2015.

Minha solução é criar uma matriz tipificada de indices , em seguida, usar uma function de comparação para classificar esses índices com base na matriz a ser classificada. Em seguida, podemos usar os indices classificados para classificar a matriz original ou criar uma cópia classificada em uma única passagem. Se isso é confuso, pense desta maneira: onde você normalmente passaria uma function de comparação como:

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

Você agora usa:

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

A velocidade é boa; é basicamente o algoritmo de sorting embutido, mais dois passes lineares no final e uma camada extra de sobrecarga indireta de ponteiro.

Feliz por receber feedback sobre esta abordagem. Aqui está a minha implementação completa do mesmo:

 /** * - `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; }