問題
あるデータ列を整理したら状態0から順に状態1, 2, ・・・, Nへと推移した。整列に使ったアルゴリズムはどれか。
状態0 3, 5, 9, 6, 1, 2
状態1 3, 5, 6, 1, 2, 9
状態2 3, 5, 1, 2, 6, 9
・
・
・
状態N 1, 2, 3, 5, 6, 9
ア クイックソート
イ 挿入ソート
ウ バブルソート
エ ヒープソート
解説
クイックソート
クイックソートは、1960年にアントニー・ホーアが開発したソートのアルゴリズムです。分割統治法の一種であり、平均計算量がO(n log n)と高速なため、実用上最もよく使われるソートアルゴリズムの一つです。
クイックソートは、以下の手順で行われます。
- ピボットと呼ばれる基準値を決めます。
- ピボットより小さい要素を配列の先頭側に集め、ピボットより大きい要素のみを含む区間とそれ以外に分割します。
- 分割された区間に対し、再びピボットの選択と分割を行います。
- 分割区間が整列済みなら再帰を打ち切ります。
例えば、以下の配列をクイックソートすると、以下のようになります。
[5, 2, 3, 1, 4]
- ピボットに配列の中央値である3を設定します。
- 3より小さい要素である2と1を配列の先頭側に移動します。
- 3より大きい要素である5と4を配列の後ろ側に移動します。
- 分割された2つの区間を再びクイックソートします。
[1, 2, 3, 4, 5]
このように、クイックソートでは、ピボットを境界として配列を分割し、再帰的に分割された区間をソートすることで、全体をソートします。
クイックソートの計算量は、以下のようになります。
- 最良計算量：O(n log n)
- 平均計算量：O(n log n)
- 最悪計算量：O(n^2)
最良計算量は、ピボットが常に配列の中央値となる場合です。平均計算量は、ピボットがランダムに選択される場合です。最悪計算量は、ピボットが常に配列の最も小さい値または最も大きい値となる場合です。
クイックソートには、以下のような特徴があります。
- 高速なソートアルゴリズムである。
- 内部ソートである。
- 不安定ソートである。
内部ソートとは、ソート対象のデータを外部メモリに書き出さずに、内部メモリだけでソートを行う方法です。不安定ソートとは、ソート結果において、要素の順序が保持されないソート方法です。
クイックソートは、高速なソートアルゴリズムであるため、多くのプログラミング言語で標準ライブラリとして実装されています。また、クイックソートは、データベースや検索エンジンなどのアプリケーションでも広く使われています。
挿入ソート
挿入ソート（insertion sort）は、ソートのアルゴリズムの一つです。配列を「整列済み」と「未整列」の2つに分け、未整列な配列の要素を1つ取り出し、整列済みの配列の適切な位置に挿入するという手順を繰り返すことで、配列をソートします。
挿入ソートの時間計算量は平均・最悪ケースでともに O(n^2) であり、クイックソートやマージソートなどと比べると遅いです。しかし、アルゴリズムが単純で実装が容易であり、小さな配列に対しては高速です。また、挿入ソートでは、要素の順序が変化しない安定なソートです。
挿入ソートの動作は、以下のとおりです。
- 配列の要素を、昇順にソートされた配列と未ソートされた配列に分割する。
- 未ソートされた配列の要素を、1つずつ取り出す。
- 取り出した要素が、整列済み配列内のどの位置に挿入すればよいか、順番に比較していく。
- 挿入する位置を見つけたら、その位置に要素を挿入する。
- 2〜4を繰り返す。
挿入ソートでは、未ソートされた配列の要素を、1つずつ順番に取り出して、整列済み配列の適切な位置に挿入します。挿入する位置は、取り出した要素が、整列済み配列内のどの要素よりも小さいか、大きいかで判断します。取り出した要素が、整列済み配列内の要素よりも小さい場合は、その要素を後方へずらしていきます。
挿入ソートでは、配列の要素数が増えると、計算量が増加します。そのため、大きな配列をソートする場合は、クイックソートやマージソートなどのアルゴリズムの方が効率的です。
バブルソート
バブルソート（bubble sort）は、ソートのアルゴリズムの一つです。配列の隣り合う要素を比較し、大きい要素を後方に移動するという手順を繰り返すことで、配列をソートします。
バブルソートの時間計算量は平均・最悪ケースでともに O(n^2) であり、挿入ソートやシェルソートなどと比べると遅いです。しかし、アルゴリズムが単純で実装が容易であり、小さな配列に対しては高速です。また、バブルソートでは、要素の順序が変化しない安定なソートです。
バブルソートの動作は、以下のとおりです。
- 配列の要素を、昇順にソートされた配列と未ソートされた配列に分割する。
- 未ソートされた配列の要素を、1つずつ取り出す。
- 取り出した要素が、後方の要素よりも小さければ、その要素を後方に移動する。
- 2〜3を繰り返す。
バブルソートでは、配列の隣り合う要素を比較し、大きい要素を後方に移動します。大きい要素が後方に移動するたびに、配列の先頭から見てソート済みの要素が増えていきます。
バブルソートでは、配列の要素数が増えると、計算量が増加します。そのため、大きな配列をソートする場合は、クイックソートやマージソートなどのアルゴリズムの方が効率的です。
バブルソートの特徴は、以下のとおりです。
- アルゴリズムが単純で実装が容易である
- 小さな配列に対しては高速である
- 要素の順序が変化しない安定なソートである
バブルソートのデメリットは、以下のとおりです。
- 時間計算量が O(n^2) と遅い
- 大きい配列をソートする場合は効率的ではない
バブルソートの利用場面としては、以下のようなものが挙げられます。
- 小さな配列をソートする場合
- アルゴリズムの理解を深めるために、バブルソートを使う場合
ヒープソート
ヒープソート（heap sort）は、ソートのアルゴリズムの一つです。ヒープ構造を用いて、配列をソートします。
ヒープソートは、時間計算量が O(n log n) であり、クイックソートやマージソートなどと比べて高速です。また、ヒープソートは、要素の順序が変化しない安定なソートです。
ヒープソートの動作は、以下のとおりです。
- 配列をヒープ構造に変換する。
- ヒープのルート要素を、整列済み配列に追加する。
- ヒープの要素数を 1 減らす。
- ヒープ構造を再構築する。
- 2〜4を繰り返す。
ヒープソートは、配列をヒープ構造に変換し、ヒープのルート要素を、整列済み配列に追加するという手順を繰り返すことで、配列をソートします。ヒープ構造は、完全二分木であり、各ノードには、そのノードより小さいすべてのノードの値が、そのノードより大きいすべてのノードの値よりも小さいように構成されています。
ヒープソートでは、配列の要素数が増えても、計算量が O(n log n) で一定に保たれます。そのため、大きな配列をソートする場合にも効率的です。
ヒープソートの特徴は、以下のとおりです。
- 時間計算量が O(n log n) であり、高速である
- 要素の順序が変化しない安定なソートである
ヒープソートのデメリットは、以下のとおりです。
- アルゴリズムが複雑で実装が難しい場合がある
- 配列の要素をヒープ構造に変換する必要がある
ヒープソートの利用場面としては、以下のようなものが挙げられます。
- 大きな配列をソートする場合
- アルゴリズムの理解を深めるために、ヒープソートを使う場合
というわけで今回の問題を解いてみましょう。
今回の問題では未整列データのうち最も大きい値を端に寄せることを繰り返しているため、「ウ」のバブルソートが正解です。
