JPH0266626A - ソート装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、順次入力される被ソートデータを値の大きい
順又は小さい順に並び替えるソート装置に関し、特にメ
モリ内のソートデータと新たに与えられた被ソートデー
タとを順次比較してソートを行なうソート装置に関する
。

［従来の技術］ 近年、各種データベース又は文字認識における認識候補
の決定等、様々な分野でソート装置が利用され、その高
速化が望まれている。この種のソート装置において、ソ
ートされたメモリ内のデータと新たに与えられた被ソー
トデータとを順次比較して、データを大きい順又は小さ
い順にメモリに格納する所謂バブルソート回路がある。

従来、この種のソート方法としては、次の２つの方法が
ある。

第１の方法は、先ず、ソートデータを格納するソートデ
ータメモリの全記憶領域に初期値を格納してからソート
処理を行う方法である。初期値としては、大きい順にソ
ートする場合には最小値、小さい順にソートする場合に
は最大値が選ばれる。

この方法では、被ソートデータが与えられる度に、被ソ
ートデータとソートデータメモリ全体との比較が行なわ
れる。

一方、第２の方法は、被ソートデータが与えられた場合
、ソートデータメモリ全体との比較は行なわず、ソート
済のデータとの間でのみソートを行なう方法である。こ
の手順を第２図に示す。即ち、この方法では、被ソート
データの入力された数をカウントする入力被ソートデー
タ数カウンタを備え、そのカウント値とメモリアドレス
とをソートの度に比較することにより、順次メモリ内の
データが有効かどうかを判定する。そして、データが有
効な場合のみソートが行われる。

［発明が解決しようとする課題］ しかしながら、上述した従来のソート回路のうち、第１
の方法では、ソートに先立ってメモリ全体を初期化する
必要があるため、初期化のためのオーバヘッドがかかっ
たり、初期化のために回路が複雑になるという欠点があ
る。

また、第２の方法では、被ソートデータの入力数によっ
て比較するメモリ量の制御が必要となるので制御が複雑
になる等、処理性能の低下及びハードウェア量の増大を
伴なうという欠点がある。

本発明はかかる問題点に鑑みてなされたものであって、
メモリの初期化を必要とせず、制御の簡単なソート装置
を提供することを目的とする。

［課題を解決するための手段］ 本発明に係るソート装置は、ソートデータを記憶するソ
ートデータメモリと、ソートデータの初期値として与え
るべきデータを記憶する初期値記憶手段と、被ソートデ
ータを入力し一時記憶する手段と、前記入力された被ソ
ートデータの数を計数する入力データ数カウンタと、被
ソートデータが入力される度に前記ソートデータメモリ
の先頭アドレスから順次メモリアドレスを生成するメモ
リアドレスカウンタと、このメモリアドレスカウンタの
カウント値が前記入力データ数カウンタのカウント値に
達したことを検出する手段と、この手段での検出前は前
記ソートデータメモリの前記メモリアドレスで指定され
るソートデータを選択し、検出後は前記初期値記憶手段
に記憶されたデータを選択する選択手段と、この選択手
段で選択されたデータと前記入力された被ソートデータ
との大小関係に基いて適宜データの交換と前記ソートデ
ータメモリへの格納とを行うソート手段とを具備してい
る。

［作用］ 被ソートデータが入力されると、入力データ数カウンタ
が１つカウントアツプし、メモリアドレスカウンタがソ
ートデータメモリのアドレスを順次生成する。選択手段
は、初めにソートデータメモリのデータを選択してソー
ト手段に供給する。

そして、メモリアドレスが入力データ数カウンタのカウ
ント値に達した場合に、泗択手段は、初期値記憶手段に
記憶された初期値を選択してソート手段に供給する。

従って、本発明によれば、ソートデータメモリ自体の初
期化が不要であり、そのためのオーバヘッド及び回路を
省略できる。また、ソートのためのデータの比較は、常
時メモリ全域にわたって行なえば良いので、制御も簡単
になる。

し実施例コ 次に、本発明の実施例に係るソート回路について添付の
図面を参照して説明する。

