Title：整列アルゴリズム
３つの基本整列法とその特徴
| バブルソート | 隣り合う要素の値を比較し、大小関係が逆転となっていれば交換する。この比較・交換の操作を必要がなくなるまで繰り返す。隣接交換法ともいう。 | 隣り合う |
| 単純選択法 | 未整列の要素の中から最も小さい（大きい）要素を選択し、未整列部分の先頭の要素と入れ替える。この操作を最後から2番目の場所に正しい要素が入るまで繰り返す。 | 未整列の最少要素 |
| 単純挿入法 | 未整列要素の並びの先頭の要素を取出し、その要素を整列済み要素の中の正しい位置に挿入していく。 | 未整列の先頭を挿入 |
| 比較回数 | データ数ｎのとき n(ｎ－１）/２ |
| 計算量 | 最悪の場合O（ｎ?） 最良の場合O（ｎ） |
整列法の考え方
| 遂次添加法 | ｎ個の要素を整列する過程で、（ｋ－１）個が整列済みであるとき、それに１つの要素を加えて整列済みの要素をｋ個にし、これを、ｋ＝２，３，４、…、ｎまで繰り返す。バブルソート、単純選択ソート、単純挿入法は基づいた整列法である。 |
| 分割統治法 | 大きな問題を小さな問題に分割し、各問題ごとに求めた解を結合することによって、全体の解を求めようとする考えです。ここで分割とは、対象とする集合や定義領域を分けるということで、分割処理の多くは再帰的な処理によって行われる。クイックソートやマージソートはこれに基づいた整列法である。 |
| データ構造の利用 | 整列の効率を上げるためにデータ構造を利用する。ヒープソート。単純挿入法でも２分検索木で表現することで、計算量がO（ｎｌｏｇ?ｎ）となる。 |
高速な整列アルゴリズム
| クイックソート | 整列対象要素の中から中間的な基準値を決め、その基準値より大きな値の要素を集めた区分と、小さな値の要素を集めた区分とに整列対象要素を分割します。次に、それぞれの区分の中で再度基準を決め、同様の処理を要素数が１つになるまで繰り返し行う方法 | 基準値で分割 |
| ヒープソート | 根と節（heap） | 根と節（heap）順序木 |
| マージソート | 分割してマージソート |