5

Array.prototype.sort私は最近、カスタム メソッドを使用して任意の時点で 2 つの値を比較し、それらを交換するかそのままにするかを決定する方法を誰かに説明したいと思いました。前の比較の結果を確認できるように、各比較中に配列をログに記録することにしました。配列をログに記録したとき、特定の時点での配列の状態にかなり奇妙な点があることに気付きました。

以下を仮定します。

var num = [ 2, 1, 8, 5, 3 ];

num.sort( comparator );

function comparator ( a, b ) {
    console.log( num ); // Current state of num
    return a - b; // Order values numerically
}

これは出力です：

[ 2, 1, 8, 5, 3 ] // Comparing 2 and 1
[ 1, 2, 8, 5, 3 ] // Comparing 2 and 8
[ 1, 2, 8, 5, 3 ] // Comparing 8 and 5
[ 1, 2, 8, 8, 3 ] // Comparing 2 and 5
[ 1, 2, 5, 8, 3 ] // Comparing 8 and 3
[ 1, 2, 5, 8, 8 ] // Comparing 5 and 3
[ 1, 2, 5, 5, 8 ] // Comparing 2 and 3

配列は適切にソートされています ( [ 1, 2, 3, 5, 8 ]) が、コレクション自体のいくつかのパスにまだ頭を悩ませています。

反復 4 で 8 が 2 回出現し、一時的に 5 が置き換えられるのはどうしてですか。そして再び、8 が 2 回出現し、2 回の反復後に 3 が一時的に置き換えられます。最後に、5 が 2 回表示され、最後の反復で 3 が一時的に置き換えられます。

上記のコードは Chrome で実行されたことに注意してください。

4

1 に答える 1

2

興味深いですが、それほど驚くべきことではありません。

この例では、単純な挿入ソート アルゴリズムを使用しているようです。

次のようなもの：

  • アイテムを入手 [1]
  • 下にあるアイテムが見つかるまで、その下にあるすべてのアイテムを 1 つ上に移動し、次にこのアイテムの上に置きます
  • アイテムを入手 [2]
  • 下にあるアイテムが見つかるまで、その下にあるすべてのアイテムを 1 つ上に移動し、次にそれをこのアイテムの上に置きます
  • アイテムを入手 [3]
  • (続き)

バブル ソート アルゴリズムを説明するとき、通常、各要素がその場所を見つけるまで配列に沿って交換されることを想像します。ただし、アイテムを交換するよりも一時変数に格納する方が効率的です。

于 2013-10-08T21:50:47.117 に答える