メモログ

💡 Personal notes about anything I'm interested in

n^2 sort algorithms again

O(n^2)の計算量で実行するソートアルゴリズムについては、Bubble Sort in JavaScript(バブルソート)Insertion Sort in JavaScript(挿入ソート)Selection Sort in JavaScript(選択ソート)にて扱ったのだけど、完全に忘れてしまったので、もう一度確認する。

  • バブルソート:配列の左側から隣り同士を比較して、大きい方を右にする。右側に完成したソートができる
  • 選択ソート:配列の左側から始めて、一番小さい値を選んで一番左に移す。左側に完成したソートができる
  • 挿入ソート:配列の左側から始めて、左側に完成したソート結果に対して新しい値を適切な場所に挿入する

JavaScriptにおけるソートはArray.prototype.sort についてで扱ったようにsortメソッドがO(n log n)の計算量で実行してくれるので、実践でO(n^2)のソートを使うことはないけど。

というメモ。