L'ordinamento di Javascript è 'instabile' - come faccio a evitare questo?

Secondo lo MDN spec, la funzione sort() di Javascript è 'unstable' (non mantiene l'ordine di input per elementi identici).L'ordinamento di Javascript è 'instabile' - come faccio a evitare questo?

Ironia della sorte, al momento Firefox non lo implementa, ma a quanto pare Chrome.

Questo mi lascia un po 'un problema. Ho un set di elementi da ordinare - una volta ordinati mi piacerebbe contrassegnarli come 'ordinati' in modo che i tentativi successivi di ordinare non perdano molto tempo a scoprire che sono già ordinati (posso sganciarli se qualcosa cambia) .

Il problema è, la mia soluzione per questo è il ritorno '0' nella mia funzione di confronto, ma che significa che sto semplicemente tornare 'equivalenza' per ogni elemento e si può (e vuole) essere mescolate.

Questo dimostra il problema (fiddle here)

<head> 
    <script> 
     var firsttime=true; 
     function test() { 
      debugger; 
      var elements = document.getElementById('test').children; 
      var sortMe = []; 
      for (var i=0; i<elements.length; i++) 
       sortMe.push(elements[i]); 
      sortMe.sort(function(a, b) { 
       if (firsttime) { 
        if (a.innerText < b.innerText) return -1; 
        else if (a.innerText > b.innerText) return 1; 
        else return 0; 
       } else { 
        return 0; 
       } 
      }); 
      var parent = document.getElementById('test'); 
      parent.innerHTML = ""; 
      for(var i = 0, l = sortMe.length; i < l; i++) { 
       parent.appendChild(sortMe[i]); 
      } 
      firsttime=false; 
     } 
    </script> 
</head> 
<body> 
<div id=test> 
    <div>B</div> 
    <div>D</div> 
    <div>A</div> 
    <div>C</div> 
    <div>E</div> 
    <div>B</div> 
    <div>D</div> 
    <div>A</div> 
    <div>C</div> 
    <div>E</div> 
    <div>B</div> 
    <div>D</div> 
    <div>A</div> 
    <div>C</div> 
    <div>E</div> 
</div> 
<input type=button onclick=test()> 
</body>

Run su Chrome si vedrà l'elemento centrale del set muoversi sulle specie successive - questo non accade su Mozilla (almeno non la versione che ho avere qui).

Qualche idea su come posso aggirare questo senza dover ricorrere a OGNI volta ?? L'ordinamento effettivo è molto più complesso e ha centinaia di elementi da controllare, quindi richiede molto tempo che non voglio ripetere inutilmente?

Modificato per aggiungere: ho persino provato a utilizzare l'indice di array per forzare l'ordinamento dell'array in ordine, ma anche questo non funziona su Chrome. Sembra che Chrome utilizzi una variante di un Quicksort che scambia elementi nell'array "solo per il gusto di farlo"

Sembra che non abbia altra scelta che ricorrere ogni volta, saltare l'ordinamento interamente o implementare il mio algoritmo. ..

fonte

2013-09-02 shrewdlogarithm

Avete a disposizione una chiave di ordinamento secondaria che potrebbe fornire un ordine univoco? –

Nell'applicazione effettiva, l'ordinamento è un algoritmo complesso che esamina il contenuto DIV, quindi la ricerca di un ordinamento secondario sarebbe altrettanto lenta. Sto cominciando a pensare di contrassegnare il tutto come "pulito" o "sporco" e semplicemente non fare alcun tentativo di ordinare qualunque cosa a meno che non sia contrassegnato come "sporco" - Ho pensato solo in questo modo che avrei potuto solo ordinare i bit che avevano cambiato ... – shrewdlogarithm

A meno che ... non aggiungo una posizione di ordinamento agli elementi e lo usi invece - potrebbe funzionare ma è ancora "un po 'di lavoro" in contrapposizione a "nessun lavoro". La cosa instabile significa che devi fare "un po 'di lavoro", credo? – shrewdlogarithm

Ecco un esempio di ordinamento stabile di lavoro. Aggiunge un parametro extra per l'indice dell'oggetto originale che viene utilizzato se gli elementi sono "uguali". Il codice dovrebbe funzionare con qualsiasi browser in uso.

Si noti che è solo un esempio e deve essere modificato in base alle circostanze specifiche.

<script type="text/javascript"> 

// Return the text content of an element depending on 
// whether the textContent or innerText property is supported 
function getText(el) { 
    if (typeof el.textContent == 'string') { 
    return el.textContent; 
    } else if (typeof el.innerText == 'string') { 
    return el.innerText; 
    } else { 
    // gather text nodes and concatenate values 
    // trimmed as almost never used now 
    } 
} 


function sortEm(){ 

    // Get the elements to sort 
    var container = document.getElementById('container'); 
    var divs = container.getElementsByTagName('div'); 
    var els = []; 

    // Convert collection to an array, add the current index for the element 
    // as a data- property 
    for (var i=0, iLen=divs.length; i<iLen; i++) { 
    divs[i].setAttribute('data-sortIndex', i); 
    els[i] = divs[i]; 
    } 

    // Sort the array. If the textContent is equal, use 
    // the original index 
    els.sort(function(a, b) { 
    var aText = getText(a); 
    var bText = getText(b); 

    if (aText < bText) return -1; 
    if (aText > bText) return 1; 
    return a.getAttribute('data-SortIndex') - b.getAttribute('data-sortIndex'); 
    }) 

    // Modify the content 
    for (var j=0, jLen=els.length; j<jLen; j++) { 
    container.appendChild(els[j]); 
    } 
} 

</script> 

<div id="container"> 
    <div style="background-color: red;">0</div> 
    <div style="background-color: red;">2</div> 
    <div style="background-color: blue;">0</div> 
</div> 
<button onclick="sortEm()">Sort divs</button>

Il parametro aggiuntivo viene aggiunto come un attributo e potrebbe essere rimosso quando gli elementi vengono aggiunti al contenitore per mantenere le cose pulite.

fonte

2013-09-03 02:41:51 RobG

Oh, un'alternativa a quanto sopra è creare un oggetto e usare l'indice textContent + come nomi di proprietà e gli elementi come valori. Ordinare i nomi delle proprietà (la funzione di ordinamento dovrà dividere l'indice in modo che venga confrontato come un numero se tutto il resto è uguale), quindi utilizzare l'array ordinato per inserire gli elementi nell'ordine corretto. Questo metodo evita di aggiungere e rimuovere attributi e proprietà direttamente sugli elementi (molto preferito da alcuni). – RobG

L'ordinamento di Javascript è 'instabile' - come faccio a evitare questo?

risposta

Problemi correlati