JPH03154920A - 高速ソート処理方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、文字列や数値データを対象としたソート処理
方式に関し、特にソート対象データの大小比較処理を必
要としない高速ソート処理方式に関する。

ｆ従来の技術〕 従来、与えられたデータの集まりを昇順あるいは降順に
並び替えるソート処理については、高速化のための方法
が種々提案されている。

例えば、特開昭６　：３＝、２２９５２２号公報に記載
されている方法では、ｍ個の処理装置に対して、データ
の値の範囲をｍ個に分割し、各々に分担範囲を割り当て
、各処理装置が手持ちのソートするデータの要素を分担
範囲に従って相互に分配し、分配後のデータについて各
個別にソートを実行することにより、全データのソート
を完了させている。

また、特開昭６３−２７６６２９号公報に記載されてい
る方法では、ソート入力ファイルに入力データを随時追
加しながら、所定の契機で同一のソートパラメータによ
り繰返し実行されるソート処理において、２回目以降の
ソート処理では、ソート入力ファイルに新たに追加され
たデータのみを読み込んでソート処理を行い、ソート初
期処理を不要としている。

また、特開昭６３−２３１５２６号公報に記載されてい
る装置では、比較転送ユニットの１次元アレイ構造から
なるソート処理装置において、ソート対象とするデータ
を複数の比較転送ユニットに分解して格納し、そのデー
タを分割して格納した各比較転送ユニットの比較・転送
処理を連動させてソートを行っている。

なお、これらの方法や装置では、ソート処理の際、デー
タの大小比較処理が必ず行われ、そのためのハードウェ
アが必要である。

〔発明が解決しようとする課題〕

上記従来技術のうち、特開昭６３−２２９５２２号公報
に記載された方法では、処理装置を複数台持つ必要があ
り、また、特開昭６３−２３１５２６号公報に記載され
た方法では、比較転送ユニットを複数台持つ必要がある
ため、ハードウェア量が増大するという問題があった。

さらに、特開昭６３−２７６６２９号公報に記載されて
いる方法では、１回目のソート処理あるいは異なるソー
トパラメータでは効果がないという問題点があった。

本発明の目的は、このような問題点を改善し、ソート対
象データの大小比較処理を行う特別なハードウェアを設
けることなく、１台の処理装置で高速にソート処理を行
うことが可能な高速ソート処理方式を提供することにあ
る。

〔課題を解決するための手段〕

上記目的を達成するため、本発明の高速ソート処理方式
は、ソート対象データ群をデータ値の大小関係に基づい
て並び換える機能を持つソート処理装置において、その
データ群の最小値および最大値で示される範囲で、デー
タ値が出現する回数を計数し、データ値と対応づけて記
憶する手段（アドレスレジスタ、カウンタ群）を備え、
その範囲の全ての値についてその記憶手段を設定し、昇
順か降順の何れか一方の順で、ソート対象データ値が示
す記憶手段を順次更新して出現回数を計数／記憶し、記
憶した値分、そのデータ値を並べる　− ことに特徴がある。

〔作用〕

本発明においては、ソート対象データ群の範囲に含まれ
る全要素について、その出現回数をカウントし、その値
分、当該要素を昇順あるいは降順に並べることにより、
ソート処理を行う。

これにより、ソート処理では、ソート対象データの大小
比較処理を行うことなく、ソート処理を行うことができ
るため、大小比較処理のためのハードウェアは不要であ
り、また、処理速度を向上させることができる。

〔実施例〕

以下、本発明の一実施例を図面により詳細に説明する。

第１図は、本発明の一実施例におけるソート処理装置の
構成図、第２図は本発明の一実施例におけるソート処理
装置のソート処理を示すフローチャート、第３図は本発
明の一実施例におけるソート処理の説明図である。

なお、第１図および第２図におけるに、ｍ、ｎ。

＋＋Ｊを予め次のように定義する。すなわち、ｋはソー
ト対象データ数、ｍはソート対象データの最小値、ｎは
ソート対象データの最大値、ｉは変数（変域：　１−ｋ
）、Ｊは変数（変域：ｍｘｎ）である。

第１図において、ｌはソート対象データ群（ａ〜ａｌ）
を格納する入力バッファ（ＩＮＢＵＦ）、２ｍ〜２ｎは
ソート対象データのとり得る範囲（ｍ−ｎ）分、ソート
対象データ値から昇順に選択可能なカウンタ（ＣＮ　Ｔ
ｌ１ｌ−ＣＮ　Ｔｎ）、３は各カウンタ（ＣＮＴ、〜Ｃ
ＮＴｎ）を選択する条件値（ソート対象データ値）を格
納するアドレスレジスタ、４はＣＮＴｍから順に各カウ
ンタ（ＣＮ下１〜ＣＮＴ、）の選択条件値（ｍ−ｎ）を
当該カウンタの値分並べる機能を有するデータ制御部（
ＤＡＴＡＣＴＬ）、５はソート処理結果を格納する出力
バッファ（ＯＵＴＢ［ＪＦ）である。

