JPS6237739A - ソ−ト処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （１）　　発明の属する技術分野 本発明は、文字列や数値データを対象としたソート処理
装置に関し、特にソート対象データ相互、データ内の複
数の領域に対して昇順あるいは降順にソートするソート
処理装置の構成に関する。

（２）従来の技術とその問題点 ソートとは、与えられたデータの集まりを所定の順序に
並び替える処理である。電子計算機におけるソート処理
とは、数値あるいは文字列として与えられたデータが、
計算機内部では“０”あるいは“１”の二値符号で表記
されている事から、二値符号の持つ数値的意味に基づい
て、与えられたデータを相互に比較し、それぞれのデー
タの大小関係によって、昇順（小さいものから大きいも
のへの順）あるいは降順（大きいものから小さいものへ
の順）にデータを並び変えることである。

一般に、ソート対象とするデータをレコー１：と称し、
レコードはデータ相互の比較を行って大小関係を判定す
るキ一部と比較を行わない部分とに分けることができる
。このレコードを、文字列や正整数（符号なし整数）に
限定した場合には、二進符号で表されたレコードのキ一
部を十位桁はど優位性を持たせて比較することによって
、ソート処理を行うレコード相互の大小関係を決定でき
る。

文字列や正整数以外の例えば実数等であっても適当な変
換処理によって、大小関係を損なわないように文字列あ
るいは正整数に変換することができる。

従来、このようなソート処理を、メモリ装置（メモリ）
と中央演算装置（ＣＰ　Ｕ）を中核として構成した汎用
の電子計算機で実行する場合には、メモリとＣＰＵ間の
データ転送やＣＰＵ内での比較が逐次処理である、一度
に２個のデータ間の比較しか出来ない等の理由により、
ソート処理で対象とするレコード数が大量の場合には、
処理に要する時間が極めて長くなるという問題があった
。

かかるソート処理時間に関する問題を解決する従来技術
として、専用のソート処理装置を用いて、データ相互の
比較による大小関係の判定と、データの転送を並列に行
って高速化を図る方法が、例えば、特願昭５８−１８８
３６８号や特１９ｎ昭５９−１６３５１９号に既知であ
る。

第１図は、従来技術の一例であるソート処理装置の構成
図である。本装置は、比較の対象となるデータを保持す
るための第１のメモリ１及び第２のメモリ２、比較器３
、この比Φ々器３によって得られた判定結果を保持する
ためのフラグレジスタ４および入出力回路５からなるユ
ニット６の？ｊｊ数個を一次元縦続接続した構成を有し
ている。本装置では、データ相互の比較と転送を複数の
ユニットで同時に実行できるため１、以下に説明する動
作原理に従って、レコード数に比例する時間でソート処
理を行うことができる。

第２図は、第１図のソート処理装置の動作原理図であり
、−例として、「０」から「９」までの−桁の数値デー
タのうち、ｒ３Ｊ　、ｒ６Ｊ　、ｒ５Ｊ　。

ｒ２ｊ、ｒ４Ｊ、ｒｌＪの、６個のレコードを降順にソ
ートする場合の動作を示している。第２図では、第１図
における第１のメモリ１および第２のメモリ２とフラグ
レジスタ４のみを簡略に示しており、他の回路は省略し
である。

ソート処理を行うに当って、始めに本装置では、全ての
ユニットの第１のメモリ１および第２のメモリ２の内容
を初期設定する。ここでは、降順にソートする場合の例
であり、この場合にはデータの最小値である「０」を設
定する。本装置では、順次レコードを入力する入力操作
と、順次レコードを出力する出力操作とでソート処理を
行う。−回の入力操作で各ユニットでは、データの右方
向への転送と２個のデータ間での比較とを行う。この場
合、転送されるデータは第１および第２のメモリに保持
された２個のデータのうち小さい方である。この時、デ
ータの転送と同期して１個のレコードをソート処理装置
に入力し、最左端のユニットの第１のメモリ１あるいは
第２のメモリ２のいずれかのうち転送によって空になっ
た方のメモリに保持する。（Ｔｌ〜Ｔ６） この人力操作を繰り返して６個のレコード全てを入力し
た段階で、今度は出力操作によって順次データを隣接す
る左側のユニットに転送する。この時、転送するデータ
はユニット内の２個のデータのうち大きい方であり、最
右端のユニットには「０」を入力する。（Ｔ７〜Ｔ１２
） 以上、入力操作の繰り返しによってデータが順次入力さ
れ、データの入力が完了した段階で出力操作を実行する
ことにより、最大値から順次ソート済みのレコードが降
順に取り出される。ここで説明したソート処理の例では
、レコード数に等しい入力操作回数と出力操作回数でソ
ート処理が行える。

