(57)【特許請求の範囲】
【請求項１】
ｎ個のデータからなるデータ集合が格納された記憶領域にソート番号１〜ｎ（ｎ≧２以上の整数）を付与し、データ集合を予め設定されたソート番号ｉ〜ｊ（１≦ｉ≦ｊ≦ｎ）の範囲のデータを有する第１集合、その前後のソート番号１〜（ｉ−１）、ソート番号（ｊ＋１）〜ｎの各範囲のデータを有する第２集合、第３集合に３分割するデータ集合分割手段と、
第２集合、第３集合のデータを逐次走査し、第２集合のデータが第１集合の最小値データと比較して大きい時には、第１集合の最小値データと交換し、第３集合のデータが第１集合の最大値データと比較して小さい時には、第１集合の最大値データと交換するデータ交換手段と、
他集合とのデータ交換毎に第１集合のデータをソートするソート手段と、
第２集合、第３集合の一方の集合の全走査が終了してから、他方の集合の全走査終了までにデータ交換したすべての走査データが、第１集合の最小値と最大値の範囲内と判別したときに、第１集合のデータをソート結果として出力するソート完了判別手段とを備えたことを特徴とするソート装置。
【請求項２】
データ交換手段は、第２集合が第１集合の最大値より大きいデータを走査し、かつ第３集合が第１集合の最小値より小さいデータを走査したときに、相互にデータを交換するデータ相互交換手段と、
第２集合、第３集合の一方の集合のデータの全走査が終了したときに、第１集合のデータ数をカウンタに設定するデータ数設定手段と、
カウンタ値が１以上で、かつ走査中の集合が、走査終了した集合の範囲に属するデータを走査したときには、第１集合とデータ交換を行うとともにカウンタ値から1 を引くデータ交換処理手段と、
カウンタ値が０以下であり、かつ走査中の集合が、走査終了した集合の範囲に属するデータを走査したときには、走査中の集合の所定の位置にデータを移動するとともにカウンタ値から1 を引くデータ移動手段とをさらに備えたことを特徴とする請求項１記載のソート装置。
【請求項３】
データ集合分割手段は、第２集合、第３集合のデータの全走査が終了したときに、カウンタ値が０以上であれば、第１集合及び先に全走査が終了した集合の２集合にデータ集合を変更する集合第１変更手段と、
カウンタ値が負であれば、第１集合及び先に全走査が終了した集合及び後から全走査が終了した集合の中で所定の位置に移動したデータのみからなる集合の３集合にデータ集合を変更する集合第２変更手段とをさらに備えたことを特徴とする請求項２記載のソート装置。
【請求項４】
データ集合分割手段は、予め設定されたソート番号ｉ〜ｊの範囲のデータを更にＡ1 〜Ａn （ｎは整数）にＮ分割するソート範囲分割手段と、
分割した集合の中のＡ1 集合とその前後の集合の３集合に３分割する集合第１分割手段と、
Ａm 集合（m ＝１〜（ｎ−１））がソート完了判別手段によりソート完了と判別されたときのＡm+1 集合の先頭データからソート番号ｎの最終データまでの集合に基いて、Ａm+1 集合とＡm+1 集合に続くデータからソート番号ｎの最終データまでの集合の２集合への分割を行う集合第２分割手段とをさらに備えたことを特徴とする請求項１記載のソート装置。
【請求項５】
ｎ個のデータからなるデータ集合が格納された記憶領域にソート番号１〜ｎ（ｎ≧２以上の整数）を付与し、データ集合を予め設定されたソート番号ｉ〜ｊ（１≦ｉ≦ｊ≦ｎ）の範囲のデータを有する第１集合、その前後のソート番号１〜（ｉ−１）、ソート番号（ｊ＋１）〜ｎの各範囲のデータを有する第２集合、第３集合に３分割するデータ集合分割ステップと、
第２集合、第３集合のデータを逐次走査し、第２集合のデータが第１集合の最小値データと比較して大きい時には、第１集合の最小値データと交換し、第３集合のデータが第１集合の最大値データと比較して小さい時には、第１集合の最大値データと交換するデータ交換ステップと、
他集合とのデータ交換毎に第１集合のデータをソートするソートステップと、
第２集合、第３集合の一方の集合の全走査が終了してから、他方の集合の全走査終了までにデータ交換したすべての走査データが、第１集合の最小値と最大値の範囲内と判別したときに、第１集合のデータをソート結果として出力するソート完了判別ステップとを有することを特徴とするソート方法。
【請求項６】
ｎ個のデータからなるデータ集合が格納された記憶領域にソート番号１〜ｎ（ｎ≧２以上の整数）を付与し、データ集合を予め設定されたソート番号ｉ〜ｊ（１≦ｉ≦ｊ≦ｎ）の範囲のデータを有する第１集合、その前後のソート番号１〜（ｉ−１）、ソート番号（ｊ＋１）〜ｎの各範囲のデータを有する第２集合、第３集合に３分割するデータ集合分割機能と、
第２集合、第３集合のデータを逐次走査し、第２集合のデータが第１集合の最小値データと比較して大きい時には、第１集合の最小値データと交換し、第３集合のデータが第１集合の最大値データと比較して小さい時には、第１集合の最大値データと交換するデータ交換機能と、
他集合とのデータ交換毎に第１集合のデータをソートするソート機能と、
第２集合、第３集合の一方の集合の全走査が終了してから、他方の集合の全走査終了までにデータ交換したすべての走査データが、第１集合の最小値と最大値の範囲内と判別したときに、第１集合のデータをソート結果として出力するソート完了判別機能とを実現するためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項７】
ｎ個のデータからなるデータ集合が格納された記憶領域にソート番号１〜ｎ（ｎ≧２以上の整数）を付与し、データ集合を予め設定されたソート番号ｉ〜ｊ（１≦ｉ≦ｊ≦ｎ）の範囲のデータを有する第１集合、その前後のソート番号１〜（ｉ−１）、ソート番号（ｊ＋１）〜ｎの各範囲のデータを有する第２集合、第３集合に３分割するデータ集合分割機能と、
第２集合、第３集合のデータを逐次走査し、第２集合のデータが第１集合の最小値データと比較して大きい時には、第１集合の最小値データと交換し、第３集合のデータが第１集合の最大値データと比較して小さい時には、第１集合の最大値データと交換するデータ交換機能と、
他集合とのデータ交換毎に第１集合のデータをソートするソート機能と、
第２集合、第３集合の一方の集合の全走査が終了してから、他方の集合の全走査終了までにデータ交換したすべての走査データが、第１集合の最小値と最大値の範囲内と判別したときに、第１集合のデータをソート結果として出力するソート完了判別機能とを実現するためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、不規則に並ぶ複数のデータを昇順又は降順に並べ換えて出力するソート装置に関する。
【０００２】
【従来の技術】
情報を人間が参照する場合、見やすくするために昇順または降順にソートして並び替え処理を行い、ディスプレイなどに出力する。
【０００３】
図14に従来例のソート手順の説明図を示す。
【０００４】
例えば、１５人のグループの試験結果で順位が下から５番目〜９番目の氏名と点数を知りたいとする。
【０００５】
そのため、まず点数データが入っている磁気ディスク等のファイルから、試験結果のデータ（氏名と点数）を読み出し、ソート番号１〜１５を付与したメモリ領域に１５個のデータを格納する。
【０００６】
次に、点数をソートキー項目として、昇順にソートする。ソート方法は、例えば、２個のデータの組合せ毎にデータを比較して大小を決める処理を繰返し、最大又は最小のデータを出力する処理を繰り返す等の公知の方法による。
【０００７】
昇順にソートした結果は、ソート番号１〜１５のメモリ領域に格納され、格納した内容をディスプレイ等に出力する。
【０００８】
そして出力した結果を見て、５番目〜９番目の氏名と点数を確認する。
【０００９】
【発明が解決しようとする課題】
しかし、不規則に並ぶデータ集合のソート結果のある一部のみを求めたいときに、全体をソートするのでは、データ量が小さければ問題はないが、データ量が大きければ大きいほど、回答が得られるまでに時間を要するという問題が発生する。すなわち、データ集合を２個単位で比較するソート方式を例にとると少なくとも、ｎ（ｎ−１）／２回のリードアクセスが発生するため、データ量の大きさが大きいほどその回答が得られるまでの時間が大きくなる。
【００１０】
本発明は、ソート対象のデータ集合について、全体のソートを行わずに、データ集合の一部のみをソートすることで高速にソート処理を行うことを目的としている。
【００１１】
【課題を解決するための手段】
ｎ個のデータからなるデータ集合が格納された記憶領域にソート番号１〜ｎ（ｎ≧２以上の整数）を付与し、データ集合を予め設定されたソート番号ｉ〜ｊ（１≦ｉ≦ｊ≦ｎ）の範囲のデータを有する第１集合、その前後のソート番号１〜（ｉ−１）、ソート番号（ｊ＋１）〜ｎの各範囲のデータを有する第２集合、第３集合に３分割するデータ集合分割手段と、
第２集合、第３集合のデータを逐次走査し、第２集合のデータが第１集合の最小値データと比較して大きい時には、第１集合の最小値データと交換し、第３集合のデータが第１集合の最大値データと比較して小さい時には、第１集合の最大値データと交換するデータ交換手段と、
他集合とのデータ交換毎に第１集合のデータをソートするソート手段と、
第２集合、第３集合の一方の集合の全走査が終了してから、他方の集合の全走査終了までにデータ交換したすべての走査データが、第１集合の最小値と最大値の範囲内と判別したときに、第１集合のデータをソート結果として出力するソート完了判別手段とを備えた構成である。
【００１２】
この構成では、データ集合を３分割しているが、第２集合、第３集合は、データが０個の集合の場合も含まれている。
【００１３】
ソート番号1 〜(i-1) の集合は、昇順ソートのときは第２集合であり、降順ソートのときは第３集合である。
【００１４】
ソート番号（j+1)〜ｎの集合は、昇順ソートのときは第３集合であり、降順ソートのときは第２集合である。
【００１５】
まず、第２集合のデータの走査により、第１集合の最小値より大きいデータを順次、第１集合の最小値と交換していくことにより、第１集合より小さいデータを第２集合に集結していく。
【００１６】
また、第３集合のデータの走査により、第１集合の最大値より小さいデータを順次、第１集合の最大値と交換していくことにより、第１集合より大きいデータを第３集合に集結していく。この繰返しにより、第１集合に予め設定されたソート範囲（ソート番号ｉ〜ｊ）のデータが順次集結してくる。
【００１７】
また第２集合、第３集合と第１集合とのデータ交換ごとに第１集合をソートする。これにより、最小値と最大値の配置が明確となり、他集合のデータ比較が簡単となる。すなわち、昇順のときは、ソート番号ｉに最小値が、ソート番号ｊに最大値が格納されている。また、降順のときは、ソート番号ｉに最大値が、ソート番号ｊに最小値が格納されている。
【００１８】
そして、第２集合、第３集合の一方が終了すると、他方が走査を継続していくが、その走査中に第１集合とのデータ交換が発生するときもある。そのときの走査データが、すべて第１集合の最小値と最大値の範囲内であれば、先に走査完了した集合に影響するデータはないと判断できるので、走査中の集合の走査完了とともに、ソート処理は完了する。そして、第１集合の内容は、ソートされているので、そのままの内容がソート結果となる。
【００１９】
このように、第１集合のみをソートし、第２、第３集合は、走査処理のみのため、全体のデータ集合をソートする必要がなくなるため、データのアクセス回数が減少し、ソート処理を高速に実施できる。
【００２０】
特にデータ量が大きく、ソート範囲が小さければ、効果が大きくなる。
【００２１】
また、データ交換手段は、第２集合が第１集合の最大値より大きいデータを走査し、かつ第３集合が第１集合の最小値より小さいデータを走査したときに、相互にデータを交換するデータ相互交換手段と、
第２集合、第３集合の一方の集合のデータの全走査が終了したときに、第１集合のデータ数をカウンタに設定するデータ数設定手段と、
カウンタ値が１以上で、かつ走査中の集合が、走査終了した集合の範囲に属するデータを走査したときには、第１集合とデータ交換を行うとともにカウンタ値から1 を引くデータ交換処理手段と、
カウンタ値が０以下であり、かつ走査中の集合が、走査終了した集合の範囲に属するデータを走査したときには走査中の集合の所定の位置にデータを移動するとともにカウンタ値から1 を引くデータ移動手段とをさらに備えた構成である。
【００２２】
この構成により、第２集合、第３集合の各々の集合に相手側の範囲に属するデータが相互に有る場合は、第１集合を経由せずに直接交換するため、ソート処理を高速化することが出来る。
【００２３】
また、カウンタ値を設け、そのカウンタ値が負の場合のときにはデータ交換方法を変え、所定の位置にデータを移動させておくことで、再走査のときに走査範囲を減少させることが出来る。
【００２４】
また、データ集合分割手段は、第２集合、第３集合のデータの全走査が終了したときに、カウンタ値が０以上であれば、第１集合及び先に全走査が終了した集合の２集合にデータ集合を変更する集合第１変更手段と、
カウンタ値が負であれば、第１集合及び先に全走査が終了した集合及び後から全走査が終了した集合の中で所定の位置に移動したデータのみからなる集合の３集合にデータ集合を変更する集合第２変更手段とをさらに備えた構成である。
【００２５】
この構成により、カウンタ値をチェックすることで、再走査するときの集合の範囲を変える。特にカウンタ値が負であれば、再度第２集合または第３集合を走査するときの走査範囲を減少することができる。これは、カウンタ値が０以上のときには、走査中の集合と第１集合との大小関係が崩れないが、カウンタ値が０以下になると、それ以降のデータは、大小関係が崩れるからである。この結果、ソート処理が高速化する。
【００２６】
データ集合分割手段は、予め設定されたソート番号ｉ〜ｊの範囲のデータを更にＡ1 〜Ａn （ｎは整数）にＮ分割するソート範囲分割手段と、
分割した集合の中のＡ1 集合とその前後の集合の３集合に３分割する集合第１分割手段と、
Ａm 集合（m ＝１〜（ｎ−１））がソート完了判別手段によりソート完了と判別されたときのＡm+1 集合の先頭データからソート番号ｎの最終データまでの集合に基いて、Ａm+1 集合とＡm+1 集合に続くデータからソート番号ｎの最終データまでの集合の２集合への分割を行う集合第２分割手段とをさらに備えた構成である。
【００２７】
この構成により、設定された範囲の集合をＡ1 〜Ａn にＮ分割する。そして、データ分割第１手段により生成された集合によりＡ1 集合のソート結果を得る。Ａ1 集合に続いて、Ａ2 〜Ａn 集合では、データ分割第２手段により生成した集合によりソート結果を順次（Ａ2 集合、Ａ3 集合───Ａn 集合の順番）得ることができる。この結果、主記憶容量が小さい装置でも、分割した部分のみを主記憶容量に順次搭載してソートできる。そのため、速度の遅いハードディスクなどを使用してソートすることが不要となり、ソート処理を高速に実行できる。
【００２８】
また、ｎ個のデータからなるデータ集合が格納された記憶領域にソート番号１〜ｎ（ｎ≧２以上の整数）を付与し、データ集合を予め設定されたソート番号ｉ〜ｊ（１≦ｉ≦ｊ≦ｎ）の範囲のデータを有する第１集合、その前後のソート番号１〜（ｉ−１）、ソート番号（ｊ＋１）〜ｎの各範囲のデータを有する第２集合、第３集合に３分割するデータ集合分割ステップと、第２集合、第３集合のデータを逐次走査し、第２集合のデータが第１集合の最小値データと比較して大きい時には、第１集合の最小値データと交換し、第３集合のデータが第１集合の最大値データと比較して小さい時には、第１集合の最大値データと交換するデータ交換ステップと、他集合とのデータ交換毎に第１集合のデータをソートするソートステップと、第２集合、第３集合の一方の集合の全走査が終了してから、他方の集合の全走査終了までにデータ交換したすべての走査データが、第１集合の最小値と最大値の範囲内と判別したときに、第１集合のデータをソート結果として出力するソート完了判別ステップとを有する構成のソート方法である。
【００２９】
また、ｎ個のデータからなるデータ集合が格納された記憶領域にソート番号１〜ｎ（ｎ≧２以上の整数）を付与し、データ集合を予め設定されたソート番号ｉ〜ｊ（１≦ｉ≦ｊ≦ｎ）の範囲のデータを有する第１集合、その前後のソート番号１〜（ｉ−１）、ソート番号（ｊ＋１）〜ｎの各範囲のデータを有する第２集合、第３集合に３分割するデータ集合分割機能と、第２集合、第３集合のデータを逐次走査し、第２集合のデータが第１集合の最小値データと比較して大きい時には、第１集合の最小値データと交換し、第３集合のデータが第１集合の最大値データと比較して小さい時には、第１集合の最大値データと交換するデータ交換機能と、他集合とのデータ交換毎に第１集合のデータをソートするソート機能と、第２集合、第３集合の一方の集合の全走査が終了してから、他方の集合の全走査終了までにデータ交換したすべての走査データが、第１集合の最小値と最大値の範囲内と判別したときに、第１集合のデータをソート結果として出力するソート完了判別機能とを実現するためのプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【００３０】
【発明の実施の形態】
図１に実施例のソート装置の構成図を示す。
【００３１】
ソート装置１は、ソート範囲設定部２、ソート処理部３、データ記憶部４、主記憶部５、結果出力部６から構成される。
【００３２】
また、ソート処理部３は、データ集合分割部３１、データ交換部３２、ソート部３３、ソート完了判別部３４より構成される。
【００３３】
ソート装置１の処理を説明する。
【００３４】
ソート範囲設定部２は、指定ファイルとソートキー項目（各データは、１つ以上の項目データを持つが、その中のソートしたい項目）とソートしたい範囲及び昇順か降順かの指定をキーボード等により設定し、そのデータをソート処理部へ渡す。
【００３５】
図２に実施例１のソート処理部の処理の流れ図を示す。
【００３６】
ソート範囲設定部２で入力されたデータを元に、データ集合分割部３１はデータ記憶部４（ハードディスク等の低速メモリ）に記憶されている指定ファイルを主記憶部５（高速メモリ）へ複写を行う（S11 ステップ）。
【００３７】
複写して主記憶部５に格納されたファイルの先頭データから最終データまでの記憶領域をソート番号の１番から昇順に順次連続番号を付与する。
【００３８】
指定ファイルのデータの集合Ｘ（要素ｎ個の構成）の設定範囲集合Ｂのソート番号ｉ番からｊ番目のデータを昇順にソートした結果を求める場合について説明する。
【００３９】
図３にソート処理部のデータ集合分割の説明図を示す。
【００４０】
データ集合分割部３１は、例えば集合Ｘを集合Ａ（ソート 番号1 〜i-1 番目）、集合Ｂ（ソート 番号ｉ〜集合Ｂのｊ番目）、集合Ｃ（ソート 番号j+1 〜n 番目）に３分類する（S12 ステップ）。
【００４１】
次にデータ交換部３２は、まず集合Ｂをソートして昇順に並べる。(S13ステップ)
次に集合Ａ第１処理（S14 ステップ）、集合Ｂ処理（S15 ステップ）、集合Ｃ第１処理（S16 ステップ）を行う。
【００４２】
図４に集合Ａ第１処理の流れ図を示す。
【００４３】
集合Ａの場合（先頭から走査するものとする）、まず集合Ｃ第１処理が完了したか否かをチェックする（S140 ステップ ）。完了していれば終了する。
【００４４】
完了していないときは、集合Ａ内に走査すべきデータの要素の有無を確認し（S141 ステップ ）、要素がなければ、処理を終了する。
【００４５】
集合Ａ内に走査する要素があれば、集合Ａの要素の値と集合Ｂのｉ番目の要素の値とを比較する（S142ステップ）。
集合Ａの要素が集合Ｂのｉ番目の要素の値より小さければ処理の先頭（S140ステップ）に戻る。
【００４６】
集合Ａの要素が集合Ｂのｉ番目の要素の値より大きい場合はj 番目の要素の値との大小を比較する（S143 ステップ ）。
【００４７】
集合Ａの要素が集合Ｂのｉ番目の要素の値より大きく、j 番目の要素の値より小さい場合は、集合Ａの要素を集合Ｂのｉ番目の要素の値と交換し、交換後、集合Ｂをソートし（S144 ステップ ）、処理の先頭（S140ステップ）に戻る。
【００４８】
集合Ａの要素が集合Ｂのj 番目より大きい場合は、集合Ｃに集合Ｂのｉ番目より小さい値を持つ要素があるかを確認する（S145ステップ）。
【００４９】
集合Ｃに集合Ｂのｉ番目より小さい値を持つ要素が有る場合は、集合Ｃと集合Ａ間で、要素の交換を行い（S146ステップ）、処理の先頭（S140ステップ）に戻る。
【００５０】
集合Ｃに集合Ｂのｉ番目より小さい値を持つ要素が無い場合は、集合Ａと集合Ｃ間で残りの要素の走査数を比較する（S147ステップ）。
【００５１】
集合Ａの残り走査数が集合Ｃの残り走査数より多い場合は、集合Ｂのｉ番目の要素と交換し、その後集合Ｃの要素と集合Ｂのｉ番目の要素と更に交換し、交換後に集合Ｂをソートする（S148ステップ）。そして処理の先頭（S140ステップ）に戻る。集合Ｃの残り走査数が集合Ａの残り走査数より多い場合、または同等の場合はS145ステップに戻り、集合Ｃに集合Ｂのｉ番目より小さい要素が走査されるまで待っている。
【００５２】
この一連の処理を集合Ａの走査する要素のなくなるまで、繰り返す。
【００５３】
集合Ｂ処理(S15ステップ）は、集合Ａ第１処理、集合Ａ第２処理、集合Ｃ第１処理、集合Ｃ第２処理などでの要素の交換ごとにソート処理を実行する。
【００５４】
ソート処理は、集合Ａと集合Ｂ間のデータ交換処理のときは、ソート番号ｉ番と(i＋１）番と比較し、ｉ番目が小さければ、何もせずに処理を終了するが、ｉ番目が大きければ、公知の方法により、ソートを実行する。
【００５５】
集合Ｃと集合Ｂ間のデータ交換処理のときは、ソート番号ｊ番と(j−１）番と比較し、ｊ番目が大きければ、何もせずに処理を終了するが、ｊ番目が小さければ、公知の方法により、ソートを実行する。
【００５６】
図５に集合Ｃ第１処理の流れ図を示す。
【００５７】
集合Ｃの場合（最後尾から走査するものとする）、まず、集合Ａ第１処理が完了したか否かをチェックする（S160ステップ）。完了しているときは、終了する。
【００５８】
完了していないときは、集合Ｃ内に走査要素の有無を確認する（S161ステップ）。要素がなければ、処理を終了する。
【００５９】
集合Ｃ内に走査する要素があるときは、集合Ｃの要素と集合Ｂのｊ番目の要素の値とを比較する（S162ステップ）。
【００６０】
集合Ｃの要素が集合Ｂのｊ番目の要素の値より大きければ処理の先頭（S160ステップ）に戻る。
【００６１】
集合Ｃの要素が集合Ｂのｊ番目の要素の値より小さい場合は集合Ｂのｉ番目の要素の値との大小を比較する。
【００６２】
集合Ｃの要素が集合Ｂのｊ番目の要素の値より小さく、集合Ｂのｉ番目の要素の値より大きい場合は、集合Ｃの要素を集合Ｂのｊ番目の要素の値と交換し、交換後集合Ｂはソート処理を行い（S164ステップ）、処理の先頭（S160ステップ）に戻る。集合Ｃの要素が集合Ｂのｉ番目より小さい場合は、集合Ａに集合Ｂのｊ番目より大きい値を持つ要素があるかを確認する（S165ステップ）。
【００６３】
集合Ａに集合Ｂのｊ番目より大きい要素の値を持つ要素が有る場合は、集合Ｃと集合Ａ間で、要素の交換を行い（S166ステップ）処理の先頭（S160ステップ）に戻る。集合Ａに集合Ｂのｊ番目より大きい要素の値を持つ要素が無い場合は、集合Ａと集合Ｃ間で残り走査数を比較する（S167ステップ）。
【００６４】
集合Ｃの残り走査数が集合Ａの残り走査数より多い場合は、集合Ｂのｊ番目の要素と交換し、その後、集合Ａの要素と集合Ｂのｊ番目の要素と更に交換し、交換後に集合Ｂをソートする（S168ステップ）。その後、処理の先頭（S160ステップ）に戻る。
【００６５】
集合Ａの残り走査数が集合Ｃより多い場合、または同等の場合は、S165ステップに戻り、集合Ａの集合Ｂのｊ番目より大きい要素が走査されるまで待っている。
【００６６】
この一連の処理を集合Ｃの走査する要素のなくなるまで、繰り返す。
【００６７】
集合Ａ第１処理、集合Ｃ第１処理は、並行に動作しているため、一方が先に全要素の走査を終了する。
【００６８】
集合Ａ第１処理が先に完了したときは、集合Ｃ第１処理を終了し、集合Ｃ第２処理を行う。
【００６９】
図６に集合Ｃ第２処理を示す。
【００７０】
集合Ｃ内に走査要素の有無をチェックする（S171ステップ）。
【００７１】
走査要素が無ければ処理を終了する。
【００７２】
集合Ｃ内に走査要素があれば、まず集合Ｂの設定範囲幅（ソート番号ｉ〜ｊの幅）をカウンタＣにセットする（S172ステップ）。
【００７３】
次に、集合Ｃの要素が集合Ｂのｊ番目より小さい値かをチェックする（S173ステップ）。
【００７４】
集合Ｂのｊ番目より大きければ、処理の先頭（S171ステップ）に戻る。
【００７５】
集合Ｂのｊ番目より小さければ、集合Ｂのｉ番目より大きい値か否かをチェックする（S174ステップ）。
【００７６】
集合Ｃの要素が集合Ｂのｊ番目より小さく集合Ｂのｉ番目より大きい値のときには、集合Ｂのｊ番目の要素と交換し、交換後、集合Ｂは、ソート処理を実行する（S175ステップ）。そして処理の先頭（S171ステップ）に戻る。
【００７７】
集合Ｃの要素が集合Ｂのｉ番目より小さい値のときには、カウンタＣ値をチェックする（S176ステップ）。
【００７８】
カウンタ値が１以上であれば、集合Ｃの要素と集合Ｂのｊ番目の要素と交換後、集合Ｂは、ソート処理を実行する（S177ステップ）。
【００７９】
次にカウンタ値から1 を引き（S179ステップ）、処理の先頭（S171ステップ）に戻る。カウンタ値が０以下であれば、集合Ｃの先頭に走査した要素を移動させる（S178ステップ）。
【００８０】
先頭への移動は、S178ステップが発生するたびに、集合Ｘのソート番号(j+1) 番の位置に移動させ、既に（j+1)番の位置にあるデータは、(j+ ２) 番目の位置に移動するという形で順次、要素を走査した位置までシフトしていく。
【００８１】
次にカウンタ値から1 を引き（S179ステップ）、処理の先頭（S171ステップ）に戻る。集合Ｃ第２処理が完了するとカウンタＣ値の値をチェックする（図２のS19ステップ ）。
【００８２】
カウンタＣ値が負数（＜０）のときには、集合Ｃの最後尾をソート番号（ｊ−カウンタ値）として、集合Ａ第１処理、集合Ｂ，集合Ｃ第１処理を再度実行する（S21ステップ ）。
【００８３】
カウンタＣ値が０以上のときには、集合Ａの走査を再実行して、集合Ｂのｉ番目より大きい値を集合第２集合Ｂのｉ番目の要素と交換する。交換後、集合Ｂをソートする。
【００８４】
この処理を集合Ａの全要素で実行する（S22ステップ ）。
【００８５】
この実行が完了すると、ソート完了のチェックに入る。
【００８６】
すなわち、集合Ａの再実行でデータ交換したときに、ｊ番目より大きい値が有ったか否かを確認し、有るときは、S23 ステップへ行く。無いときは、集合Ｂのソート番号ｉ番からｊ番目に、ソート結果が得られる。
【００８７】
また、集合Ｃ第１処理が先に完了したときは、集合Ａ第１処理を終了し、集合Ａ第２処理を行う。
【００８８】
図７に集合Ａ第２処理を示す。
【００８９】
集合Ａ内に走査要素の有無をチェックする（S181ステップ）。
【００９０】
走査要素が無ければ処理を終了する。
【００９１】
集合Ｃ内に走査要素があれば、まず集合Ｂの設定範囲幅（ソート番号ｉ〜ｊ  番の幅）をカウンタＡにセットする（S182ステップ）。
【００９２】
次に、集合Ｂのｉ番目より大きい値かをチェックする（S183ステップ）。
【００９３】
集合Ｂのｉ番目より小さければ、処理の先頭（S181ステップ）に戻る。
【００９４】
集合Ｂのｉ番目より大きければ、集合Ｂのｊ番目より小さい値か否かをチェックする（S184ステップ）。
【００９５】
集合Ａの要素が、集合Ｂのｊ番目より小さく集合Ｂのｉ番目より大きい値のときには、集合Ｂのｉ番目の要素と交換し、交換後、集合Ｂは、ソート処理を実行する（S185ステップ）。そして処理の先頭（S181ステップ）に戻る。
【００９６】
集合Ａの要素が集合Ｂのｊ番目より大きい値のときには、カウンタＡ値をチェックする（S186ステップ）。
【００９７】
カウンタＡ値が１以上であれば、その要素と集合Ｂのｉ番目の要素と交換し、交換後、集合Ｂは、ソート処理を実行する（S187ステップ）。
【００９８】
次にカウンタＡ値から1 を引き（S189ステップ）、そして処理の先頭（S181ステップ）に戻る。
【００９９】
カウンタＡ値が０以下であれば、集合Ａの最後尾に走査した要素を移動させる（S188ステップ）。
【０１００】
最後尾への移動は、S188ステップが発生するたびに、集合Ｘのソート番号(i-1) 番目の位置に移動させ、既に(i-1) 番目の位置にあるデータは、(i-2) 番目の位置に移動するという形で順次、要素を走査した位置までシフトしていく。
【０１０１】
次にカウンタＡ値から1 を引き（S189ステップ）、そして処理の先頭（S181ステップ）に戻る。
【０１０２】
集合Ａ第２処理が完了するとカウンタＡ値の値をチェックする（図２のS20ステップ ）。
【０１０３】
カウンタＡ値が負数のときには、集合Ａの先頭を（ｉ＋カウンタ値）として、集合Ａ第１，集合Ｂ，集合Ｃ第１処理を再度実行する（S24ステップ ）。
【０１０４】
カウンタＡ値が０以上のときには、集合Ｃの走査を再実行して、集合Ｂのｊ番目より小さい値を集合Ｂのｊ番目の要素と交換する。交換後、集合Ｂをソートする。この処理を集合Ｃの全要素で実行する（S23ステップ ）。
【０１０５】
この実行が完了すると、ソート完了のチェックに入る。
【０１０６】
すなわち、集合Ｃの再実行によりデータ交換したときに、ｉ番目より小さい値が有ったか否かを確認し、有るときは、S22 ステップへ行く。無いときは、集合Ｂのソート番号ｉ番からｊ番目に、ソート結果が得られる。
【０１０７】
以上のように、すべてのソート処理終了すると、集合Ｂのソート番号のｉ番からｊ番目にソートした結果が求まるのでその結果を結果出力部６へ出力する。
【０１０８】
図８に実施例１のソート処理の具体例の説明図１を示す。
【０１０９】
１５人のグループの試験結果で順位が下から５番目〜９番目の氏名と点数を知りたい例とする。
【０１１０】
点数をキー項目としてそのデータを昇順にソートし、点数の順位が下から５番目〜９番目を抽出する例である。
【０１１１】
まず、データ記億部４から主記憶部５のソード番号１〜15が付与された記憶領域に点数データファイルを読み込む。
【０１１２】
点数データファイルをソート番号１〜５の集合Ａ、ソート番号６〜９の集合Ｂ（求めたい範囲）、ソート番号10〜15の集合Ｃに分割する。
【０１１３】
分割後、集合Ｂを昇順にソートする。
【０１１４】
図９に実施例１のソート処理の具体例の説明図２を示す。
(1) 分割したデータをもとに、まず、集合Ａ第１処理により、集合Ａのソート番号１のデータ「50 」を読み出し、次に集合Ｂのソート番号６のデータ「48」とソート番号９のデータ「100」を読み出す。そして集合Ａのデータを集合Ｂのソート番号６とソート番号９のデータと比較すると、その範囲内にあるため、集合Ａのデータと集合Ｂのソート番号６のデータとを交換する。そしてポインタを集合Ａのソート番号２に移す。
(2) 交換後、集合Ｂをソートする。
(3) 次に、集合Ｃ第１処理により、集合Ｃのソート番号15のデータ「56 」を読み出し、次に集合Ｂのソート番号６のデータ「50」とソート番号９のデータ「100」を読み出す。そして集合Ｃのデータを集合Ｂのソート番号6 とソート番号９のデータと比較すると、その範囲内にあるため、集合Ｃのデータと集合Ｂのソート番号９のデータとを交換する。そしてポインタを集合Ｃのソート番号14に移す。
(4) 交換後、集合Ｂをソートする。
(5) 次に集合Ａのソート番号２のデータ「80 」を読み出し、次に集合Ｂのソート番号６のデータ「50」とソート番号９のデータ「89 」を読み出す。そして集合Ａのデータを集合Ｂのソート番号6 とソート番号９のデータと比較すると、その範囲内にあるため、集合Ａのデータと集合Ｂのソート番号6 のデータとを交換する。そしてポインタを集合Ａのソート番号３に移す。
(6) 交換後、集合Ｂをソートする。
(7) 次に、集合Ｃのソート番号14のデータ「69 」を読み出し、次に集合Ｂのソート番号6 のデータ「56」とソート番号９のデータ「89 」を読み出す。そして集合Ｃのデータを集合Ｂのソート番号6 とソート番号９のデータと比較すると、その範囲内にあるため、集合Ｃのデータと集合Ｂのソート番号９のデータとを交換する。そしてポインタを集合Ｃのソート番号13に移す。
(8) 交換後、集合Ｂをソートする。
(9) 次に集合Ａのソート番号3 のデータ「77 」を読み出し、次に集合Ｂのソート番号6 のデータ「56」とソート番号９のデータ「80 」を読み出す。そして集合Ａのデータを集合Ｂのソート番号6 とソート番号９のデータと比較すると、その範囲内にあるため集合Ａのデータと集合Ｂのソート番号6 のデータとを交換する。そしてポインタを集合Ａのソート番号4 に移す。
(10)交換後、集合Ｂをソートする。
(11)次に、集合Ｃのソート番号13のデータ「88 」を読み出し、次に集合Ｂのソート番号6 のデータ「65」とソート番号９のデータ「80 」を読み出す。そして集合Ｃのデータを集合Ｂのソート番号6 とソート番号９のデータと比較すると、ソート番号９より大きいため、集合Ｃのデータは、そのままとし、ポインタのみをソート番号12へ移す。
(12)次に集合Ａのソート番号４のデータ「99 」を読み出し、次に集合Ｂのソート番号6 のデータ「65」とソート番号９のデータ「80 」を読み出す。そして集合Ａのデータを集合Ｂのソート番号6 とソート番号９のデータと比較すると、ソート番号９より大きいため、集合Ｃのポインタのあるソート番号12のデータ「49 」を読み出す。そして、集合Ｂのソート番号6 のデータ「65」より小さいため、集合Ｃのデータと集合Ａのデータを交換し、集合Ａのポインタをソート番号５に集合Ｃのポインタをソート番号11に移す。
(13)次に、集合Ａのソート番号５のデータ「32 」を読み出し、次に集合Ｂのソート番号6 のデータ「65」とソート番号９のデータ「80 」を読み出す。そして集合Ａのデータを集合Ｂのソート番号6 とソート番号９のデータと比較すると、ソート番号６より小さいため、集合Ａのデータは、そのままとし、集合Ａ１処理を終了する。
【０１１５】
また、集合Ａ１処理の終了により、集合Ｃ１処理も終了する。
【０１１６】
図10に実施例１のソート処理の具体例の説明図３を示す。
(14)集合Ｃ第２処理により、まず、カウンタＣを集合Ｂのデータ数（ソート番号６〜９）の「4」 に設定する。集合Ｃのソート番号11のデータ「30 」を読み出し、次に集合Ｂのソート番号６のデータ「65」とソート番号９のデータ「80 」を読み出す。そして集合Ｃのデータを集合Ｂのソート番号９のデータと比較すると、ソート番号９より小さいため、集合Ｃのデータと集合Ｂのソート番号９のデータとを交換する。そしてポインタを集合Ｃのソート番号10に移す。
また、集合Ｃのデータは集合Ｂのソート番号６のデータと比較すると、小さいため、カウンタＣを−１して「３」に設定する。
(15)集合Ｂをソートする。
(16)集合Ｃのソート番号10のデータ「95 」を読み出し、次に集合Ｂのソート番号６のデータ「30」とソート番号９のデータ「77 」を読み出す。そして集合Ｃのデータを集合Ｂのソート番号９のデータと比較すると、ソート番号９より大きいため、何もせずに終了する。これにより集合Ｃ第２処理が終了する。
(17)次にカウンタＣの内容が「０」以上のため、ポインタをソート番号１に移し、集合Ａのソート番号１のデータ「48 」を読み出し、次に集合Ｂのソート番号６のデータ「30」とソート番号９のデータ「77 」を読み出す。そして集合Ａのデータを集合Ｂのソート番号６とソート番号９のデータと比較すると、その範囲内にあり、ソート番号６より大きいため、集合Ａのデータと集合Ｂのソート番号６のデータとを交換する。そしてポインタを集合Ａのソート番号２に移す。
(18)交換後、集合Ｂをソートする。
(19)集合Ａのソート番号2 のデータ「50 」を読み出し、次に集合Ｂのソート番号６のデータ「48」とソート番号９のデータ「77 」を読み出す。そして集合Ａのデータを集合Ｂのソート番号６とソート番号９のデータと比較すると、その範囲内にあり、ソート番号６より大きいため、集合Ａのデータと集合Ｂのソート番号６のデータとを交換する。そしてポインタを集合Ａのソート番号3 に移す。
(20)交換後、集合Ｂをソートする。
(21)集合Ａのソート番号3 のデータ「56 」を読み出し、次に集合Ｂのソート番号６のデータ「50」とソート番号９のデータ「77 」を読み出す。そして集合Ａのデータを集合Ｂのソート番号６とソート番号９のデータと比較すると、その範囲内にあり、ソート番号６より大きいため、ソート番号６のデータとを交換する。そしてポインタを集合Ａのソート番号4 に移す。
(22)交換後、集合Ｂをソートする。
(23)集合Ａのソート番号4 のデータ「49 」を読み出し、次に集合Ｂのソート番号６のデータ「56」とソート番号９のデータ「77 」を読み出す。そして集合Ａのデータを集合Ｂのソート番号６とソート番号９のデータと比較すると、ソート番号６より集合Ａのデータが小さいため、ポインタのみをソート番号５へ移す。
(24)集合Ａのソート番号5 のデータ「32 」を読み出し、次に集合Ｂのソート番号６のデータ「56」とソート番号９のデータ「77 」を読み出す。そして集合Ａのデータを集合Ｂのソート番号６とソート番号９のデータと比較すると、ソート番号６より集合Ａのデータが小さいため、そのまま何もせずに終わる。
【０１１７】
次に、(17)(19)(21)の処理の中を見ると、集合Ａと集合Ｂの交換データの中に、ソート番号９より大きい値がないため、ソート完了と判断し、集合Ｂのデータをソート結果として出力する。そして、出力されると、ソース結果は、ディスプレイ等に出力される。
【０１１８】
次に主記憶部のすべてに、集合Ｂが搭載できる場合は、問題ないが、搭載できない場合には、集合Ｂの一部が搭載されるデータ記憶部４は、ハードディスクなどで構成されているため、Ｉ／Ｏアクセスが大量に発生して速度劣化を起す。
【０１１９】
このような場合は、ソートする部分のみを主記憶部に分割して搭載し処理を実行することで、速度劣化を防ぐ。
【０１２０】
図11に実施例２のソート処理部の流れ図を示す。
【０１２１】
指定ファイルのデータの集合Ｘ（要素ｎ個の構成）の設定されたソート範囲のデータ（ソート番号ｉ番からｊ番目）のデータを昇順にソートした結果を求める場合について説明する。
【０１２２】
図12に実施例２のソート処理部のデータ集合分割の説明図を示す。
【０１２３】
データ集合分割部３１は、ソート範囲設定部２で入力されたデータを元に、まずｎ個のデータ要素からなる集合Ｘが格納されている記憶領域にソート番号を付与する。
【０１２４】
次に、集合Ｘを集合Ａ（ソート番号1 〜i-1 番目）、１次集合Ｂ（ソート番号i 〜k 番目）、１次集合Ｃ（ソート番号k+1 〜n 番目）に３分類する。
【０１２５】
このとき、主記憶部５に搭載できるデータの値を集合Ｂのｉ番目からｋ番目とする。
【０１２６】
そして、データ記憶部４に記憶されている指定ファイルから設定範囲の搭載部分（ｉ〜ｋ番目）を主記憶部５に複写し、複写された主記憶部５上の記憶領域にソート番号ｉ〜ｋ番を付与する。（S31 ステップ）。
【０１２７】
そして次に実施例１のソート１処理（図２参照）と同様な処理を行う。（S32 ステップ）
各処理の終了により、１次集合Ｂのi 〜k 番目のソート結果が求まる。
【０１２８】
次に、１次集合Ｃを元に、再分類を行う（S33 ステップ）。
【０１２９】
（ｋ＋１）〜ｊ番目の要素は、主記憶部５に搭載できる容量とする。
【０１３０】
１次集合Ｃを２分割し、（k+1 ）〜ｊ番目を２次集合Ｂとし、（j+1 ）〜n 番目を２次集合Ｃとする。そして、２次集合Ｂをデータ記憶部４から主記憶部５に複写する。
【０１３１】
２次集合Ｂをソートする。（S34 ステップ）
そして、２次集合Ｂ処理（S35 ステップ）、２次集合Ｃ処理（S36 ステップ）を行う。２次集合Ｂ処理(S35ステップ）は、図示はしていないが、２次集合Ｃ処理との要素の交換のときごとにソート処理を実行する。
【０１３２】
図13に２次集合Ｃ処理の流れ図を示す。
【０１３３】
まず、２次集合Ｃの場合（最後尾から走査する）、集合内に走査要素の有無を確認する（S361ステップ）。要素がなければ、処理を終了する。
【０１３４】
２次集合Ｃの要素と集合Ｂのｊ番目の要素の値とを比較する（S362ステップ）。
【０１３５】
２次集合Ｃの要素が集合Ｂのｊ番目の要素の値より大きければ、処理の先頭（S361ステップ）に戻る。
【０１３６】
２次集合Ｃの要素が集合Ｂのｊ番目の要素の値より小さい場合は、２次集合Ｃの要素を、２次集合Ｂの要素の集合Ｂのｊ番目の要素の値と交換する（S363ステッフ゜）。
【０１３７】
交換後、２次集合Ｂはソート処理を行い（S35 ステップ）、処理の先頭（S361ス
テップ ）に戻る。
【０１３８】
この処理を集合Ｃの走査要素のなくなるまで、繰り返す。
【０１３９】
処理終了後、１次集合Ｂのソート結果（i 〜k 番目）と２次集合Ｂのソート結果（k+1 〜ｊ番目）とをそのまま結合して、（i 〜j 番目）の集合とすることで、集合Ｂのソートした結果が求まるので、その結果を結果出力部６へ出力する（S37 ステップ）。
【０１４０】
また、図示はしていないが、ソート結果を、結合して出力するのではなく、ユーザに早く結果を知らせるために、ソート結果が求まるたびに結果出力部６へ出力することも可能である。例えば、ソート結果（i 〜k 番目）をまず出力し、その後ソート結果（k+1 〜ｊ番目）が求まった段階で、その内容を出力する。
【０１４１】
【発明の効果】
本発明によれば、ソート対象データの所定の範囲のソート結果を高速に出力することが出来る。
【図面の簡単な説明】
【図１】    実施例のソート装置の構成図
【図２】    実施例１のソート処理部の処理の流れ図
【図３】    実施例１のソート処理部のデータ集合分割の説明図
【図４】    実施例１の集合Ａ第１処理の流れ図
【図５】    実施例１の集合Ｃ第１処理の流れ図
【図６】    実施例１の集合Ｃ第２処理の流れ図
【図７】    実施例１の集合Ａ第２処理の流れ図
【図８】    実施例１のソート処理の具体例の説明図１
【図９】    実施例１のソート処理の具体例の説明図２
【図１０】  実施例１のソート処理の具体例の説明図３
【図１１】  実施例２のソート処理部の処理の流れ図
【図１２】  実施例２のソート処理部のデータ集合分割の説明図
【図１３】  実施例２の２次集合Ｃ処理の流れ図
【図１４】  従来例のソート手順の説明図
【符号の説明】
１      ソート装置
２      ソート範囲設定部
３      ソート処理部
４      データ記憶部
５      主記憶部
６      結果出力部
３１      データ集合分割部
３２      データ交換部
３３      ソート部
３４      ソート完了判別部
【図１】
0003873632.tif 000002
【図２】
0003873632.tif 000003
【図３】
0003873632.tif 000004
【図４】
0003873632.tif 000005
【図５】
0003873632.tif 000006
【図６】
0003873632.tif 000007
【図７】
0003873632.tif 000008
【図８】
0003873632.tif 000009
【図９】
0003873632.tif 000010
【図１０】
0003873632.tif 000011
【図１１】
0003873632.tif 000012
【図１２】
0003873632.tif 000013
【図１３】
0003873632.tif 000014
【図１４】
0003873632.tif 000015