今回の記事は応用情報のアルゴリズム分野でよく聞かれるソート系の処理です。午前試験では用語やそのソートの意味を問われる問題が出題されることがあります。午後試験ではプログラミングの分野で、ソートがどのように実装されているかを問う問題が出題されているイメージです。応用情報を受ける方は是非参考にしてみてください。
ソートまとめ
バブルソート
隣り合うものの大小で入れ替える。
配列長さがnの場合、計算量はn^2。
挿入ソート
1つの要素よりでかいか大きいかで順番に挿入していく。
計算量n^2。
選択ソート
要素の中の最小・最大値のどちらかでその要素を左詰めしていく。
計算量n^2。
B木
B木は、木構造のデータ構造に分類されます。１つの節が複数の子を持つことができる多分木をベースとし、根から葉までの深さがほぼ一定であるバランス木です。階層の深さが同じになるように，ノードの分割と併合を行う。
シェルソート
ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、間隔が1になるまでこれを繰り返す。
計算量nlogn。
クイックソート
クイックソート中間的な基準値を決め、それよりも大きな値区分と小さな値区分に振り分ける。次に、それぞれの区分の中で同様な処理を繰り返す。
計算量nlogn。
ヒープソート
ヒープソートでは，未整列の部分を順序木に構成し、そこから最大値又は最小値を取り出して既整列の部分に移す。この操作を繰り返して、未整列部分を縮めていく。
今回の記事は以上です。他にもサイト内是非みていってください。
コメント