Hayato式！！　　応用情報技術者試験　　　　　　　　　～～アルゴリズム編その２～～

2022年11月4日 16:40

2⃣　整列アルゴリズム

整列っていうものは、あるデータをキーとなる値の順に並び変えることです。その整列には様々な種類があり、以下にその整列法がある。

選択ソートとは、整列されているデータの最小の値を選択しながら並び替えることです。また、計算するのにかかる量は要素の数をｎとするとｎ²と表すことができます。

バブルソートとは、データ内で隣り合う要素の大小を比べながら並び替えることです。計算量は、選択ソートと同様です！

クイックソートとは、データ内で適当な基準値を選んで、その基準値より大きな要素と小さな要素で分けながら整列していき、それを完了するまで延々と繰り返す。計算量は最大の時はｎ²、平均は ｎlog₂ｎと表せる。

挿入ソートとは、整列が完了している配列に対して、追加したい要素を適切な位置に挿入する整列方法である。計算量は選択ソートと同様。

シェルソートとは、とびっとびの要素の中に挿入ソートを適用して整列する手法である。計算量はｎの3分の2乗以下といわれています。

ヒープソートとは、ヒープの根が最大（最小）の値であることを利用して整列する方法である。計算量はｎlog₂ｎであらわせる。
また、午前試験などでよく聞かれる頻出テーマの一つ。

マージソートとは、整列済みの2つの配列を合体して1つにして整列するという手法です。計算量はヒープソートと同様。
これもまた、頻出テーマの一つである。

これで整列アルゴリズムは以上となります。
次回は再帰・文字列探索アルゴリズムになります。
よー－く過去問演習をして理解しておきましょう！！