この従来のソート処理装置を用いて昇順にソートする場
合には、初期設定として、全ユニットの第１のメモリ１
および第２のメモリ２に、データの最大値として「９」
を設定しておき、入力操作時には、各ユニットで比較し
た２個のデータのうち、大きい方を右方向に転送し、出
力操作時には、各ユニットで比較した２個のデータのう
ち、小さい方を左方向に転送する。従って、この従来の
ソート処理装置では、降順ソートの場合と昇順ソートの
場合とでは、各ユニットの初期設定する値を変更する問
題と、入力操作時および出力操作時の転送データの大小
を逆にしなければならない問題があった。このため、−
次元接続した比較転送ユニットの制御回路が複雑になり
、ソート処理装置の回路規模の増大や、装置全体の動作
速度が低下する問題があった。

（３）発明の目的 本発明の目的は、ソート処理装置において、降順あるい
は昇順のいずれであってもソートできる構成とするとと
もに、レコード内に複数のキ一部を設け、入力操作およ
び出力操作と同期してビット反転手段を制御することに
よって、複数のキーのそれぞれに対して昇順あるいは降
順にソートするマルチキーソートが可能なソート処理装
置を提供することにある。

（４）発明の構成 （４−１）発明の特徴と従来技術との差異本発明は、ソ
ート処理器のデータ入出力部に、入力あるいは出力する
データのビットを制御によって反転するビット反転手段
を具備したことを最も主要な特徴とする。従来のソート
処理装置で降順ソートと昇順ソートを行うためには、−
次元接続した複数個のユニットの各々で初期設定するす
る値を変更し、さらに、入力操作時および出力操作時に
転送するデータの大小を変更するため、−次元接続した
比較転送ユニットの制御回路が複雑になり、ソート処理
装置の回路規模の増大や、装置全体の動作速度を制限す
る要因となっていた。

本発明に基づくソート処理装置では、比較転送処理を行
うユニットを昇順ソートあるいは降順ソートのいずれか
一方に限定して実現することから、従来のソート処理装
置に比べて制御が闇路になり、この結果回路量の削減と
動作速度の向上が図れる。

さらに、従来のソート処理装置では、レコードを複数の
データに分割し、分割したデータに対する入力操作ある
いは出力操作の繰り返しによって、データ長が長いレコ
ードをソートするが、この入力操作および出力操作と同
期して該ビット反転手段を制御することによって、従来
のソート処理装置では実現することがほとんど不可能で
あった、レコード内に複数のキーを設定し、それぞれの
キーに対して降順あるいは昇順にソートするマルチキー
ソートを実現することが可能となった。

（４−２）実施例 以下、本発明を実施例を参照して詳細に説明する。第３
図は、本発明の詳細な説明するソート処理装置の全体構
成図である。本実施例では、レコード長の長いデータを
ソートするために、レコードを複数のデータに分割し、
分割したデータを単位として入力操作あるいは出力操作
を行う場合を示している。図中の７は転送データの切替
回路、８はレジスタＡ、９はレジスタＢ、１０はビット
反転回路、１１は排他的論理和をとるＥＸＯＲゲート、
１２はビット反転回路を制御する反転制御端子、１３と
１４はソート対象データの入力端子と出力端子、１５は
降順ソート処理器である。切替回路７とレジスタ８，９
で転送回路を形成する。

降順ソート処理器１５は、データの比較転送処理を行う
ユニット６の繰り返し構造からなり、降順ソート専用で
ある。従って、各ユニットではソート処理を行う際に、
第１のメモリであるメモリＡと第２のメモリであるメモ
リＢをともにオール“Ｏ″に初期設定する。ここで、オ
ール“Ｏ”とは、メモリの全ビットを理論値“０”に設
定することである。この時、フラグレジスタ４も同時に
理論値“Ｏ”に初期設定する。

