日々勉強するものが多くて困っている新卒のwebエンジニアです。
SQL、アルゴリズム、コンピューターアーキテクチャーなど、何をどんな順番で勉強するべきかわからなくなったので、とりあえず一つ一つ学んだことをブログに書いていこうと思います。
最初の題材はアルゴリズム！しっかり勉強して行きたいと思います！
sort()メソッドを理解していなかった
先日ブートキャンプに参加しアルゴリズム問題を解いていました。
そこでsort()を使ってもいいとのことだったので活用して問題を解きましたが、全然うまく行きませんでした。
その場ではとりあえず解けずに終了...アルゴリズムについて勉強する前に、まずは普段使っているJSがどのようなメソッドを提供しているか知りたいと思いました。
問題を解いているときはconsole.logが使えずなぜ失敗していたかわからなかったのですが、以下のようなところで私の認識は間違っていました。
const array = [4, 1, 2, 10, 5];
const sortedArray = array.sort(); // [1, 2, 4, 5, 10]かな？
console.log(sortedArray); // [1, 10, 2, 4, 5]だった！
数字をそのままソートしているわけではなさそうですね。
ECMAを見てみると、一度ToStringを挟んでいるんですね。
変換してからは、ASCIIでのソートになります。
Perform ? Set(obj, ! ToString(𝔽(j)), sortedList[j], true).
MDNにも書いてある通り、数字のソートは以下のように比較する必要がありそうです。
const array = [4, 1, 2, 10, 5];
const compareNumbers = (a, b) => {
return a - b; // +の値を持つとaをbの後に並べる
};
const sortedArray = array.sort(compareNumbers); // [1, 2, 4, 5, 10]
sort()のアルゴリズム
使い方は分かりましたが、sort()ってどんなアルゴリズムを採択しているのでしょう？
まだ他のアルゴリズムがわかっていない状態ですが、とりあえず調べたいと思いました。
MDNにはアルゴリズムについては書かれていない。そこで調べてみると、JavaScriptを解析するエンジンによって異なるアルゴリズムを採っているとのことですね。
一般的にはChromeのV8エンジンを使うことが多いので、今回はV8エンジンのsort()について調べました。
V8のGitHubから以下のような記述を見つけました。
This file implements a stable, adapative merge sort variant called TimSort.
TimSort
TimSort、初めて聞きました。挿入ソートとマージソートを合わせたものなんですね。
上の記述にも書いている通り、
マージソートを元に実生活のデータに合わせた最適化を行った安定したソートがTimSort。
計算量でみると、最善はO(n),平均と最悪はO(nlogn)になります。
追加のメモリ消費はありますが、マージソートに比べると比較的に少ない安定したソートとのこと！
結論
これでsort()が何をしているかが大体はわかってきましたが、まだ今回出てきたマージソートや挿入ソートなどについて理解ができていません。
ということで次からは、早速いろんなソートについて調べていきます。
参考