JavascriptプログラムのArray.sort（）メソッドが不安定なのはなぜですか？ここで

Question

は私jsFiddleです：

//Change this variable to change the number of players sorted 
var numberOfPlayers = 15; 

var teams = []; 
var alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 

for(var a=0; a<numberOfPlayers; a++){ 
    updateStandings(); 
    teams.push(new Team(alphabet.charAt(a))); 
} 

console.log("Teams:"); 
for(var x=0; x<teams.length; x++){ 
    console.log(teams[x].name); 
} 

//Functions and such 
function updateStandings(){ 
    teams.sort(function(a, b) { 
    if(a.score == b.score){ 
     if(a.tiebreak == b.tiebreak){ 
     return teams.indexOf(a)-teams.indexOf(b); 
     }else{ 
     return b.tiebreak-a.tiebreak; 
     } 
    }else{ 
     return b.score-a.score; 
    } 
    }); 
} 

function Team(name){ 
    this.name = name; 
    this.score = 0; 
    this.tiebreak = 0; 
} 

私はこの問題を想定しjavascriptのソートが不安定だったことだった、と私の比較機能を変更しましたが、それはまだ動作しません。

Answer 1

JSの並べ替えは通常不安定なので、 §22.1.3.24 of the spec：

この配列の要素はソートされています。ソートが必ずしも安定しているとは限りません（つまり、equalを比較する要素が必ずしも元の順序にとどまるわけではありません）。あなたがindexOfを呼んでいるので

return teams.indexOf(a)-teams.indexOf(b); 

、それはアイテム（とそのインデックス）を検索します。あなたのチームは彼らの名前を除いて同じプロパティを使用して作成するので、実際にソートを実行する行があるさ

並べ替えの各繰り返し。並べ替えは配列を変更します（from MDN：配列の要素を配列にソートし、に配列を返します）。

ソート対象の配列内のアイテムを検索しているため、インデックスは各繰り返しで変更される可能性があります。正しく（相対的に言えば）完了すると、それで終わりのないソートを作り出すことができます。例えば

：ドキュメントによると

const data = [1, 3, 2, 4]; 
 
let reps = 0; 
 

 
data.sort((a, b) => { 
 
    console.log(data); 
 
    
 
    const ia = data.indexOf(a), ib = data.indexOf(b); 
 
    if (ia === ib || reps > 50) { 
 
    return 0; 
 
    } else if (ia < ib) { 
 
    return 1; 
 
    } else if (ib < ia) { 
 
    return -1; 
 
    }  
 
});

Answer 2

は、ソート方法が安定していることが必要とされていません。https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort一部のブラウザでは、それが安定している、いくつかありませんで。

あなたが試した方法ではなく、比較機能を変更する必要があります。その理由は、あなたが現在配列に

return teams.indexOf(a)-teams.indexOf(b); 

を比較することです。これは、以前の手順でaとbの順序が変更された場合、ソートルーチンはこれらの要素が最初に持っていた順序ではなく、この新しい順序を保持することを意味します。

解決方法はいくつかあります。たとえば、並べ替えの前に配列のコピーを作成し、このコピーでindexOfを実行できます。並べ替えを開始する前に要素が持つ順序を保持します。

しかし、あらかじめその注文を知っている場合は、この知識を使用することもできます。たとえば、チームをソートする前に名前でソートされている場合は、配列の位置ではなく文字列として名前を比較することができます。これは、最初のオプションよりもはるかに効率的です。

Answer 3

次のようにJSでの安定したソートへの一般的なアプローチは次のとおりです。

function stable_sort(array, sortfunc) { 
    function _sortfunc(a, b) { return sortfunc(array[a], array[b]) || a - b; } 

    return array.map((e, i) => i) . sort(_sortfunc) . map(i => array[i]); 
} 

これは、実際に行うことはインデックスのリストを並べ替えることです。次に、ソートされたインデックスのリストを元の配列に戻します。並べ替え関数は、それらのインデックスで配列内の値を比較するために書き換えられ、等しい場合はインデックス自体の比較にフォールバックします。

このアプローチでは、コード内の問題が回避されます。これは、並べ替え中の配列にindexOfルックアップを実行しているということです。

This questionは参考になります。