本降順ソート処理器における入力操作と出力操作は、転
送と比較の２つのフェーズからなる。入力操作における
転送フェーズでは、左方向からの転送データをレジスタ
ＡあるいはレジスタＢにセントする。この時、メモリＡ
あるいはメモリＢ内の対応するデータを切替回路７を介
して右方向に送出するとともに、反対側のレジスタＢあ
るいはレジスタＡに対応するメモリからデータを読み込
む。比較フェーズでは、レジスタＡ及びレジスタＢにセ
ットされた２個のデータを比較するとともに、レジスタ
Ａ及びレジスタＢのイ直をメモリＡおよびメモリＢに書
き込む。この転送フェーズと比較フェーズからなる入力
操作を繰り返してルーコードの入力が完了した段階で、
ルコード分の比較結果をフラグレジスタ４にセットする
。ルーコードの入力が完了したら、新たにセットしたフ
ラグレジスタの値に基づいて、次のレコードの入力を行
う。

全レコードの入力が終了した段階で、今度は出力操作を
行う。出力操作における転送フェーズでは、右方向から
の転送データをレジスタＡあるいはレジスタＢにセット
する。この時、メモリＡあるいはメモリＢ内の対応する
データを切替回路７を介して左方向に送出するとともに
、反対側のレジスタＢあるいはレジスタＡに対応するメ
モリからデータを読み込む。出力操作における比較フェ
ーズは、入力操作と同じである。以上示したように、入
力操作時には、各ユニットでフラグレジスタ４の値に基
づいて切替回路７を制御して、レジスタＡ８およびレジ
スタＢ９の内で小さい方を右方向に転送する。出力操作
時には、入力操作時と同様に、フラグレジスタ４の値に
基づいて切替回路７を制御して、レジスタＡ及びレジス
タＢの内で大きい方を左方向に転送する。これらの入力
操作の繰り返しと出力操作の繰り返しによって、降順に
ソートされた結果が得られる。

第３図に示す、本発明実施例におけるソート処理装置で
降順ソートを行う場合には、反転制御端子１２を論理値
“０”に設定し、昇順ソートを行う場合には、反転制御
端子１２を“１”に設定する。

ビット反転回路１０は、転送データの各ビットにＥＸＯ
Ｒゲートを負荷し、ビット毎に反転／非反転の制御を行
う。第４図は、ＥＸＯＲゲートの入出力関係を示した図
である。ＥＸＯＲゲートの出力は、２つの入力の排他的
論理和であるから、片方の入力を反転制御端子とすると
、他方の入力端子の反転／非反転を制御できる。

本ソート処理装置が、ソート対象とするデータは、文字
列あるいは正整数であるから、ビット反転を行うことよ
って、′１″の補数をとることになり、ビット反転操作
により、２個のデータの大小関係を逆転させることがで
きる。従って、入力データの各ビットを反転した後に、
降順ソート処理器１５に入力し、得られた出力を再度ビ
ット反転することで昇順にソートできる。

次に、本実施例に示すソート処理装置で、レコード内に
複数のキーを設定し、複数のキーのそれぞれに対して、
昇順あるいは降順にソートするマルチキーソートについ
て具体例を用いて説明する。

第５図は、１０進４桁の正整数を対象として、千の位を
降順に、百の位を昇順に、十の位、−の位を降順にソー
トする場合の例である。本例では、各数字を１バイトで
表わし、１バイト単位で比較と転送の入出力操作を行う
。反転制御信号Ｃは、各位の入出力操作と同期して、千
の位は論理値“０”、百の位は論理値“１”、十の位は
論理値“０”、−の位は論理値“０”を反転制御端子１
２から与える。この結果、入力レコードは、ビット反転
回路１０によって、百の位のみがビット反転して補数と
なっている。図では、各桁を１６進表示していることか
ら、ビット反転操作によって、１（２進表示でｏｏｏｉ
　＞はＥ（２進表示で１１１０）に、２はＤに、３はＣ
に変換されている。この反転処理後の各レコードを降順
ソート処理器１５に入力し、降順にソートする。得られ
た結果を再度ビット反転回路１０に入力し、反転制御信
号Ｃに基づいて百の位のみビット反転することによって
、各レコードのビットパターンを再現する。以上示した
ように、ソート対象データを複数に分割し、分割したレ
コードのそれぞれの入力操作あるいは出力操作と同期し
て、ビット反転手段を制御することによって、ソート対
象データ内に複数の領域を設定して、それぞれの領域に
対して他の領域とは独立に昇順又は降順にソートするこ
とにより容易にマルチキーソートを行うことができる。

