JavaScript の sort関数 の内部動作を改めて理解してみる

JavaScriptの 配列をソートする実装はある程度覚えているのですが、おまじないのように書くことが多いので改めて整理してみました。

MDNの方にもしっかりと記載のある sort関数 ですが、
文面を見ても内部動作があまり理解できなかったので今回は動作を確認しました。

JavaScript Tutor で今回の実装の動きは 確認 できます

URLを開いたら、
Visualize Execution を実行してください。

では、詳細に入っていきます。
以下のような実装があったとします。
これは配列を昇順に並べる実装です。

var array = [1,10,3,100,7]
array.sort((a,b) => a - b)

まず一番最初の動作として、先頭二つの要素を比較します。

a - b = -9

符号がマイナスなので並び替える必要はなし。
次のステップに進みます。

次にインデックス1とインデックス2の配列の要素を比較します。

10 - 3 = 7

符号がプラスなので、並び替えが必要。

このとき暫定的に配列は

[1,3,10,100,7]

になります。

ただし、1と3のどちらが大きいのか分からないので再度比較する必要あり。

a = 1
b = 3

として再度比較する。

a - b = -2

なので、並び替える必要はなし

次のステップに進む。

インデックス2とインデックス3の配列の要素を比較します。

a - b = -90

符号がマイナスなので並び替えの必要なし。

インデックス3とインデックス4の配列の要素を比較します。

a - b = 93

符号がプラスなので、並び替えの必要あり。

暫定的に

[1,3,10,7,100]

となる。
ただし、7とその手前の配列 [1,3,10] とを大小比較していないため、再度検証が必要になる。

a = 10
b = 7

として

a - b = 3

なので並び替えの必要あり。

[1,3,7,10,100]

また、7とそれ以前の配列 [1,3]とを比較していないため、再度検証が必要になる。

a = 3
b = 7

とすると

a - b = -4

なので、これは並び替える必要なし。

ここで計算終了となり、結果として配列

[1,3,7,10,100]

が得られる。

降順ソート

array.sort((a,b) => b-a))

でも理屈は同じになります。

昇順ソートの場合、二つの要素を取り出し、それを比較し、
もし a-b の値がプラスであれば並び替える必要があり、
暫定的に並べ替えた後、その手前の配列とも一つ一つ値を検証して並び替えるのが
sort関数の動作となります。

シンプルな処理ではあるが、コードを見ただけだとあまり仕組みが理解できなかったので。
今回はまとめてみました。