次に、本実施例のソート処理の手順について述べる。

本実施例では、第２図のように、まず、ソート処理の前
処理として、予めソート対象データ値から選択可能なカ
ウンタ群（ＣＮ　Ｔ、〜ＣＮ　Ｔ、）をリセットし、初
期値を設定する（２０１，２０２）。

次に、ソート対象データ群の先頭から最終データまで順
に、アドレスレジスタを介してソート対象データ値（ａ
ｌ、ｉ＝ｌ−ｗｋ）から選択されるカウンタ（ＣＮＴ、
）を更新（＋１）する（２０３〜２０６）。

これらの動作により、ソート対象データ全体の各要素の
数が各カウンタ（ＣＮＴＩｌｌ〜ＣＮＴｎ）に格納され
る。

その後、ステップ２０３〜２０６の動作によって得られ
た各カウンタ（ＣＮＴ、〜ＣＮＴｎ）の値を用い、ソー
ト対象データ値ｉから選択されるカウンタ（ＣＮＴ、）
の値分、データｉを繰返し、出力バッファ（ＯＵＴＢＵ
Ｆ）に格納する。

すなわち、昇順ソートの場合（２０７）、この格納動作
をｉ＝ｍから初めてｎまで行い（２０８〜２１１）、降
順ソートの場合には（２０？）、ｉ＝ｎから初めてｍま
で行う（２１２〜２１５）。

以」二の処理により、大小比較処理を行うことなく、入
力バッファ（ＩＮＢＵＦ）１内のデータをソートして、
出力バッファ（ＯＵＴＢＵＦ）５に格納することができ
る。

次に、昇順ソートの具体例について述べる。

例えば、ソート対象データ群（８，３，５，２゜９．１
．２）を昇順にソートする場合、第１図に示した入力バ
ッファｌには、第３図（ａ）のようなデータが格納され
ている。

これらのデータの範囲は最小値ＩＩ　１　！１〜最大値
１１９　Ｉ＋であるため、アドレスレジスタ３の選択に
従って更新処理を行った後のカウンタ群２ｍ〜２ｎでは
、（ｂ）のように、ＣＮＴ、がデータ値“１″の出現回
数を示し、ＣＮＴヨ〜ＣＮ’ｒ、はデータ値パ２〜９”
の出現回数を順次示す。

さらに、（ｃ）のように、このカウンタ群が示す値分、
各データを昇順に出力バッファ５へ格納することにより
、ソート処理を完了する。

〔発明の効果〕

本発明によれば、ソート対象データ群に含まれる各要素
の数をカウントし、その値分、当該要素を並べることに
よりソート処理を行うので、ソート対象データの大小比
較処理が不要となる。また、各カウンタの更新処理もソ
ート対象データ数分だけ行えばよいので、ソート対象デ
ータ数が増しても、ソート処理性能が指数的に劣化する
ことはない。

なお、従来はソート対象データ値の大小比較処理が必要
であり、ソート対象データ数が増すと、ソート対象デー
タ値の大小比較処理回数が指数的に増加するので、ソー
ト処理性能も指数的に劣化していた。例えば、クイック
ソートでは、ｎ個のソート対象データ値の大小比較処理
回数は平均してｎｌｏｇｎ回必要であった。

また、ハードウェア量についても、ソート対象データ値
の大小比較処理は不要であるため、ソート対象データ値
の大小比較を行う特別なハードウェアを設ける必要はな
く、また、複数台の処理装置を設ける必要もない。従っ
て、少いハードウェア量でソート処理を実現することか
り能である。

【図面の簡単な説明】

第１図は本発明の一実施例におけるソート処理装置の構
成図、第２図は本発明の一実施例におけるソート処理装
置のソート処理を示すフローチャート、第３図は本発明
の一実施例におけるソート処理の説明図である。 ｌ：人力バッフｙ（ｌＮＩ３ＬＪｌ’）、２ｍ　〜２ｎ
　：カウンタ（ＣＮＴ、〜ＣＮＴ、）、３　ニアドレス
レジスタ、４：データ制御部（ＤＡＴＡＣＴＬ）、５　
：出力バッファ（ＯＵＴＢＵＦ）。

Claims (1)

【特許請求の範囲】
1. １、ソート対象データ群をデータ値の大小関係に基づい
   て並び換える機能を持つソート処理装置において、該デ
   ータ群の最小値および最大値で示される範囲で、データ
   値が出現する回数を計数し、該データ値と対応づけて記
   憶する手段を備え、該範囲の全ての値について該記憶手
   段を設定し、昇順か降順の何れか一方の順で、ソート対
   象データ値が示す該記憶手段を順次更新して該出現回数
   を計数／記憶し、記憶した値分、該データ値を並べるこ
   とを特徴とする高速ソート処理方式。