本実施例では、降順ソート処理器１５とビット反転回路
を組合わせた場合を示したが、昇順ソートのみを実行で
きる昇順ソート処理器を降順ソート処理器の代わりに用
いた場合でも、反転制御信号の論理値（０，１）を木実
側倒とは逆にすることによって、容易に昇順／降順ソー
トおよびマルチキーソートを行うことができる。

（５）発明の効果 以上実施例をもって説明したように、本発明のソート処
理装置では、降順あるいは昇順のいずれか一方にソート
できるソート処理器に対して、レコードを入力、出力す
る入出力部に、制御によってデータのビットを反転する
ビット反転手段を具備したことによって、降順あるいは
昇順のいずれであってもソート可能とするとともに、レ
コード内に複数のキ一部を設け、入力操作および出力操
作と同期してビット反転手段を制御することによって、
複数のキーのそれぞれに対して昇順あるいは降順にソー
トするマルチキーソートを実現したことである。

従来のソート処理装置で降順ソートと昇順ソートを行う
ためには、−次元接続した複数個のユニットの各々で初
期設定する値を変更し、さらに、人力操作時および出力
操作時に転送するデータの大小を変更しなければならな
い。このため、ユニットの制御回路が複雑になり、ソー
ト処理装置の回路量が増加するとともに、処理速度を制
限する要因となっていた。本発明では、降順ソートある
いは昇順ソートのいずれかのソート処理器で十分である
から、ソート処理装置の回路量の削減と、処理速度を向
上できる利点がある。

さらに、従来のソート処理装置では回路が複雑になり、
実現することが困難であったマルチキーソートをわずか
な付加回路で実現できる利点がある。

【図面の簡単な説明】

第１図は従来のソート処理装置の構成図、第２図は第１
図に示したソート処理装置の動作原理図、第３図は本発
明の一実施例であるソート処理装置の構成図、第４図は
第３図に示したビット反転回路を構成するＥＸＯＲゲー
トの動作図、第５図は第３図のソート処理装置による複
数キーに対するソート処理の動作説明図である。 １・・・第１のメモリ、　２・・・第２のメモリ、３・
・・比較器、　　４・・・フラグレジスタ、５・・・入
出力回路、　６・・・ユニット、７・・・切替回路、　
　８・・・レジスタＡ。 ９・・・レジスタＢ、　１０・・・ビット反転回路、１
１・・・ＥＸＯＲゲート、　１２・・・反転制御端子、
１３・・・入力データ端子、　１４・・・出力データ端
子、１５・・・降順ソート処理器。

Claims (1)

【特許請求の範囲】
1. （１）２個のデータを保持するメモリと、該メモリに保
   持されたデータ間の大小関係を判定する比較器と、該比
   較器による該メモリに保持された２個のデータの大小関
   係にもとづいて、該２個のデータのいずれか一方を右方
   向又は左方向に転送するための転送回路とを少なくとも
   有する比較転送ユニットの一次元アレイ構造からなるソ
   ート処理器を備えて、文字列あるいは正整数を対象とし
   て昇順あるいは降順のいずれかにソートできるソート処
   理装置において、 前記ソート処理器を降順又は昇順に特定されたソート処
   理器に構成するするとともに、該ソート処理器にソート
   対象データを入力あるいは出力する際に二値符号で表わ
   されたソート対象データの各々のビットを反転するか否
   かの機能を有するビット反転手段を具備し、該ビット反
   転手段のビット反転操作を実行するか否かによって昇順
   あるいは降順のいずれのソートも実行できるように構成
   されたことを特徴とするソート処理装置。