ソート(sort、整列)とはデータを条件によって並び替えを行う処理であり、様々な方法(アルゴリズム)がある。
ソートはアルゴリズムの差により演算回数(処理時間)が異なるため、情報処理技術者試験ではソートのアルゴリズムの問題と、演算回数(オーダ)についての出題がある。
主なソートのアルゴリズムには以下のようなものがあります。
| 名称 | オーダ | 処理概要 |
|---|---|---|
| バブルソート | n2 | 隣り合ったデータの比較と入替えを繰り返すことによって、小さな値のデータを次第に端の方に移していく方法 (平成21年秋期 基本情報技術者 問6より) |
| 選択ソート | n2 | データ中の最小値を求め、次にそれを除いた部分の中から最小値を求めるという操作を繰り返していく方法 (平成21年秋期 基本情報技術者 問6より) |
| 挿入ソート | 平均:n 最悪:n2 |
既に整列済みのデータ列の正しい位置に、データを追加する操作を繰り返していく方法 (平成21年秋期 基本情報技術者 問6より) |
| シェルソート | n1.25 | 一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、間隔が1になるまでこれを繰り返す方法 (平成20年春期 基本情報技術者 問13より) |
| マージソート | n log n | データ列を2分割し、2分割したデータ列に対し整列を行い、分割したデータ列を合わせて(マージして)整列を行う方法 (平成18年秋期 ソフトウェア開発技術者 問10より) |
| ヒープソート | n log n | 未整列の部分を順序木に構成し、そこから最大値又は最小値を取り出して既整列の部分に移す操作を繰り返して、未整列部分を縮めていく方法 (平成20年春期 基本情報技術者 問13より) |
| クイックソート | 平均:n log n 最悪:n2 |
適当な基準値を選び、それより小さい値のグループと大きい値のグループにデータを分割し、次に分割した各グループに対し同様の処理を繰り返していく方法 (平成21年秋期 基本情報技術者 問6より) |
ソートの演算回数を比べるときの対象となる処理は“データの比較演算”になります。これはCPUの処理の中で比較演算の処理に時間がかかるためです。
ただし、現実に複数のアルゴリズムのソートのプログラムを作成し処理時間を比較すると、メモリのアクセス回数などの影響が大きく関係します。特にクイックソートやマージソートのような再帰処理は再帰呼び出し時にCPUのレジスタの内容をスタックに退避する処理(メモリアクセスになります)があるため他のソートアルゴリズムと比べ処理時間が長くなることがあります。
戻る
一覧へ