Web教材一覧アルゴリズム
(BOK大区分:1 基礎理論、中区分:2 アルゴリズムとプログラミング、中区分:2 アルゴリズム)

マージと外部ソート

学習のポイント

外部ソートとは、磁気ディスクや磁気テープに保管されているファイルをソートすることです。ここでは順編成ファイルを対象とします。マージ(併合)とは、既に共通のキー項目でソートされている2つのファイルあるいは配列を、ソートの順序を保持しながら1つのファイル(配列)にまとめる処理です。外部ソートを行うには、マージが重要な処理になります。

キーワード

アルゴリズム、外部ソート、マージ


マージ(併合)

既にソートされている複数の配列やファイルを、ソートの順序を保持しつつ、一つの配列やファイルにまとめることをマージ併合)といいます。

2つの順編成ファイル、ファイルBとファイルCが、それぞれコードBとコードCの昇順にソートされています。それをマージしてファイルAにするアルゴリズムを考えます。

     ファイルB       ファイルC         ファイルA
   コードB        コードC
   ┌──┬─────┐  ┌──┬─────┐    ┌──┬─────┐
   │10│BBアアア│  │20│CCカカカ│   ①│10│BBアアア│
   ├──┼─────┤  ├──┼─────┤    ├──┼─────┤
   │30│BBイイイ│  │40│CCキキキ│   ②│20│CCカカカ│
   ├──┼─────┤  ├──┼─────┤    ├──┼─────┤
   │40│BBウウウ│  │60│CCククク│   ③│30│BBイイイ│
   └──┴─────┘  └──┴─────┘    ├──┼─────┤
   :99:Bの終わり:  :99:Cの終わり:   ④│40│BBウウウ│
   ・……・……………・  ・……・……………・    ├──┼─────┤
                            ⑤│40│CCキキキ│
                             ├──┼─────┤
                            ⑥│60│CCククク│
                             └──┴─────┘

アルゴリズム
一般的には、次のようになります。
 コードB<コードC : ファイルBのレコードをファイルAにコピーして、次にファイルBを読む
 コードB>コードC : ファイルCのレコードをファイルAにコピーして、次にファイルCを読む
 コードB=コードC : ファイルBとCのレコードをファイルAにコピーして、次にファイルBとCを読む
ファイルのすべてのレコードを読み終わった後をどうすればよいでしょうか。
 上図の点線のようなダミーレコードがあればよいと考えられます。このような機能は、例えばCOBOLでは
   READ ファイルB AT END コードB=大きい値.
という機能があります。

プログラム
 ア  ファイルBを読む。終わりならば コードB=99;
 イ  ファイルCを読む。終わりならば コードC=99;
 ウ  while ( (コードB<99) and (コードC<99) ) {
 エ    if (コードB<コードC) {
 オ      レコードBをファイルAに出力;
 カ      ファイルBを読む。終わりならば コードB=99;
 キ    }
 ク    else if (コードB>コードC) {
 ケ      レコードCをファイルAに出力;
 コ      ファイルCを読む。終わりならば コードC=99;
 サ    }  シ    else if (コードB>コードC) {
 ス      レコードBをファイルAに出力;
 セ      レコードCをファイルAに出力;
 ソ      ファイルBを読む。終わりならば コードB=99;
 タ      ファイルCを読む。終わりならば コードB=99;
 チ    }
 ツ  }

トレース
 ア コードB=10
 イ コードC=20
 ウ コードB<99 コードC<99、 コードB(10)<コードC(20) → オへ
 オ コードB(10)のレコードを出力 ①
 カ コードB=30 → ウへ
 ウ コードB<99 コードC<99、 コードB(30)>コードC(20) → ケへ
 ケ コードC(20)のレコードを出力 ②
 コ コードC=40 → ウへ
 ウ コードB<99 コードC<99、 コードB(30)<コードC(40) → オへ
 オ コードB(30)のレコードを出力 ③
 カ コードB=40 → ウへ
 ウ コードB<99 コードC<99、 コードB(40)=コードC(40) → スへ
 ス コードB(40)のレコードを出力 ④
 セ コードC(40)のレコードを出力 ⑤
 ソ ファイルB終わり コードB=99
 タ コードC=60 → ウへ
 ウ コードB=99 しかし コードC<99、 コードB(99)>コードC(60) → ケへ
 ケ コードC(60)のレコードを出力 ⑥
 コ ファイルC終わり コードC=99 → ウへ
 ウ コードB=99 AND コードC=99 → 終了

