アルゴリズム、計算量、レンダリングエンジン - daiiz

アルゴリズム、計算量、レンダリングエンジン

アルゴリズムと計算量

ソートアルゴリズム

いまは知らなくてもlist.sort()でできるけど

比較ソート

バブルソート

シェーカーソート

選択ソート

ヒープソート

挿入ソート

シェルソート

マージソート

クイックソート

非比較ソート

バケットソート

基数ソート

メモリ使用量

ラウダウ記号

最悪計算量

平均計算量

JavaScriptエンジン

Chrome: V8

Safari: JavaScript Core（JSC）

macのターミナルから呼び出すこともできるらしい

Firefox: Spider Monkey

Array.prototype.sort

https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

仕様は共通だが、実装はブラウザ（JavaScriptエンジン）ごとに異なる

V8最適化のための独自言語

エンジンと組み込み関数の実装がまとめて行われている

書き心地ははC++に近そう？

ティムソートが採用されている

https://ja.wikipedia.org/wiki/ティムソート

JSC

エンジン: 選択ソート

組み込み関数:

文字列: バケットソート

文字列以外: マージソート

Spider Monkey

マージソート

コード読もう daiiz.icon

関連

https://dev.to/bekmurzintimur/how-arrayprototypesort-works-3kcn