応用情報技術者試験の学習メモ アルゴリズム＜整列編＞

徹底攻略 応用情報技術者教科書 平成27年度 (Tettei Kouryaku JOHO SHORI)

 今日は、探索アルゴリズムに続いて整列アルゴリズムをまとめました。

まずは基本となる

１．バブルソート

２．挿入ソート

３．選択ソート

を学習してから、応用となる

４．クイックソート

５．シェルソート

６．ヒープソート

７．マージソート

を学習します。

 １．バブルソート(交換法)

配列の端から順に隣り合う要素を比較して、大小の順が逆であれば要素を交換する操作を繰り返していくアルゴリズム。

平均比較回数	n(n-1)/2
計算量	O(n2)

２．挿入ソート

整列された配列に、新たに要素を一つずつ適切な位置に挿入する操作を繰り返すアルゴリズム。

・ほとんど整列済みのデータに対しては高速

平均比較回数	n(n-1)/2以下
計算量	O(n2)

３．選択ソート

未整列の個所から最大値（または最小値）を検索して、それを配列の先頭要素と交換していくアルゴリズム。

平均比較回数	n(n-1)/2
計算量	O(n2)

４．クイックソート

最初に中間的な基準値を決めて、基準値よりも大きな値と小さな値で振り分け分割する。分割した部分列の中で再び基準値を決めて、同様の操作で再帰的に分割を繰り返していくアルゴリズム。バブルソートの応用。

・ランダムに並んだ列を整列させる速度は高速

・逆にすでに整列してあるデータでは非効率となり、最悪の場合計算量はO(n²)となる。

計算量	O(nlog n)

５．シェルソート

ある適当な間隔おきに取り出した要素からなる部分列を挿入ソートで整列し、さらに間隔を狭めて同様の操作を繰り返し、間隔が１になったら最後に全体に挿入ソートを適用して完全に整列させるアルゴリズム。

挿入ソートの応用。名前は開発者ドナルド・シェルから。

ランダムなデータを間隔をあけてソートしておき、ほとんど整列されたデータ全体に最後に挿入ソートを適用する。「ほとんど整列されたデータに対して高速」という挿入ソートの特徴を考慮したアルゴリズムとなっている。

計算量	O(nlog n)

６．ヒープソート

未整列のリストでヒープ（完全２分木）を構成し、この根から最大値（または最小値）を取り出して整列済みの列に移すという操作を繰り返して、未整列部分をなくしていくアルゴリズム。

選択ソートの応用。

計算量	O(nlog n)

７．マージソート（併合）

未整列のデータを前半と後半に分ける分割作業を繰り返し、大きさが１になるまで分割する。その後分割した前半の列と後半の列のそれぞれの要素の先頭を比較しマージして、整列済みのデータ列をつくっていく。

・マージするために多くの領域が必要で、メモリを多く消費するのが欠点

計算量	O(nlog n)

アルゴリズムはあいまいにせずにしっかり覚えよう。

イメージできなければ、実際にプログラミングしてみるといいかも。

ウィキ先生のページに動くイメージ図があるので覚えられなければ参考に見てみるといいと思います。

私は動画で覚えます。

……覚えられるかな。orz

================================================

応援クリックお願いします☆　<m(__)m>

にほんブログ村

にほんブログ村

スポンサーリンク