練習問題
<問題>
 ファイルBとファイルCがソートされているとの条件に反しますが、次のファイルを、上のプログラムでマージすると、どのようになるでしょうか。

     ファイルB       ファイルC
   コードB        コードC
   ┌──┬─────┐  ┌──┬─────┐
   │10│BBアアア│  │20│CCカカカ│
   ├──┼─────┤  ├──┼─────┤
   │40│BBイイイ│  │60│CCキキキ│
   ├──┼─────┤  ├──┼─────┤
   │30│BBウウウ│  │50│CCククク│
   └──┴─────┘  └──┴─────┘
<解答>
   ┌──┬─────┐
   │10│BBアアア│
   ├──┼─────┤
   │20│CCカカカ│
   ├──┼─────┤
   │40│BBイイイ│
   ├──┼─────┤
   │30│BBウウウ│
   ├──┼─────┤
   │60│CCキキキ│
   ├──┼─────┤
   │50│CCククク│
   └──┴─────┘

かなり複雑になりますが、入力ファイルが3つ以上でのマージを行うことも可能です。その機能をもつユーティリティソフトウェアが提供されています。

外部ソート

磁気ディスクや磁気テープなど、外部記憶装置にあるファイルをソートすることを外部ソートといいます。
 ファイルの全データをメモリに読み込むことは、メモリ容量が不足しますので、外部記憶装置を用いてソートする必要があります。
 直接編成ファイルや索引順編成ファイルなどに関しては、別章で取り扱いますので、ここでは順編成ファイルを対象にします。

ソートするキー項目が次のように並んでいるファイルAをソートすることを考えます(キー項目以外の項目は煩雑になるので省略します)。
  ファイルA
     ①  ②  ③  ④  ⑤  ⑥  ⑦  ⑧  ⑨
   ┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
   │30│60│93│14│84│41│71│53│26│
   └──┴──┴──┴──┴──┴──┴──┴──┴──┘

アルゴリズム
 ①~③ や ④~⑤ など、部分的には既にソートされています。ソートされている部分をといいます。
 ファイルAを連ごとに別のファイル(ワークファイルといいます)に出力すれば、
   30、60、90
   14、84
   41、71
   53
   26
の4つのファイルになります。
 この4つのファイルをマージすればソートが完成します。

複数のファイルをマージするソフトウェアがあるにせよ、せいぜい数ファイルを想定しているのであり、ワークファイルの個数が数百、数千のファイルになる場合には使えません。それで、限られたワークファイルでソートする工夫をする必要があります。ここでは、ワークファイルをファイルBとファイルCの2つであるとします。

分割
ファイルAのレコードを、連をファイルBとファイルCに交互に出力します。上の例では、
   ファイルB:30、60、90、41、71、26
   ファイルC:14、84、53
となります。
マージ
ファイルBとファイルCをマージしてファイルAに出力します。
   ファイルA:14、30、60、84、53、90、41、71、26
となります。

このファイルAはソートされていません。それでまた分割とマージを行います。これを繰り返すことにより、ソートができます。
   ファイルA:14、30、60、84、53、90、41、71、26
      ファイルB:14、30、60、84、41、71、
      ファイルC:53、90、26
   ファイルA:14、30、53、60、84、41、71、90、26
      ファイルB:14、30、53、60、84、26
      ファイルC:41、71、90、
   ファイルA:14、30、41、53、60、71、84、26、90
      ファイルB:14、30、41、53、60、71、84
      ファイルC:26、90
   ファイルA:14、26、30、41、53、60、71、84、90
      ソート終了

以上からわかるように、連の個数が多いと、分割とマージの回数が多くなり、入出力回数が増大し、効率が悪くなります。
 最も効率が悪いのは、ファイルAが逆順にソートされているときです。


アルゴリズムへ