第１図はこのソート回路を示すブロック図である。被ソ
ートデータは、先ずソートデータバッファ１を介してソ
ート回路の内部に取込まれ、−旦ソートデータレジスタ
２に格納される。ソートデータレジスタ２の出力は、ソ
ートデータ比較器３及びデータスワツパ４の各一方の入
力に供給されている。一方、ソートデータメモリ５には
、現時点までのソート結果が格納されている。メモリア
ドレスによって指定されソートデータメモリ５から読出
されたソートデータは、ソートデータ選択回路７の一方
の入力に与えられている。同選択回路７の他方の入力に
は、初期値設定回路６に記憶された初期値が与えられて
いる。ソートデータ選択回路７は、後述する比較器９か
らの制御信号に基き、ソートデータと初期値とのいずれ
か一方を選択する。選択されたデータは、ソートデータ
比較器３及びデータスワツパ４の各他方の入力に与えら
れている。ソートデータ比較器３は、入力された２つの
データを比較する。データスワツパ４は、その比較結果
に基き適宜データを交換し、ソートデータレジスタ２及
びソートデータメモリ５に格納する。

入力データ数カウンタ８は、リセット信号１６によりリ
セットされ、データ書込み信号１７をカウントする。そ
のカウント値は比較器９の一方の入力に与えられている
。また、メモリアドレスカウンタ１０は、データ書込み
信号１７でリセットされ、カウントｕｐ信号１８をカウ
ントする。そのカウント値、即ちメモリアドレスは比較
器９の他方の入力に与えられている。比較器９は、両刃
ウンタ８，１０のカウント値を比較して両者が一致した
ら、前述したソートデータ選択回路７にソートデータメ
モリ５から初期値設定回路６への切替えのための制御信
号を出力する。

更に、このソート回路には、ソートデータに対応させて
その入力順番を記憶するための回路が付加されている。

即ち、入力データ数カウンタ８の出力は、入力順序バッ
ファ１１を介して入力順序レジスタ１２に一時格納され
る。入力順序レジスタ１２の出力は、データスワツパ１
３の一方の入力に与えられている。データスワツパ１３
の他方の入力には入力順序メモリ１４からのデータが供
給されている。そして、データスワツパ１３は、データ
スワツパ４と全く同様にソートデータ比較器３の出力に
基づいて適宜データを交換し、入力順序レジスタ１２と
入力順序メモリ１４にデータを格納する。

なお、制御部１５は、以上の各部の制御を司る。

以上の構成において、リセット信号１６がアクデイプに
なると、入力データ数カウンタ８がリセットされる。被
ソートデータが到来すると、データ書込み信号は入力デ
ータ数カウンタ８をインクリメントし、メモリアドレス
カウンタ１０をクリア（０とする）してソートが開始さ
れる９制御部１５は、ビジー信号１９をアクティブにす
る。

被ソートデータ２０はソートデータバッファ１を通じて
ソートデータレジスタ２に格納され、入力データ数カウ
ンタ８の出力は入力順序バッファ１１を通じて入力順序
レジスタ１２に格納される。

メモリアドレスカウンタ１０の出力は、比較器９におい
て、入力データ数カウンタ８の出力と比較されると同時
に、ソートデータメモリ５及び入力順序メモリ１４のア
ドレスとして供給される。

比較器９はリセット信号の入力直後では、メモリアドレ
スカウンタ１０の初期値と入力データ数カウンタ８の値
とが一致するので、直ちにその出力を１にするが、いく
つかの被ソートデータが到来している場合には、メモリ
アドレスカウンタ１０のカウント値が被ソートデータの
到来数に達するまでＯを出力し、これに達した時点で１
を出力する。比較器９の出力が０である場合には、ソー
トデータ選択回路７はソートデータメモリ５のデータを
選択し、１の場合には初期値設定回路６のデータを選択
する。ここで大きい順のソートを考えると、初期値設定
回路６には初期値として最小値（例えばＯ）が設定され
る。従って、リセット直後では、ソートデータ比較器３
への入力は、被ソートデータと初期値Ｏとになるため、
比較器３はデータスワツパ４，１３にデータの変換を指
示する。これにより、データスワツパ４は、ソートデー
タレジスタ２の内容をソートデータメモリ５の指定され
たアドレスに供給し、ソートデータ選択回路７の出力（
初期値）をソートデータレジスタ２に供給する。また、
データスワツパ１３は、入力順序レジスタ１２と入力順
序メモリ１４の内容を入れ替えて夫々に供給する。制御
部１５は、各メモリ５，１４と各レジスタ２，１２に夫
々のデータをストローブするように制御信号を出した後
、メモリアドレスカウンタ１０にカウントｕｐ信号１８
を出力してアドレスをインクリメントする。以後、同様
の動作がくり返されるが、メモリアドレスカウンタ〉入
力データ数カウンタであるので、初期値同士の比較とな
り、有意な比較は行なわれない。メモリアドレスが一巡
すると制御部１５はビジー信号１９をクリアして次の被
ソートデータの入力待ちとなる。

