Ｗｅｂ教材一覧＞
アルゴリズム
（ＢＯＫ大区分：１ 基礎理論、中区分：２ アルゴリズムとプログラミング、中区分：２ アルゴリズム）
アルゴリズムの例として、また実際に利用される処理にソート（整列）があります。ここでは、ソートの代表的な方法を紹介します。個々の方法へのリンク元でもあります。
アルゴリズム、選択整列法、バブルソート、シェルソート、順序づけ、計算量
|
バブルソート 分類：交換法、安定ソート 平均比較回数：ｎ(ｎ－１)／２ 計算量：Ｏ(ｎ2) |
対象集合（配列など）の隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返して行う方法です。 昇順ソートのとき：Ａ[ｉ]＞Ａ[ｉ＋１] ならば、Ａ[ｉ] とＡ[ｉ＋１] をスワップ 降順ソートのとき：Ａ[ｉ]＜Ａ[ｉ＋１] ならば、Ａ[ｉ] とＡ[ｉ＋１] をスワップ 昇順のとき、小さい要素が泡（バブル）のように上（配列の先頭側）へ移動する |
|
選択ソート 分類：選択法、安定ではない 平均比較回数：ｎ(ｎ－１)／２ 計算量：Ｏ(ｎ2) |
対象集合から最も小さい(または最も大きい)要素を順次取り出して、端に置いていくことでソートする方法です。 昇順ソートならば、全体のなかで最小値（最大値）の要素を探し、その要素を先頭（末尾）に置きます。次に、対象になった要素以外での最小値（最大値）の要素をその次に置きます。これを繰り返すことにより、ソートができます。降順ソートの場合も同様です。 |
|
挿入ソート 分類：挿入法、安定ソート 計算量：Ｏ(ｎ2) 特徴：データ移動回数が多い |
対象集合の先頭付近がソートされているとして、対象集合の未ソートの部分から要素を順次取り出し，それまでに取り出した要素の集合に順序関係を保つよう挿入してソートを行う方法です。 Ａ[１]～Ａ[ｋ]が既にソートされているとします。未ソートの最初の要素はＸ＝Ａ[ｋ＋１]です。ＸとＡ[１]～Ａ[ｋ]を比較して、入れるべき個所がｉならば、Ａ[ｉ]～Ａ[ｋ]を一つ下にずらし（Ａ[ｉ＋１]以降にコピーして、Ａ[ｉ]をＸにすればよいのです。要素の移動数が非常に多くなります。 |
|
マージソート 分類：併合法、安定ソート 計算量：Ｏ(ｎlog2ｎ) 特徴：大きな作業領域が必要 |
対象集合を単純に２等分した区分にします。それぞれの区分内でソートされていれば、２つの区分をマージ（併合）することにより、全体がソートされます。区分内でソートされていない場合は、それをさらに２等分して、同様な操作を行います。これを繰り返すことにより全体がソートされます。 マージソートは、クイックソートのように、状況によって速度が低下するようなことがありません。しかし、区分に分けるために、大きな作業領域が必要になります。 |
|
クイックソート 分類：交換法、安定ではない 平均比較回数：ｎlog2ｎ （最悪の場合：ｎ2） 計算量：Ｏ(ｎlog2ｎ) |
全体のなかから、中間的な基準となる要素を１つ選び（ピボット－枢軸－という）、これより小さい要素と大きい要素の区分に分割します。さらに分割した２つの区分の中で分割を行います。これを繰り返してソートを行う方法です。 ピボットになる要素の選び方により、一方の区分に多くの要素が集まることがああり、その場合には効率が悪くなります。 |
|
シェルソート 分類：挿入法、安定ではない 計算量：Ｏ(ｎα)、α＝1.2～1.5 |
ある間隔で要素を取り出した部分列を整列し、さらに間隔をつめた部分列を取り出してソートする方法です。 ある一定間隔おきに取り出した要素からなる部分列をそれぞれソートし（このときに挿入ソートや他の方法を用いることもあります）、更に間隔を詰めて同様の操作を行い、間隔が１になるまで繰り返すことによりソートが実現します。 この間隔の取り方、対象集合の事前の並びの状況により、処理効率は大きく変わり、計算量Ｏも厳密には与えられません。 |
|
ヒープソート 分類：選択法、安定ではない 計算量：Ｏ(ｎlog2ｎ) 特徴：大きな作業領域が必要 |
未整列の部分を木構造の順序木（ヒープ構造）に構成し、そこから最大値又は最小値を取り出して既整列の部分に移す。この操作を繰り返して、実整列部分を縮めていく方法です。 ヒープ構造とは、２分木の各節点にデータを保持し、親のデータが２つの子のデータよりも小さく（大きく）なるように作られたデータ構造で、これにより、最小値（最大値）が根（ルート）になります。根のデータから、順にポインタにより取り出して、先頭（末尾）の要素とすることにより、昇順（降順）にソートできます。 部分的にヒープ構造にする（データとポインタ）ので、そのための作業領域が必要になります。 |
例えば、売上ファイルのレコードを得意先コード順や日付順でソートするというように、磁気ディスクなど外部記憶装置にあるデータをソートする方法です。直接編成ファイルや索引順編成ファイルのソートに関しては別途にして、ここでは順編成ファイルのソートについて考察します。
レコードは、部分的には既にソートされている部分があります。それを連といいます。連ごとに別のファイルに書き込めば、それらのファイル内ではソートされています。
ソートされている複数のファイルから、ソートの順を維持しつつ一つのファイルにまとめることをマージ（併合）といいます。（マージは配列の併合などにも用いられます）。連ごとに書き込まれているファイルをマージすることにより、ソートすることができます。
書き込むファイルの個数に制約がある場合には工夫が必要です。外部ソート、マージに関しては、「マージ」（al-sort-merge）で説明します。