ソートアルゴリズム
配列[3,1,4,2]の並べ替えを例に、ソートアルゴリズムについて学習しましょう。
1. バブルソート
隣り合う要素を比較して、大小の順序が逆であれば左右を入れ替えることを繰り返すアルゴリズム。
例) [3,1,4,2]
→ [1,3,4,2] (最も左の3,1を比較して、左右を入れ替え)
→ [1,3,4,2] (次に3,4を比較して、ここは順番通りなのでそのまま)
→ [1,3,2,4] (2,4を比較して、左右を入れ替え)
→ [1,3,2,4] (1度目の比較が右端まで行われたので、再度左に戻り1,3を比較)
→ [1,2,3,4] (次に2,3を比較し、左右を入れ替え)
→ [1,2,3,4] (この後右端まで比較を行い2週目終了、さらに3週目を終え変更点がないのでソート終了)
配列の長さがnの時、1週当たりの左右の入れ替え数がnに比例し、さらに周回する回数もnに比例するので、計算量は$O(n^2)$となります。
2.挿入ソート
整列された列に、新たな要素を一つずつ適切な位置に挿入する操作を繰り返すアルゴリズム。
例) [3,1,4,2] ("3"を固定して考える)
→ [1,3,4,2] (1は固定した3よりも大きいので3よりも手前に挿入)
→ [1,3,4,2] (4は固定した1,3よりも大きいのでそのまま)
→ [1,2,3,4] (2は固定した1,3の間なのでこの場所に挿入)
配列の長さがnの時、挿入回数はnに比例します。さらに、挿入のたびに前方から線形探索が行われているので、そちらの計算量もnに比例します。よって、計算量は$O(n^2)$となります。
3.選択ソート
未整列の部分列から最大値または最小値を検索し、それを繰り返すアルゴリズム。
例) [3,1,4,2]
→ [1,3,4,2] (3,1,4,2のうち最小の1を最左に移動)
→ [1,2,3,4] (3,4,2のうち最小の2を左に移動)
→ [1,2,3,4] (3,4のうちの最小は3なのでそのまま)
配列の長さがnの時、最小値を求める回数はnに比例します。さらに、最小値を求める際に線形探索が行われているので、そちらの計算量もnに比例します。よって、計算量は$O(n^2)$になります。
4.クイックソート
最初に中間的な基準値を決めて、それよりも大きな値を集めた部分列と小さな値を集めた部分列に要素を振り分ける操作を繰り返すアルゴリズム。
例) [3,1,4,2] (3を基準値にとる)
→ [1,2,3,4](3より小さいものは3より左へ、大きいものは右へ)
今回は一回の操作で終わりですが、通常は左右それぞれで新しく基準値を決め、左右の入れ替えがなくなるまでこの作業を繰り返します。
配列の長さがnの時、左右に要素を振り分ける操作は平均で$log_2(n)$回行われます。さらに、それぞれにおいて線形探索が行われるので、そちらの計算量もnに比例します。よって、計算量は$O(n*log(n))$となります。
5.シェルソート
シェルソートは、一定間隔おきに(7つとび、3つとびなど)要素を取り出し、それぞれを整列させ、間隔を狭くしていくアルゴリズム。15,7,3,1と$O(2^n-1$のn)を小さくしていく形で間隔が減っていく。こちらのサイトが分かりやすい。
シェルソートの計算量は難しい。。。とりあえず$O(n*log(n))$で覚えておきましょう。
詳しくは参考サイトを。
6.ヒープソート
これも難しい。こちらの動画を参考にしました。計算量はn回最大値を求める作業をしていて、二分木を使っているから$log_2(n)$をかけて$O(n*log(n))$って感じです。消費するメモリが小さいらしい。
7.マージソート
まずはデータ列を2分割する作業を1つずつになるところまで繰り返す。そのあと、分割した前半と後半をマージ(併合)する作業を繰り返す。こちらも動画がわかりやすかった。計算量は$O(n*log(n))$で他と比べても早いが、メモリを多く使う点が欠点。
結論
バブルソート、挿入ソート、選択ソートの基本3ソートの計算量は$O(n^2)$。
クイックソート、シェルソート、ヒープソート、マージソートの応用4ソートの計算量は$O(n*log(n))$と覚えておきましょう。