次の被ソートデータの入力では入力データ数カウンタ８
の値はメモリアドレスカウンタ１０のクリア値より１だ
け多いので、このときは比較器９の出力が０となり、ソ
ートデータ選択回路７はソートデータメモリ５の出力を
選択する。このため、メモリ５に格納されたソートデー
タと入力された被ソートデータとの比較が行なわれ、大
きい方のデータと入力順序とが各メモリ５，１４に入力
され、小さい方のデータと入力順序が各レジスタ２１２
に格納された後、メモリアドレカウンタ１０がカウント
アツプされる。

次の比較では、メモリアドレスカウンタ１０か＋１され
た結果、メモリアドレスカウンタ＝入力データ数カウン
タとなるので、前述した如くに前段でレジスタ２に格納
された小さい方のデータと初期値設定回路６の出力との
比較となり、以後は同様に動作を継続する。

このように、本回路によれば、ソートデータメモリ５の
初期化が不要で、しかもソートデータメモリ５に対して
は、ソートデータ量に拘らず常に全記憶領域について比
較を行なえば良いので、制御が容易である。

なお、以上の実施例では数の大きい順からのソートにつ
いて説明したが、初期値の設定とデータ比較器の判定方
法を変更すれば小さい順からのソートやソート方向の設
定も可能となること、またカウンタの動作がカウントｕ
ｐかｄ　ｏ　ｗ　ｎかは本発明にとってどちらを採用す
ることも可能なことは以上の説明から明らかである。

［発明の効果］ 以上説明したように本発明は、入力順序を示すカウント
値とメモリのアドレスを発生するカウント値とを比較し
てその結果によってメモリからの出力データを使用する
か、初期値設定回路で発生した初期値を使用するかを選
択することによって、メモリ自体の初期値設定を行なう
というオーバヘッドは不要となり、更に常時メモリ全域
にわたって比較を行なうことになるので制御自体も簡単
となる。

【図面の簡単な説明】

第１図は本発明の実施例に係るソート回路を示すブロッ
ク図、第２図は従来のソート方法の一例を示すフローチ
ャートである。 １；ソートデータバッファ、２；ソートデータレジスタ
、３；ソートデータ比較器、４．１３：データスワツパ
、５；ソートデータメモリ、６；初期値設定回路、７；
ソートデータ選択回路、８；入力データ数カウンタ、９
；比較器、１０；メモリアドレスカウンタ、１１；入力
順序バッファ、１２；入力順序レジスタ、１４；入力順
序メモリ、１５；制御部 ＋６＋’Ｉじ−、トう名号 １７；テーク書込み１占号

Claims (1)

【特許請求の範囲】
1. （１）ソートデータを記憶するソートデータメモリと、
   ソートデータの初期値として与えるべきデータを記憶す
   る初期値記憶手段と、被ソートデータを入力し一時記憶
   する手段と、前記入力された被ソートデータの数を計数
   する入力データ数カウンタと、被ソートデータが入力さ
   れる度に前記ソートデータメモリの先頭アドレスから順
   次メモリアドレスを生成するメモリアドレスカウンタと
   、このメモリアドレスカウンタのカウント値が前記入力
   データ数カウンタのカウント値に達したことを検出する
   手段と、この手段での検出前は前記ソートデータメモリ
   の前記メモリアドレスで指定されるソートデータを選択
   し、検出後は前記初期値記憶手段に記憶されたデータを
   選択する選択手段と、この選択手段で選択されたデータ
   と前記入力された被ソートデータとの大小関係に基いて
   適宜データの交換と前記ソートデータメモリへの格納と
   を行うソート手段とを具備したことを特徴とするソート
   装置。