(57)【要約】【課題】  特殊なハードを用いることなく、ソート時間を短縮し、また、途中で処理を中断してソート結果を取得可能とする。【解決手段】  比較制御部６は、最後の１つに絞り込めるまで、比較対象である隣り合うデータ同士を比較し、大きい方のデータ（または小さい方）を一時データ配列部３に保持する。また、比較制御部６は、最後まで残ったデータを前記一時データ配列部３に記憶されている比較対象から除外する。出力制御部１２は、最後まで残ったデータを順番に出力データ配列部１３に格納する。比較制御部６は、比較対象となる全データが出力データ配列部１３に保持されるまで、繰り返し比較を行なう。また、出力制御部１２は、ソート結果が要求データ数１１に達すると、ソート処理を途中で終了させる。【選択図】  図１
2005038338.tif 000002
【特許請求の範囲】
【請求項１】
比較対象となるデータを降順または昇順に並び替えるソート回路において、
最後の１つに絞り込めるまで、大きい方のデータまたは小さい方のデータを保持しながら、比較対象となる隣り合うデータ同士を比較する比較手段と、
前記比較手段による比較結果を、前記比較手段による比較対象として保持する一時データ記憶手段と、
最後まで残ったデータを順番に格納する出力データ記憶手段と、
最後まで残ったデータを前記一時データ記憶手段に記憶されている比較対象から除外する比較対象除外手段と、
比較対象となる全データが前記出力データ記憶手段に保持されるまで、前記比較手段による比較を繰り返させる制御手段と
を具備することを特徴とするソート回路。
【請求項２】
前記比較手段は、
比較対象となる隣り合うデータ同士が既に比較されている場合、そのデータ同士を比較することなく、前回の比較結果を採用することを特徴とする請求項１記載のソート回路。
【請求項３】
比較対象となるデータを格納するデータ記憶手段と、
前記比較対象となるデータが格納されている場所を示す格納位置情報を取得する格納位置取得手段とを具備し、
前記一時データ記憶手段は、前記格納位置取得手段により取得された格納位置情報を保持し、
前記比較手段は、前記一時データ記憶手段に記憶されている格納位置情報に基づいて、比較対象となるデータを前記データ記憶手段から読み出して比較することを特徴とする請求項１または２記載のソート回路。
【請求項４】
前記出力データ記憶手段に保持されるデータ数を設定するための要求データ数設定手段を具備し、
前記出力データ記憶手段に格納されるデータ数が前記要求データ数設定手段により設定されたデータ数に達すると、ソート動作を停止することを特徴とする請求項１記載のソート回路。
【請求項５】
前記比較手段は、最後の１つに絞り込めるまで、大きい方のデータおよび小さい方のデータを保持しながら、比較対象となる隣り合うデータ同士の大小比較を並行して行ない、
前記一時データ記憶手段は、前記比較手段による大小比較の双方の比較結果を、前記比較手段による比較対象として保持し、
前記出力データ記憶手段は、最後まで大きい値として残ったデータを先頭から順に、最後まで小さい値として残ったデータを最後尾から順に保持することを特徴とする請求項１記載のソート回路。
【請求項６】
最後の１つに絞り込めるまで、大きい方のデータまたは小さい方のデータを保持しながら、比較対象となる隣り合うデータ同士を比較し、
最後まで残ったデータを順番にソート結果として格納し、
最後まで残ったデータを比較対象から除外し、
比較対象となる全データがソート結果として保持されるまで、前記隣り合うデータ同士の比較を繰り返すことを特徴とするソート方法。
【請求項７】
前記比較対象となる隣り合うデータ同士が既に比較されている場合、そのデータ同士を比較することなく、前回の比較結果を採用することを特徴とする請求項６記載のソート方法。
【請求項８】
前記比較対象となるデータが格納されている場所を示す格納位置情報に基づいて、比較対象となるデータを参照して比較し、前記格納位置情報を、比較対象となる隣り合うデータを示す情報として保持することを特徴とする請求項６または７記載のソート方法。
【請求項９】
前記ソート結果として取得すべきデータ数を設定可能とし、
前記ソート結果として格納されるデータ数が前記設定されたデータ数に達すると、ソート動作を停止することを特徴とする請求項６記載のソート方法。
【請求項１０】
最後の１つに絞り込めるまで、大きい方のデータおよび小さい方のデータを保持しながら、比較対象となる隣り合うデータ同士の大小比較を並行して行ない、前記大小比較の双方の比較結果を、前記比較対象として保持し、最後まで大きい値として残ったデータを先頭から順に、最後まで小さい値として残ったデータを最後尾から順にソート結果として格納することを特徴とすることを特徴とする請求項６記載のソート方法。
【請求項１１】
最後の１つに絞り込めるまで、大きい方のデータまたは小さい方のデータを保持しながら、比較対象となる隣り合うデータ同士を比較するステップと、
最後まで残ったデータを順番にソート結果として格納するステップと、
最後まで残ったデータを比較対象から除外するステップと、
比較対象となる全データがソート結果として保持されるまで、前記隣り合うデータ同士の比較を繰り返すステップと
をコンピュータに実行させることを特徴とするソートプログラム。
【請求項１２】
前記比較対象となる隣り合うデータ同士が既に比較されている場合、そのデータ同士を比較することなく、前回の比較結果を採用するステップをコンピュータに実行させることを特徴とする請求項１１記載のソートプログラム。
【請求項１３】
前記ソート結果として取得すべきデータ数を設定するステップと、
前記ソート結果として格納されるデータ数が前記設定されたデータ数に達すると、ソート動作を停止するステップと
をコンピュータに実行させることを特徴とする請求項１１記載のソートプログラム。
【請求項１４】
最後の１つに絞り込めるまで、大きい方のデータまたは小さい方のデータを保持しながら、比較対象となる隣り合うデータ同士を比較するステップと、
最後まで残ったデータを順番にソート結果として格納するステップと、
最後まで残ったデータを比較対象から除外するステップと、
比較対象となる全データがソート結果として保持されるまで、前記隣り合うデータ同士の比較を繰り返すステップと
をコンピュータに実行させるソートプログラムを記録したことを特徴とする記録媒体。
【請求項１５】
前記比較対象となる隣り合うデータ同士が既に比較されている場合、そのデータ同士を比較することなく、前回の比較結果を採用するステップをコンピュータに実行させるソートプログラムを記録したことを特徴とする請求項１４記載の記録媒体。
【請求項１６】
前記ソート結果として取得すべきデータ数を設定するステップと、
前記ソート結果として格納されるデータ数が前記設定されたデータ数に達すると、ソート動作を停止するステップと
をコンピュータに実行させるソートプログラムを記録したことを特徴とする請求項１４記載の記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソート回路、ソート方法、ソートプログラムおよび記録媒体に関する。
【背景技術】
【０００２】
従来のソート方法では、ただ単にアルゴリズムを単純にしてソートを行うことが多かった。そのため、一例を挙げると、（１）基本交換法（バブルソート）などにおいては、ソートするデータの数がＮ倍になると、計算量がＮ２倍になる。これは、データ量が１０倍になると計算量は１００倍になり、データの量が１００倍になると計算量は１０，０００倍になることを意味する。このような計算量を「Ｏ（Ｎ２）」と示す。データ数がＮ倍になると、計算量はＮ２倍になるという意味である。その他、（２）基本選択法（直接選択法）、（３）基本挿入法もＯ（Ｎ２）の計算量になる。
【０００３】
このように、データ数の増大により、処理量が指数関数的に伸びてしまうという問題を解決するために、その他のアルゴリズムが考案されてきた。その中でも最も有名なものが（４）クイックソート（改良交換法）と呼ばれるアルゴリズムを用いたソート方法である。このクイックソートでは、計算量はＯ（Ｎ ｌｏｇ２Ｎ）になる。これは、データ数がＮ倍になると、計算量はＯ（Ｎ ｌｏｇ２Ｎ）倍になるという意味である。仮にデータ数が１０倍になるとすると、計算量はおよそ３３倍になる。データ数が１００倍になると、計算量はおよそ６６４倍になる計算である。
【０００４】
一見、クイックソートでは、基本交換法などよりも計算量の増加量を抑制することができたように見える。しかし、クイックソートのＯ（Ｎ ｌｏｇ２Ｎ）の計算量は、平均計算量であり、ソートする前のデータの並び方や、基準値の選び方によっては、最大計算量は基本交換法などと同じＯ（Ｎ２）になることも知られている。
【０００５】
この処理量の増大に対処したアルゴリズムが、（５）マージソートである。マージソートでは、計算量がＯ（Ｎ ｌｏｇ２Ｎ）になる。しかも、データの並びによる影響をほとんど受けないのである。しかし、マージソートだけではなく、クイックソートについても同様であるが、これらのソートアルゴリズムでは、ソート処理が完全に最後まで終了しないと、ソート順が決定しない。
【０００６】
このように、様々なソートアルゴリズムが存在する。しかしながら、これまで見てきたように、どれも一長一短であるのが現状である。利用者は（システム開発者は）、データを並び替える際の様々な状況を考慮したうえで、最適なソート方法を選ばなければならないのである。
【０００７】
また、（６）その他のソート方法として、複数の比較を同時に行なうことにより、計算量を削減する技術が提案されている（例えば特許文献１参照）。例えば、通常、１５回の比較が必要とされる５つのデータを並び替える場合、２組の数値の比較を１回としてカウントすると、前述した（１）基本交換法（バブルソート）で行なうと、１０回の比較が必要となる。これに対して、該ソート方法によれば、複数の比較を同時に行なうことができるので、９回の動作で完了することができる。これによって、処理結果出力までの時間を短縮することに成功している。
【特許文献１】特開平１０−１４９２７６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
このように、上述した従来技術において、上記（１）基本交換法（バブルソート）、上記（２）基本選択法（直接選択法）および上記（３）基本挿入法では、計算量の増大に対応できない。これらのソートアルゴリズムでは、データ数が増加したときの計算量の増大を抑制することができないため、大量のデータをソートする場合に、著しく時間がかかってしまうという問題がある。
【０００９】
また、上記（４）クイックソートでは、計算量の増大を抑制するものの、場合によっては計算量が著しく増加してしまい、処理に時間がかかってしまう。クイックソートの場合、基準値としてあるデータを選び、その基準値よりも大きいデータと小さいデータに振り分けることを繰り返して整列を行なう。この基準値が、整列された後の配列の右端や左端にくるような値に近いほど、高速な処理を行なうことができない。
【００１０】
基準値の選び方には、様々な方法がある。理想的には、ソート対象データ中で、中央の値を持つデータを基準値とするのが一番よい（例えば、３１，４１，５９，２６，５３の５つのデータがソート対象の場合、真ん中の値である４１を基準値とするということ）。しかしながら、中央の値を求めると、整列するのと同様の手間がかかってしまう。そこで、配列の中央にあるデータを基準とする方法や（３１，４１，５９，２６，５３の５つのデータがソート対象の場合、先頭から３番目にある５９を基準値とするということ）、先頭または最後にあるデータを基準とする方法もある（３１，４１，５９，２６，５３の５つのデータがソート対象の場合、先頭から１番目にある３１、または最後の５３を基準値とするということ）。いずれにしても、中央の値がどれなのかを計算に基づいて決定するわけではないので、計算量が増大する可能性がある。
【００１１】
また、従来技術によるソート方法では、データを逐一で把握することができない。すなわち、整列結果を順次把握することができず、すべての処理が終了するのを待つしかない。上記（１）基本交換法（バブルソート）、上記（２）基本選択法（直接選択法）では、大きな（または、小さな）データがどれであるのかを逐一確認しながらソートを行なう。しかし、処理量が、データ数の増加に伴って爆発的に増加してしまうというデメリットがある。
【００１２】
また、処理量の増大を解決した上記（４）クイックソートや上記（５）マージソートでは、処理の最後にならないと、どのデータが大きいか（または、小さいか）が分からない。具体的には、６５，５３６件のデータの中から最も大きな（小さな）１００件を選び出す場合、基本選択法および基本交換法では、６，５５０，０００回の比較を行なえば、１００件のデータがどれであるのかを把握することができる。６５，５３６件のデータをすべて並べ替える場合は、およそ２１．５億回の比較が必要である。
【００１３】
しかし、上記（４）クイックソートや上記（５）マージソートでは、処理量の増加が抑制されるため、６５，５３６件すべてを並べ替えても、およそ１００万回で終了する。ところが、最後の方まで処理を行わないと、６５，５３６件のうちの１００件を選び出すことができない。つまり、６５，５３６件すべてを並び替える場合でも、６５，５３６件の中から１００件を選び出す場合でも、どちらも大差ない量の処理を行なわなければならなくなる。
【００１４】
例えば、上記（５）マージソートでは、既に整列された２個以上の配列を１つの配列に併合する処理を繰り返すことでソートを実現している。例えば、「３１，４１，５９，２６，５３」の５つのデータを降順にマージソートでソートする過程は次のようになる。
【００１５】
まず、データを２分割することを繰り返す。この場合は、「３１，４１，５９」と「２６，５３」に分割する。次に、それぞれを更に２分割する。「３１，４１，５９」は「３１，４１」と「５９」に分割する。「２６，５３」は「２６」と「５３」に分割する。さらに、まだ１つになっていないデータ「３１，４１」を「３１」と「４１」に分割する。
【００１６】
このように、分割できなくなるまでデータを２分割したあと、それらをマージすることを繰り返す。まず、先頭から「３１」と「４１」をマージする。その結果、「４１，３１」を得る。次に、この「４１，３１」と先ほどの「５９」をマージして、「５９，４１，３１」を得る。また、これとは別に「２６」と「５３」をマージして「５３，２６」を得る。最後に、「５９，４１，３１」と「５３，２６」をマージして、「５９，５３，４１，３１，２６」を得る。
【００１７】
このように、マージソートでは、ソートをすべて完了させないと、ソートされたデータを得ることができない。たとえば、１００万個のデータの中から、もっとも大きな１００個についてのデータを集めるような場合でも、すべての並べ替えを完了させなければならない。
【００１８】
また、上記（６）その他のソート方法（特許文献１）では、複数の比較を同時に行えるという利点があるが、同じ数値が何度も比較されており、比較回数が多い。また、複数の比較を一度に同じタイミングで行なうことは、複数の処理装置（比較を行なうための特殊なＣＰＵのような装置）が必要であることを意味し、特殊なハードを必要とするという問題がある。
【００１９】
この発明は上述した事情に鑑みてなされたもので、特殊なハードを用いることなく、比較回数を削減することにより短時間でソートを行なうことができ、また、途中で処理を中断して結果を得ることができるソート回路、ソート方法、ソートプログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００２０】
上述した問題点を解決するために、請求項１記載の発明では、比較対象となるデータを降順または昇順に並び替えるソート回路において、最後の１つに絞り込めるまで、大きい方のデータまたは小さい方のデータを保持しながら、比較対象となる隣り合うデータ同士を比較する比較手段と、前記比較手段による比較結果を、前記比較手段による比較対象として保持する一時データ記憶手段と、最後まで残ったデータを順番に格納する出力データ記憶手段と、最後まで残ったデータを前記一時データ記憶手段に記憶されている比較対象から除外する比較対象除外手段と、比較対象となる全データが前記出力データ記憶手段に保持されるまで、前記比較手段による比較を繰り返させる制御手段とを具備することを特徴とする。
【００２１】
また、請求項２記載の発明では、請求項１記載のソート回路において、前記比較手段は、比較対象となる隣り合うデータ同士が既に比較されている場合、そのデータ同士を比較することなく、前回の比較結果を採用することを特徴とする。
【００２２】
また、請求項３記載の発明では、請求項１または２記載のソート回路において、比較対象となるデータを格納するデータ記憶手段と、前記比較対象となるデータが格納されている場所を示す格納位置情報を取得する格納位置取得手段とを具備し、前記一時データ記憶手段は、前記格納位置取得手段により取得された格納位置情報を保持し、前記比較手段は、前記一時データ記憶手段に記憶されている格納位置情報に基づいて、比較対象となるデータを前記データ記憶手段から読み出して比較することを特徴とする。
【００２３】
また、請求項４記載の発明では、請求項１記載のソート回路において、前記出力データ記憶手段に保持されるデータ数を設定するための要求データ数設定手段を具備し、前記出力データ記憶手段に格納されるデータ数が前記要求データ数設定手段により設定されたデータ数に達すると、ソート動作を停止することを特徴とする。
【００２４】
また、請求項５記載の発明では、請求項１記載のソート回路において、前記比較手段は、最後の１つに絞り込めるまで、大きい方のデータおよび小さい方のデータを保持しながら、比較対象となる隣り合うデータ同士の大小比較を並行して行ない、前記一時データ記憶手段は、前記比較手段による大小比較の双方の比較結果を、前記比較手段による比較対象として保持し、前記出力データ記憶手段は、最後まで大きい値として残ったデータを先頭から順に、最後まで小さい値として残ったデータを最後尾から順に保持することを特徴とする。
【００２５】
また、上述した問題点を解決するために、請求項６記載の発明では、最後の１つに絞り込めるまで、大きい方のデータまたは小さい方のデータを保持しながら、比較対象となる隣り合うデータ同士を比較し、最後まで残ったデータを順番にソート結果として格納し、最後まで残ったデータを比較対象から除外し、比較対象となる全データがソート結果として保持されるまで、前記隣り合うデータ同士の比較を繰り返すことを特徴とする。
【００２６】
また、請求項７記載の発明では、請求項６記載のソート方法において、前記比較対象となる隣り合うデータ同士が既に比較されている場合、そのデータ同士を比較することなく、前回の比較結果を採用することを特徴とする。
【００２７】
また、請求項８記載の発明では、請求項６または７記載のソート方法において、前記比較対象となるデータが格納されている場所を示す格納位置情報に基づいて、比較対象となるデータを参照して比較し、前記格納位置情報を、比較対象となる隣り合うデータを示す情報として保持することを特徴とする。
【００２８】
また、請求項９記載の発明では、請求項６記載のソート方法において、前記ソート結果として取得すべきデータ数を設定可能とし、前記ソート結果として格納されるデータ数が前記設定されたデータ数に達すると、ソート動作を停止することを特徴とする。
【００２９】
また、請求項１０記載の発明では、請求項６記載のソート方法において、最後の１つに絞り込めるまで、大きい方のデータおよび小さい方のデータを保持しながら、比較対象となる隣り合うデータ同士の大小比較を並行して行ない、前記大小比較の双方の比較結果を、前記比較対象として保持し、最後まで大きい値として残ったデータを先頭から順に、最後まで小さい値として残ったデータを最後尾から順にソート結果として格納することを特徴とすることを特徴とする。
【００３０】
また、上述した問題点を解決するために、請求項１１記載の発明では、最後の１つに絞り込めるまで、大きい方のデータまたは小さい方のデータを保持しながら、比較対象となる隣り合うデータ同士を比較するステップと、最後まで残ったデータを順番にソート結果として格納するステップと、最後まで残ったデータを比較対象から除外するステップと、比較対象となる全データがソート結果として保持されるまで、前記隣り合うデータ同士の比較を繰り返すステップとをコンピュータに実行させることを特徴とする。
【００３１】
また、請求項１２記載の発明では、請求項１１記載のソートプログラムにおいて、前記比較対象となる隣り合うデータ同士が既に比較されている場合、そのデータ同士を比較することなく、前回の比較結果を採用するステップをコンピュータに実行させることを特徴とする。
【００３２】
また、請求項１３記載の発明では、請求項１１記載のソートプログラムにおいて、前記ソート結果として取得すべきデータ数を設定するステップと、前記ソート結果として格納されるデータ数が前記設定されたデータ数に達すると、ソート動作を停止するステップとをコンピュータに実行させることを特徴とする。
【００３３】
また、上述した問題点を解決するために、請求項１４記載の発明では、最後の１つに絞り込めるまで、大きい方のデータまたは小さい方のデータを保持しながら、比較対象となる隣り合うデータ同士を比較するステップと、最後まで残ったデータを順番にソート結果として格納するステップと、最後まで残ったデータを比較対象から除外するステップと、比較対象となる全データがソート結果として保持されるまで、前記隣り合うデータ同士の比較を繰り返すステップとをコンピュータに実行させるソートプログラムを記録したことを特徴とする。
【００３４】
また、請求項１５記載の発明では、請求項１４記載の記録媒体において、前記比較対象となる隣り合うデータ同士が既に比較されている場合、そのデータ同士を比較することなく、前回の比較結果を採用するステップをコンピュータに実行させるソートプログラムを記録したことを特徴とする。
【００３５】
また、請求項１６記載の発明では、請求項１４記載の記録媒体において、前記ソート結果として取得すべきデータ数を設定するステップと、前記ソート結果として格納されるデータ数が前記設定されたデータ数に達すると、ソート動作を停止するステップとをコンピュータに実行させるソートプログラムを記録したことを特徴とする。
【００３６】
この発明では、比較手段により、最後の１つに絞り込めるまで、大きい方のデータまたは小さい方のデータを一時データ記憶手段に保持しながら、比較対象となる隣り合うデータ同士を比較し、最後まで残ったデータを順番に出力データ記憶手段に保持し、比較対象除外手段により、最後まで残ったデータを前記一時データ記憶手段に記憶されている比較対象から除外し、制御手段により、比較対象となる全データが前記出力データ記憶手段に保持されるまで、前記比較手段による比較を繰り返させる。したがって、特殊なハードを用いることなく、比較回数を削減することにより短時間でソートを行なうことが可能となる。また、前記出力データ記憶手段に格納されるデータ数が前記要求データ数設定手段により設定されたデータ数に達すると、ソート動作を停止するようにしたので、途中で処理を中断して結果を得ることが可能となる。
【発明の効果】
【００３７】
以上説明したように、本発明によれば、比較手段により、最後の１つに絞り込めるまで、大きい方のデータまたは小さい方のデータを一時データ記憶手段に保持しながら、比較対象となる隣り合うデータ同士を比較し、最後まで残ったデータを順番に出力データ記憶手段に保持し、比較対象除外手段により、最後まで残ったデータを前記一時データ記憶手段に記憶されている比較対象から除外し、制御手段により、比較対象となる全データが前記出力データ記憶手段に保持されるまで、前記比較手段による比較を繰り返させるようにしたので、特殊なハードを用いることなく、比較回数を削減することにより短時間でソートを行なうことができるという利点が得られる。また、前記出力データ記憶手段に格納されるデータ数が前記要求データ数設定手段により設定されたデータ数に達すると、ソート動作を停止するようにしたので、途中で処理を中断して結果を得ることができるという利点が得られる。
【発明を実施するための最良の形態】
【００３８】
以下、図面を用いて本発明の実施の形態を説明する。
Ａ．実施形態
Ａ−１．実施形態の構成
図１は、本発明の実施形態によるソート装置の構成を示すブロック図である。図１において、入力データ配列部１は、一次元配列からなり、ソート対象となる入力データを格納する。配列番号取得部２は、入力データ配列部１に格納された入力データの配列順番を示す配列番号を取得し、一時データ配列部３に供給する。一時データ配列部３は、２次元配列からなり、上記入力データの配列番号を格納するとともに、ソート途中の結果（配列番号）を一時的に格納する。
【００３９】
参照カウンタ４は、後述する実データ参照部５において、一時データ配列部３の２次元配列をアクセスするための配列セル番号を順次出力する。実データ参照部５は、参照カウンタ４からの配列セル番号に従って、一時データ配列部３の２次元配列をアクセスし、大小比較するための入力データに対応する配列番号を取得し、該配列番号に従って、入力データ配列部１から実データを参照して比較制御部６へ供給する。比較制御部６は、実データ参照部５からの大小比較するための入力データを比較し、昇順であれば小さい方の入力データの配列番号を転送部９へ供給する一方、降順であれば大きい方の入力データの配列番号を転送部９へ供給する。
【００４０】
トーナメントの深さ数７は、本実施形態によるソート方法において入力データをソートする際に必要とされる比較階層（トーナメント）レベル（後述）を示すデータである。該トーナメント深さ数７は、比較制御部６において、各トーナメントの中で最も大きな入力データ（または、小さいデータ）が決定されたかを判断するために用いられる。一時データ数８は、一次元配列であり、各トーナメントの深さ（階層）に対する、一時データ配列部３における一時データ配列の要素数（具体的には、本実施形態では、トーナメントの深さ「１」階層目に対して５個、トーナメントの深さ「２」階層目に対して３個、トーナメントの深さ「３」階層目に対して２個、トーナメントの深さ「４」階層目に対して１個）を記憶する。
【００４１】
転送部９は、比較制御部６からの比較結果、すなわち、昇順であれば小さい方の入力データの配列番号、または降順であれば大きい方の入力データの配列番号を、参照カウンタ４からの配列セル番号から算出した、比較結果を格納するための一時データ配列部３の配列セル番号に格納する。したがって、一時データ配列部３の２次元配列には、各トーナメントレベルにおける大小比較の途中結果が格納されることになる。
【００４２】
出力カウンタ１０は、現在、何番目に大きなデータ（または小さなデータ）を、後述する出力データ配列部１３に格納し終えたかを示す、出力データ配列部１３の配列セル番号を出力する。要求データ数１１は、大きなデータ（または小さなデータ）の何番目までをソートすればよいかを示すデータである。該要求データ数１１は、ユーザにより設定可能となっている。これにより、要求データ数に達した時点でソート処理を停止することが可能となっている。
【００４３】
出力制御部１２は、一時データ配列部３の２次元配列から最も大きな入力データ（または最も小さな入力データ）を示す配列番号を取得し、該配列番号に従って入力データ配列部１から対応する入力データを取得し、出力カウンタ１０からの配列セル番号に従って出力データ配列部１３に供給する。また、出力制御部１２は、要求データ数１１を参照し、出力カウンタ１０の配列セル番号が要求データ数に達すると、ソート処理を終了するようになっている。出力データ配列部１３は、出力制御部１２からの各トーナメントにおけるソート結果である、最も大きな入力データ（または最も小さな入力データ）を順次格納するための一次元配列からなる。
【００４４】
Ａ−２．実施形態の動作
次に、本実施形態の動作について詳細に説明する。ここで、図２ないし図５は、本実施形態によるソート方法の動作を説明するためのフローチャートである。また、図６は、実データとして、「３１」、「４１」、「５９」、「２６」、「５３」をソートする場合の入力データ配列、一時データ配列および出力データ配列の構成を示す概念図である。また、図７ないし図１１は、図６に示す例において、本実施形態によるソート方法において降順に並び替える場合の動作を説明するための概念図である。なお、図７ないし図１１では、説明を簡単にするために、一時データ配列に実データを記しているが、実際には、対応する実データの配列番号が格納されるようになっている。
【００４５】
まず、実データ数Ｎが入力されると（ステップＳ１０）、該Ｎ個の実データをソートするためのトーナメントの深さ数Ｔを取得し、トーナメントの深さ数７に格納する（ステップＳ１２）。図６に示す例では、実データ数Ｎは「５」となり、トーナメントの深さ数Ｔは「４」となる。次に、上記Ｎ個の実データを格納するための入力データ配列［１］〜［Ｎ］を入力データ配列部１に確保する（ステップＳ１４）。実データ数Ｎが「５」の場合、入力データ配列［１］〜［５］が確保される。同様に、図６（ｂ）に示すように、各階層に対応した一時データ配列［１］［Ｎ］〜［Ｔ］［１］を一時データ配列部３に確保し（ステップＳ１６）、図６（ｃ）に示すように、出力データ配列［１］〜［Ｎ］を出力データ配列部１３に確保する（ステップＳ１８）。
【００４６】
次に、図６（ａ）に示すように、入力データ配列部１の入力データ配列［１］〜［Ｎ］に実データを順次格納し（ステップＳ２０）、配列番号取得部２により、実データの配列番号を取得し、該実データの配列番号を、図６（ｂ）に示すように、一時データ配列部３の一時データ配列［１］［１］〜［１］［Ｎ］に格納する（ステップＳ２２）。次に、トーナメントの深さ毎に、一時データ配列の要素数を、一時データ数８の一次元配列に取得し（ステップＳ２４）、要求データ数１１を入力させる（ステップＳ２６）。そして、比較対象の一時データ配列を［１］とする（ステップＳ２８）。
【００４７】
次に、図３に示すように、実データ参照部５により、一時データ配列の配列番号を参照し、比較制御部６により、隣同士の実データを比較する（ステップＳ３０）。次に、比較した結果、大きい方（または小さい方）の実データの配列番号を一段上の一時データ配列に格納する（ステップＳ３２）。次に、次の実データがあるか否かを判断し（ステップＳ３４）、次の実データがあれば、その隣に比較すべき実データがあるか否かを判断する（ステップＳ３６）。これは、実データの最後を検出するためと、実データが奇数個である場合に最後の１つは隣り合う実データがないことを検出するためである。そして、比較すべき２つの実データがある場合には、ステップＳ３０へ戻り、上述したように、実データ同士の大小比較を行なう。以下、次の実データがなくなるか、あるいは最後の１つになるまで、上述したように、隣り合う実データ同士を比較する。実データが奇数個である場合には、最後に１つの実データが残るので、該最後の実データの配列番号をそのまま一段上の一時データ配列に格納する（ステップＳ３８）。
【００４８】
図６に示す例では、まず、一時データ配列［１］［１］の配列番号で示される実データ「３１」と一時データ配列［１］［２］の配列番号で示される実データ「４１」とが比較される。この例では、実データ「３１」と「４１」とが比較されるので、図７に示すように、大きい方の実データ「４１」（実際には配列番号「２」）が一時データ配列［２］［１］に格納される（図示の黒丸は比較動作を示す）。以下、同様にして、一時データ配列［１］［３］の配列番号で示される実データ「５９」と一時データ配列［１］［４］の配列番号で示される実データ「２６」とが比較され、図７に示すように、大きい方の実データ「５９」（実際には配列番号「３」）が一時データ配列［２］［２］に格納される。そして、一時データ配列［１］［５］の配列番号で示される実データ「５３」には比較対象となる隣の実データがないので、図７に示すように、該実データ「５３」（実際には配列番号「５」）がそのまま一時データ配列［２］［３］に格納される（図示の四角は上書き動作を示す）。
【００４９】
次に、比較制御部６では、トーナメントの深さ数７に従って、最後の１つに絞れたか否か、すなわち最も大きな入力データ（または、小さいデータ）が決定されたかを判断する（ステップＳ４０）。そして、最後の１つに絞れていない場合には、比較対象の一時データ配列を一段上げ（ステップＳ４２）、ステップＳ３０へ戻り、上述した処理を繰り返す。
【００５０】
図７に示す例では、比較対象が一時データ配列［２］［１］〜［２］［３］となり、一時データ配列［２］［１］の配列番号で示される実データ「４１」と一時データ配列［２］［２］の配列番号で示される実データ「５９」とが比較され、大きい方の実データ「５９」（実際には配列番号「３」）が一時データ配列［３］［１］に格納される。そして、一時データ配列［２］［３］の配列番号で示される実データ「５３」には比較対象となる隣の実データがないので、該実データ「５３」（実際には配列番号「５」）がそのまま一時データ配列［３］［２］に格納される。
【００５１】
次に、比較対象が一時データ配列［３］［１］、［３］［２］となり、一時データ配列［３］［１］の配列番号で示される実データ「５９」と一時データ配列［３］［２］の配列番号で示される実データ「５３」とが比較され、大きい方の実データ「５９」（実際には配列番号「３」）が一時データ配列［４］［１］に格納される。このように、最後の１つに絞り込まれるまで、比較と格納を繰り返した結果、最終的に残った実データ「５９」は、入力データの中で最大のものである。
【００５２】
最後の１つに絞り込まれると（ステップＳ４０ＹＥＳ）、出力制御部１２により、最終的に絞り込んだ配列番号の実データを入力データ配列部１から取得し、出力データ配列部１３における、出力カウンタ１０からの配列番号に格納する（ステップＳ４４）。
【００５３】
したがって、図７に示す例では、出力データ配列［１］に実データ「５９」が格納されることになる。
【００５４】
次に、要求データ数１１に達したか否かを判断し（ステップＳ４６）、要求データ数に達していなければ、ソートが終了したか否かを判断する（ステップＳ４８）。そして、ソートが終了していなければ、最終的に絞り込んだ配列番号を一時データ配列から除外する（ステップＳ５０）。除外する方法として考えられるのは、最終的に絞り込んだ配列番号が格納されていた一時データ配列［１］［ｘ］に、配列番号としてはありえないマイナスの値を格納すればよい。
【００５５】
図８に示す例では、一時データ配列［１］［３］に斜線を記して「除外」を示しているが、この場合、マイナスの値を格納している。
【００５６】
次に、図４において、除外した一時データ配列を注目対象とする（ステップＳ５２）。次に、注目対象である一時データ配列に対して比較対象となる一時データ配列があるか否かを判断する（ステップＳ５４）。これは、注目対象である一時配列、すなわち上記除外した一時配列が奇数番目の配列で、かつ最後の配列であるかを判断している。奇数番目の配列で、かつ最後尾の配列である場合、その一時配列には比較対象となる配列が存在しないことを示す。そして、注目対象である一時配列、すなわち除外した一時配列が奇数番目の配列で、かつ最後の配列である場合には、比較対象の配列がないので、注目対象の実データの配列番号を一段上の一時データ配列に格納する（ステップＳ５５）。そして、この一段上の一時データ配列を注目対象として比較対象の一時データ配列を一段上げ（図５に示すステップＳ７０）、ステップＳ５４へ戻り、上述した処理を繰り返す。
【００５７】
一方、注目対象である一時配列、すなわち除外した一時配列が奇数番目の配列で、かつ最後の配列でない場合には、大小比較すべき比較対象の配列があるということなので、その注目対象の一時配列が除外されているか否かを判断する（ステップＳ５６）。そして、注目対象の一時配列が除外されている場合には、比較対象の実データの配列番号を一段上の一時データ配列に格納する（ステップＳ５８）。
【００５８】
次に、比較制御部６では、トーナメント深さ数７に従って、最後の１つに絞れたか否か、すなわち最も大きな入力データ（または、小さいデータ）が決定されたかを判断し（ステップＳ６８）、最後の１つに絞れていなければ、比較対象の一時データ配列を一段上げ（図５に示すステップＳ７０）、ステップＳ５４へ戻り、上述した処理を繰り返す。
【００５９】
ここで、注目対象の一時データ配列に比較対象の配列があり、かつ注目対象の配列が除外されていなければ、比較対象の配列が除外されているか否かを判断する（ステップＳ６０）。ここで、比較対象の配列が除外されていれば、注目対象の実データの配列番号を一段上の一時データ配列に格納する（ステップＳ６２）。次に、最後の１つに絞れたか否かを判断し（ステップＳ６８）、最後の１つに絞れていなければ、比較対象の一時データ配列を一段上げ（図５に示すステップＳ７０）、ステップＳ５４へ戻り、上述した処理を繰り返す。
【００６０】
また、注目対象の一時データ配列に比較対象の配列があり、かつ注目対象の配列が除外されておらず、さらに、比較対象の配列が除外されていなければ、一時データ配列の配列番号を参照し、隣同士である注目対象と比較対象とで示される実データ同士を比較する（ステップＳ６４）。そして、比較した結果、大きい方（または小さい方）の実データの配列番号を一段上の一時データ配列に格納する（ステップＳ６６）。次に、最後の１つに絞れたか否かを判断し（ステップＳ６８）、最後の１つに絞れていなければ、比較対象の一時データ配列を一段上げ（図５に示すステップＳ７０）、ステップＳ５４へ戻り、上述した処理を繰り返す。
【００６１】
例えば、図８に示すように、一時データ配列［１］［３］の配列番号で示される実データ［５９］が除外されている場合、まず、該一時データ配列［１］［３］を注目対象とする。この場合、該一時データ配列［１］［３］には、比較対象として一時データ配列［１］［４］が存在し、かつ、一時データ配列［１］［３］が除外されているので、比較対象である一時データ配列［１］［４］で示される実データ「２６」の配列番号が一段上の一時データ配列［２］［２］に格納されることになる。
【００６２】
次に、一時データ配列［２］［２］が注目対象となる。この場合、該一時データ配列［２］［２］には、比較対象として一時データ配列［２］［１］が存在し、かつ注目対象である一時データ配列［２］［２］は除外されていない。また、比較対象の一時データ配列［２］［１］も除外されていない。したがって、この場合、注目対象である一時データ配列［２］［２］の配列番号で示される実データ「２６」と、比較対象である一時データ配列［２］［１］の配列番号で示される実データ「４１」とが比較される。そして、大きい方の実データ「４１」（実際には配列番号「２」）が一時データ配列［３］［１］に格納される。
【００６３】
次に、一時データ配列［３］［１］が注目対象となる。この場合、該一時データ配列［３］［１］には、比較対象として一時データ配列［３］［２］が存在し、かつ注目対象である一時データ配列［３］［１］は除外されていない。また、比較対象の一時データ配列［３］［２］も除外されていない。したがって、この場合、注目対象である一時データ配列［３］［１］の配列番号で示される実データ「４１」と、比較対象である一時データ配列［３］［２］の配列番号で示される実データ「５３」とが比較される。そして、大きい方の実データ「５３」（実際には配列番号「５」）が一時データ配列［４］［１］に格納される。
【００６４】
最後の１つに絞り込まれると、出力制御部１２により、最終的に絞り込んだ配列番号の実データを入力データ配列部１から取得し、出力データ配列部１３における、出力カウンタ１０からの配列番号に格納する（ステップＳ７２）。
【００６５】
したがって、図８に示す例では、実データ「５３」が、実データの中で２番目に大きな値として最終的に一時データ配列［４］［１］に残り、出力データ配列［２］に格納される。
【００６６】
つまり、２回目のソート処理では、例えば、一時データ配列［１］［１］の配列番号で示される実データ「３１」と一時データ配列［１］［２］の配列番号で示される実データ「４１」とは、前述した１回目の処理で既に比較されているので、実データ「３１」と実データ「４１」との比較は行なわれない。
【００６７】
次に、要求データ数１１に達したか否かを判断し（ステップＳ７４）、要求データ数に達していなければ、ソートが終了したか否かを判断する（ステップＳ７６）。そして、ソートが終了していなければ、最終的に絞り込んだ配列番号を一時データ配列から除外する（ステップＳ７８）。次に、図４に示すステップＳ５２へ戻り、前述した処理を繰り返す。
【００６８】
図９に示す例では、前述したように、一時データ配列［１］［５］に一時データ配列に格納することのできる配列番号としてはありえないマイナスの値が格納され、除外される。そして、この一時データ配列［１］［５］が注目対象となる。しかし、一時データ配列［１］［５］は、比較対象がないため、一時データ配列［２］［３］に一時データ配列［１］［５］の内容が格納され、除外される。同様に、一時データ配列［３］［２］に一時データ配列［２］［３］の内容が格納され、除外される。
【００６９】
続いて、一時データ配列［３］［２］が注目対象となる。この場合、該一時データ配列［３］［２］には、比較対象として一時データ配列［３］［１］が存在するが、注目対象である一時データ配列［３］［２］は除外されている。したがって、この場合、比較対象である一時データ配列［３］［１］の実データ「４１」が一時データ配列［４］［１］に格納される。そして、最後の１つに絞り込まれたので、実データ「４１」が、出力データ配列［３］に格納される。その後、図１０に示すように、一時データ配列［１］［２］を除外する（配列番号としてはありえないマイナスの値を格納する）。
【００７０】
続いて、図１０に示す例では、一時データ配列［１］［２］が注目対象となる。この場合、該一時データ配列［１］［２］には、比較対象として一時データ配列［１］［１］が存在し、かつ、一時データ配列［１］［２］が除外されているので、比較対象である一時データ配列［１］［１］で示される実データ「３１」の配列番号が一段上の一時データ配列［２］［１］に格納されることになる。
【００７１】
次に、一時データ配列［２］［１］が注目対象となる。この場合、該一時データ配列［２］［１］には、比較対象として一時データ配列［２］［２］が存在し、かつ注目対象である一時データ配列［２］［１］は除外されていない。また、比較対象の一時データ配列［２］［２］も除外されていない。したがって、この場合、注目対象である一時データ配列［２］［１］の配列番号で示される実データ「３１」と、比較対象である一時データ配列［２］［２］の配列番号で示される実データ「２６」とが比較される。そして、大きい方の実データ「３１」（実際には配列番号「１」）が一時データ配列［３］［１］に格納される。
【００７２】
次に、一時データ配列［３］［１］が注目対象となる。この場合、注目対象である一時データ配列［３］［１］は除外されていないが、比較対象の一時データ配列［３］［２］は除外されている。したがって、この場合、注目対象である一時データ配列［３］［１］の配列番号で示される実データ「３１」（実際には配列番号「１」）が一時データ配列［４］［１］に格納される。そして、最後の１つに絞り込まれると、一時データ配列［４］［１］の実データ「３１」（実際には配列番号「１」）が、出力データ配列［４］に格納される。その後、図１１に示すように、一時データ配列［１］［１］が除外され（配列番号としてはありえないマイナスの値を格納する）、注目の対象となる。
【００７３】
続いて、上述した処理を行なうと、図１１に示す例では、一時データ配列［１］［１］が注目対象となる。この場合、該一時データ配列［１］［１］には、比較対象として一時データ配列［１］［２］が存在し、かつ、両者とも除外されているため、一段上の一時データ配列［２］［１］も除外される。そして、次に、一時データ配列［２］［１］が注目対象となる。この場合、該一時データ配列［２］［１］は除外されている。したがって、この場合、比較対象である一時データ配列［２］［２］の実データ「２６」が一時データ配列［３］［１］に格納される。
【００７４】
次に、一時データ配列［３］［１］が注目対象となる。この場合、注目対象である一時データ配列［３］［１］は除外されていないが、比較対象の一時データ配列［３］［２］は除外されている。したがって、この場合、注目対象である一時データ配列［３］［１］の配列番号で示される実データ「２６」が一時データ配列［４］［１］に格納される。そして、最後の１つに絞り込まれると、一時データ配列［４］［１］の実データ「２６」が、出力データ配列［５］に格納される。
【００７５】
このように、本実施形態では、一度、行なった大小比較は行なわれなかったことに注目したい。すなわち、「比較結果を保存し再利用している」ことに特徴がある。本実施形態においては、降順に並べ替える場合には、大きなデータが１つ１つ判明していき、昇順に並べ替える場合には、小さなデータが１つ１つ、ソート処理を行なっている過程で判明していく。これがクイックソートやマージソートの場合には、処理の終盤になるまで最も大きな（小さな）データがどれであるかが、分からないのである。つまり、本実施形態では、与えられたデータの中から上位の値をいくつか算出するような場合には（１００件のデータの中から上位１０個を求めればよいような場合には）、要求データ数１１を設定することで、全てを並び替える前に処理を終了してしまうことも可能なのである。
【００７６】
なお、前述した実施形態では、説明を簡易にするために５つの数値で行ったが、さらに多くのデータで行なうことももちろん可能である。
【００７７】
Ｂ．変形例
次に、上述した実施形態の変形例として、トーナメントを同時に２つ行なう例について説明する。一方では、降順にデータを並べるためのソートを行ない、他方では、昇順にデータを並べるためのソートを行なう。つまり、ソート対象データの中で、最も大きなデータと最も小さなデータとを選出することを同時に行なう。なお、以下の説明では、一時データ配列に実データを記しているが、実際には、上述した実施形態と同様に、対応する実データの配列番号が格納されるようになっている。
【００７８】
ここで、図１２ないし図１４は、本変形例の一動作例を説明するための概念図である。本変形例では、前述した実施形態と同じ入力データ「３１」、「４１」、「５９」、「２６」、「５３」を例にとって、このデータを降順にソートする場合を図示すると、一番大きなデータである「５９」と一番小さなデータである「２６」を選出する過程は、以下のようになる。
【００７９】
まず、図１２に示すように、一時データ配列Ａ［１］［１］の配列番号で示される実データ「３１」と一時データ配列Ａ［１］［２］の配列番号で示される実データ「４１」を比較し、大きい方の実データ「４１」を、降順データを選出するための一時データ配列Ａ［２］［１］に格納する。また、上記選出と並行して、小さい方の実データ「３１」を、昇順データを選出するための一時データ配列Ｂ［２］［１］に格納する。
【００８０】
次に、図１２に示すように、一時データ配列Ａ［１］［３］の配列番号で示される実データ「５９」と一時データ配列Ａ［１］［４］の配列番号で示される実データ「２６」とについても同様の比較を行ない、大きい方の実データ「５９」を、降順データを選出するための一時データ配列Ａ［２］［２］に格納する。また、上記選出と並行して、小さい方の実データ「２６」を、昇順データを選出するための一時データ配列Ｂ［２］［２］に格納する。
【００８１】
そして、１つだけ残った実データ「５３」は、一時データ配列Ａ［２］［３］と一時データ配列Ｂ［２］［３］の両方に格納する。
【００８２】
次に、図１２に示すように、一時データ配列Ａ［２］［１］に格納された実データ「４１」と一時データ配列Ａ［２］［２］に格納された実データ「５９」とを比較し、大きい方の実データ「５９」を、降順データを選出するための一時データ配列Ａ［３］［１］に格納する。また、上記選出と並行して、一時データ配列Ｂ［２］［１］に格納された実データ「３１」と一時データ配列Ｂ［２］［２］に格納された実データ「２６」とを比較し、小さい方の実データ「２６」を、昇順データを選出するための一時データ配列Ｂ［３］［１］に格納する。
【００８３】
さらに、一時データ配列Ａ［２］［３］に残っている実データ「５３」を、一時データ配列Ａ［３］［２］に格納し、一時データ配列Ｂ［２］［３］に残っている実データ「５３」を、一時データ配列Ｂ［３］［２］に格納する。
【００８４】
次に、一時データ配列Ａ［３］［１］の実データ「５９」と一時データ配列Ａ［３］［２］の実データ「５３」とを比較し、大きい方の実データ「５９」を、一時データ配列Ａ［４］［１］に格納する。また、上記選出と並行して、一時データ配列Ｂ［３］［１］の実データ「２６」と一時データ配列Ｂ［３］［２］の実データ「５３」とを比較し、小さい方の実データ「２６」を、一時データ配列Ｂ［４］［１］に格納する。
【００８５】
このようにして、降順データ配列である一時データ配列Ａにおいて選出された実データ「５９」が最も大きな値であり、昇順データ配列である一時データ配列Ｂにおいて選出された実データ「２６」が最も小さな値である。そこで、最も大きな実データ「５９」を、出力データ配列［１］に格納し、最も小さな実データ「２６」を、出力データ配列［５］に格納する。このようにして、一度の２つのデータを選出する。
【００８６】
次に、図１３に示すように、選出し終えた実データ「５９」と実データ「２６」とを一時データ配列Ａ［１］［３］、［１］［４］から除外して（配列番号としてはありえないマイナスの値を格納する）、再度、同じ処理を行なう。但し、次に大きな値を選出するためには、実データ「５９」を選出するために行った比較だけを行なえばよい。同様に、次に小さな値を選出するためには、実データ「２６」を選出するために行なった比較だけを行なえばよい。
【００８７】
降順データ選出では、一時データ配列Ａ［１］［３］が注目対象となる。この場合、該一時データ配列Ａ［１］［３］には、比較対象として一時データ配列Ａ［１］［４］が存在し、かつ、両者とも除外されているため、一段上の一時データ配列Ａ［２］［２］も除外される。次に、一時データ配列Ａ［２］［２］を注目対象とすると、これは除外されているので、比較対象の一時データ配列Ａ［２］［１］の実データ「４１」が一段上の一時データ配列Ａ［３］［１］に格納される。この結果、次に、実データ「４１」と「５３」とが比較され、大きい方の実データ「５３」が最も大きな値として選出され、出力データ配列［２］に格納される。
これと並行して、昇順データ選出では、一時データ配列Ｂ［１］［４］が注目対象となる。この場合、該一時データ配列Ｂ［１］［４］には、比較対象として一時データ配列Ｂ［１］［３］が存在し、かつ、両者とも除外されているため、一段上の一時データ配列Ｂ［２］［２］も除外される。一時データ配列Ｂ［２］［２］を注目対象とすると、これは除外されているので、比較対象の一時データ配列Ｂ［２］［１］の実データ「３１」が一段上の一時データ配列Ｂ［３］［１］に格納される。この結果、次に、実データ「３１」と「５３」とが比較されて、小さい方の実データ「３１」が選出され、出力データ配列［４］に格納される。
【００８８】
次に、図１４に示すように、選出された実データ「３１」と「５３」を一時データ配列Ａから除外することで、降順データ選出では、一時データ配列［２］［１］及び一時データ配列［３］［１］の実データ「４１」が一段上の一時データ配列Ｂ［４］［１］に格納される。この結果、次に、実データ「４１」が出力データ配列［３］に格納される。
【００８９】
上述した変形例では、降順データの選出と昇順データの選出とを同時に行なう必要がある。同時に行なうことで、データをソートするために必要な時間を短縮することができる。しかし、「降順データを選出してから昇順データを選出する」またはその逆である「昇順データを選出してから降順データを選出する」ように、別々に処理を行なうと、処理の完了に要する時間は、降順データ選出配列のみによって（つまり実施形態で示した方法によって）データを選出する場合と、それほど変わらなくなってしまう。ただし、従来技術の特許文献１にあるような特殊なハードウェアを用意する必要はなく、単にＣＰＵが複数あればよいだけである。
【００９０】
なお、このようなソートを行なう場合、「あるデータの中から、昇順（または降順）のデータの先頭から途中までを少ない処理量で得ることができる」に影響を及ぼす。求めたいデータが、全データ数の中の半分以下のデータであれば（例えば、６０万件のデータの中から上位３０万位以下を求めたいような場合であれば）、このような発展形態を使う必要は必ずしもない。しかし、全データ数の中の半分以上のデータを求めたい場合には（例えば、６０万件のデータの中から上位３０万位以上のデータを求めたいような場合であれば）、このような発展形態を利用した方が、処理時間を短縮することができる。
【００９１】
Ｄ．結論
上述した本発明の実施形態および変形例によれば、
１）  比較回数が、従来のソートアルゴリズムに比べると少ない。
２）  比較回数が、要素の並び順によって変化しない。
という効果が得られる。
【００９２】
本実施形態では、比較回数を削減しているが、それをもっとも計算量の多い基本交換法の比較回数と比較したグラフを図１５に示す。図１５に示すグラフでは、縦軸に比較回数、横軸にデータの数をとり、データ数の増加によって比較回数がどのように変化するかを、データ数「１」から「３００」までについて示している。
【００９３】
なお、従来技術で述べた基本交換法の場合、比較回数は以下の計算式によって、求められる。
基本交換法の比較回数＝（データの数＊（データの数−１））／２
【００９４】
また、本実施形態によるソート方法では、以下の計算式によって比較回数が求められる。
本実施形態の比較回数＝
（データの数−１）＋（Ｌｏｇ２データの数＊（データの数−１））
注：但し、「Ｌｏｇ２データの数」は、小数点切り上げで計算する。
【００９５】
また、上述した本発明の実施形態および変形例によれば、
３）  交換回数は、データの数とイコールである（最小交換回数＝データの数＝最大交換回数）。
４）  交換回数が、要素の並び順によって変化しない。
という効果が得られる。
【００９６】
従来技術で述べた基本交換法における最大交換回数は、比較回数と同じになる。これはつまり、比較のたびに交換が起こるということである。例えば、あるデータを昇順（小さい順）に並べ替えようとしたときに、並べ替える前のデータが完全に降順（大きい順）に並んでいる場合には、比較のたびに交換する必要がある。
【００９７】
また、基本交換法における最小交換回数は、０回である。これはつまり、交換する必要がまったくないということである。例えば、あるデータを昇順に並べ替えようとしたときに、並べ替える前のデータが既に完全に昇順に並んでいる場合には、交換が１度も行われない。
【００９８】
このように、基本交換法の最大交換回数は比較回数と同じになり、最小交換回数は０回になることを踏まえると、基本交換法の平均交換回数は、比較数（＝最大交換回数）の半分（２分の１）になる。
【００９９】
本発明の実施形態では、最大交換回数および最小交換回数、さらには平均交換回数もデータ数と同じになる。最も大きなデータ（または最も小さなデータ）が、配列のどの位置にあっても、必ず交換が発生するためである。これは裏返すと、それ以上の交換が発生しないことをも意味する。これをグラフ化したものを図１６に示す。
【０１００】
本実施形態では、あるデータの中から、昇順（または降順）のデータの先頭から途中までを少ない処理量で得ることができる。一例を挙げると、２０００件あるデータの中からもっとも大きな１０個の数を選出するまでにかかる比較回数は、従来技術による基本交換法では、１９９４５回である（１９９９＋１９９８＋１９９７＋１９９６＋１９９５＋１９９４＋１９９３＋１９９２＋１９９１＋１９９０）。交換回数は、９７２回ほどである。
【０１０１】
これに対して、本実施形態では、比較回数はおよそ２１００回であり（２０００＋（１１＊９））、交換回数は１０回である（選出するデータ数と同じ回数）。
【０１０２】
Ｅ．利用シーン
次に、本発明の実施形態の利用シーンについて説明する。
【０１０３】
Ｅ−１．要素の並び順に依存せず、どんな並び順でも一定の時間内にソートが完了することが求められる場合
一般的に、ソートアルゴリズムは、要素の並び順で計算量が異なってくる。例えば、ある数列を小さい順に並び替える場合を考えてみる。並び替える前の数列が、仮に大きい順に並んでいると、小さい順に並べ替えるために必要な処理は、多くなる。しかし、並べ替える前に既に小さい順に並んでいれば、ほとんど処理を行なうことなく、ソートは終了する。
【０１０４】
本実施形態によるソート方法では、処理量が、このように要素の並び順による影響を受けないので、ソートの処理を行なう前に、予めデータ数から計算時間を予測することが可能である。
【０１０５】
Ｅ−２．個々の要素が、大容量であるため、交換をなるべく行ないたくないような場合
並べ替えを行なう要素が、音声データや画像データなどの場合、単に数値や文字を並べ替えるのとは違い、交換に膨大な時間を要するため、できるだけ無駄な交換をしない方が、並べ替えを早く終了することができる。本実施形態では、要素がどのような順で並んでいても、交換回数は一定である。
【０１０６】
Ｅ−３．個々の比較に、時間がかかる場合
数値を大きな順（降順）や小さな順（昇順）に並べ替えるような場合、単にどちらの数値が大きいか、小さいかを比較すればよいだけであり、このような比較の結果はすぐに求めることができる。Ｃ言語やＪａｖａ（登録商標）で行なう場合であれば、２つの数値が格納された変数や配列であるＡとＢを、ｉｆ文などを使ってただ単に比較すればよいのである。
【０１０７】
しかし、例えば、画像として、□、△、☆の３つがあり、どれが一番「○」の画像に近いかを比較する場合、すなわち「○」に近い形状順に並び替える場合、様々な基準によって比較を行なわなければならない。この場合であれば、「１つの線の端と、もう一方の端が繋がっていて（輪になっていて）」、「それぞれの角が１８０度未満０度以上の範囲でなるべく大きく」、「角の数が多い」ほど、○に近いということになる。つまり、□の画像と△の画像を比較するにあたって、この３つの基準にそって比較をしなければならないということである。「□と☆」および「△と☆」を比較する場合も同様に、先ほどの３つの基準で比較しなければならないということである。この３つの組み合わせ（「□と△」、「□と☆」、「△と☆」）のそれぞれで、先ほどの３つの条件について比較を行なわなければならないため、この場合は９回の比較を行なわなければならない。
【０１０８】
１つの組み合わせで、複数の比較を行なわなければならないことは、比較時間の増大を意味する。このようなソートの場合に、従来技術で述べた基本交換法（バブルソート）やクイックソートを利用すると、同じ比較が何度も行われることがあり、無駄な処理が発生してしまう。本実施形態によれば、無駄な比較を行なわないことで、処理時間を大幅に削減できる。
【０１０９】
Ｅ−４．大量のデータすべてをソートする必要がない場合
近年のインターネットの普及により、ユーザがＷｅｂサイトを訪れて本を購入したり、動画を閲覧したりする機会は多い。一例を挙げると、様々な映画や情報番組の動画を配信するＷｅｂサイトや、和書、洋書、ＣＤ、ＤＶＤ、ビデオなどを販売するＷｅｂサイトなどがある。このようなサイトを訪れたときに、利用者が参考にするのが人気ランキングである。どのようなものが売れているのかを一目瞭然で把握することができるこの人気ランキングは、どんなに短くても１時間ごとに更新されているという現状がある。
【０１１０】
しかし、このようなサイトに限らず、不特定多数のネットの利用者が一時的にネット上で購入をすることで、一瞬にしてランキングが大きく変わってしまうこともある。ネットの世界では、１時間と言わず、リアルタイムで、つまりユーザがランキングを見たいと思ったその時点でのランキング結果が閲覧できることが望ましい。
【０１１１】
ランキングの表示がこのようにある程度の間隔を要しているのは、過去の取引記録をもとに、バッチ処理でランキングを集計しているからである。例えば、およそ６０万の商品やコンテンツがあり、その中からもっとも購入数の多い１００位のランキングを、１時間ごとに更新してサイトに表示するような場合を想定してみる。過去の取引記録をもとに、商品マスタファイルに、売上数を加えて累計の売上数を出す。その後、売上数をもとにソート処理を行って、上位１００個をサイトに表示することになる（但し、上位１００個を決めるための売上数の考え方はここでは詳細には記述しない。実際には、過去１週間の売上数などでランキングを決めていると考えられる）。
【０１１２】
現在、一般的に知られているソートアルゴリズムを考えると、１時間という間隔を要することは、仕方のないことである。例えば、基本交換法でソートを行った場合、処理に膨大な時間を要するであろう。おそらく１，７８０億回［（６００，０００＊５９９，９９９回）／２］の比較と、平均で９００億回［比較回数／２］の交換処理が必要になる。仮に、上位１００位までを選出したところでソート処理を終了するとしても、およそ６，０００万回の比較と３０００万回の交換が必要になる。
【０１１３】
ここで、クイックソートを利用しても、最悪の場合には、基本交換法と同じ処理量になるばかりではない。処理量を軽減するために上位１００位までを選出した時点で処理を終了させることは、クイックソートのアルゴリズムの観点からは難しい。
【０１１４】
これに対して、本実施形態のソート方法を利用して上位１００位を選出する場合には、およそ６０万２０００回の比較と、１００回の交換で処理が終了できる。仮に、６０万位までのデータをソートする場合でも、およそ１，２６０万回の比較と６０万回の交換で処理を終了させることができる。
【０１１５】
また、上位１００位だけを選出するのであれば、ユーザが望んだときに（サイト上にある「ランキング」などのリンクをクリックしたときに）、即座に計算を行なってまさにリアルタイムにランキングを表示することも可能になる。
これにより、ユーザは、どのコンテンツや商品に人気が集まっているのかをどんなときでもリアルタイムに把握することが可能になるのである。
【０１１６】
なお、上述した実施形態において、ソート装置の機能は、図示しない記憶部に記憶されたプログラムを実行することで実現するようになっている。記憶部は、ハードディスク装置や光磁気ディスク装置、フラッシュメモリ等の不揮発性メモリやＲＡＭ（Random Access Memory）のような揮発性のメモリ、あるいはこれらの組み合わせにより構成されるものとする。また、上記記憶部とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含む。
【０１１７】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワークや電話回線等の通信回線のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、上述した処理の一部を実現するためのものであってもよい。さらに、上述した処理をソート装置に既に記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【０１１８】
以上、この発明の実施形態を、図面を参照して詳述してきたが、具体的な構成は、上記実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【０１１９】
【図１】本発明の実施形態によるソート装置の構成を示すブロック図である。
【図２】本実施形態によるソート方法の動作を説明するためのフローチャートである。
【図３】本実施形態によるソート方法の動作を説明するためのフローチャートである。
【図４】本実施形態によるソート方法の動作を説明するためのフローチャートである。
【図５】本実施形態によるソート方法の動作を説明するためのフローチャートである。
【図６】実データとして、「３１」、「４１」、「５９」、「２６」、「５３」をソートする場合の入力データ配列、一時データ配列および出力データ配列の構成を示す概念図である。
【図７】本実施形態によるソート方法の一動作例を説明するための概念図である。
【図８】本実施形態によるソート方法の一動作例を説明するための概念図である。
【図９】本実施形態によるソート方法の一動作例を説明するための概念図である。
【図１０】本実施形態によるソート方法の一動作例を説明するための概念図である。
【図１１】本実施形態によるソート方法の一動作例を説明するための概念図である。
【図１２】本変形例の一動作例を説明するための概念図である。
【図１３】本変形例の一動作例を説明するための概念図である。
【図１４】本変形例の一動作例を説明するための概念図である。
【図１５】本実施形態による比較回数と基本交換法の比較回数と比較した概念図である。
【図１６】本実施形態による平均交換回数と基本交換法の比較回数と比較した概念図である。
【符号の説明】
【０１２０】
１  入力データ配列部（データ記憶手段）
２  配列番号取得部（格納位置取得手段）
３  一時データ配列部（一時データ記憶手段）
４  参照カウンタ
５  実データ参照部
６  比較制御部（比較手段、比較対象除外手段、制御手段）
７  トーナメントの深さ数
８  一時データ数
９  転送部
１０  出力カウンタ
１１  要求データ数
１２  出力制御部（要求データ数設定手段）
１３  出力データ配列部（出力データ記憶手段）
【図１】
2005038338.tif 000003
【図２】
2005038338.tif 000004
【図３】
2005038338.tif 000005
【図４】
2005038338.tif 000006
【図５】
2005038338.tif 000007
【図６】
2005038338.tif 000008
【図７】
2005038338.tif 000009
【図８】
2005038338.tif 000010
【図９】
2005038338.tif 000011
【図１０】
2005038338.tif 000012
【図１１】
2005038338.tif 000013
【図１２】
2005038338.tif 000014
【図１３】
2005038338.tif 000015
【図１４】
2005038338.tif 000016
【図１５】
2005038338.tif 000017
【図１６】
2005038338.tif 000018