JPH04160532A - ソート処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、データテーブルに格納されたデータを、大
きなものあるいは小さなものから昇順もしくは降順に並
べ換えるソート処理装置に関するものである。

〔従来の技術〕

第３図は従来のソート処理装置を示すブロック図である
。図において、１はデータがその大小に関係なくメモリ
上に連続して格納され、そのデータが昇順もしくは降順
に並べ換えられるデータテーブルである。２はこのデー
タテーブル１内のデータを順次読み出してゆくデータテ
ーブル読出回路であり、３はこのデータテーブル読出回
路２にデータテーブル１の読み出しアドレスを与える読
出カウンタである。４はデータテーブル読出回路２の読
み出したデータと、読出カウンタ３の計数値に対応する
アドレスよりも前のデータテーブル１の内容とを比較す
る比較回路である。５は比較回路４による比較結果をも
とにデータテーブル１の並べ換えを行うデータテーブル
並べ換え回路である。

次に動作について説明する。ここではデータテーブル１
内のデータを大きなものから昇順にソートする場合につ
いて説明する。第４図はその処理イメージを示す説明図
である。

まず、読出カウンタ３に初期値“１パをセットし、デー
タテーブル１より当該読出カウンタ１の計数値”１″に
対応する最初のアドレスに格納されているデータ″３”
をデータテーブル読出回路２によって読み出す。比較回
路４はこのデータテーブル読出回路２の読み出したデー
タ”３”を、読出カウンタ３の計数値に対応するアドレ
スよりも前のデータテーブル１の内容と大小比較を行い
、データテーブル並べ換え回路５はその比較結果より読
み出したデータの方が大きな場合にはデータの入れ換え
を行う。今回は最初のアドレスが読み出されて比較対象
のデータがないため、第４図（ａ）に示すようにデータ
テーブル並べ換え回路５にょるデータの並べ換えは実行
されない。

次いで、読出カウンタ３を歩進させ、その計数値”２″
に対応したデータテーブル１０２番目のアドレスのデー
タ゛２′″がデータテーブル読出回路２にて読み出され
、比較回路４に送られる。比較回路４はそれを読出カウ
ンタ３の計数値ＩＩ　２１１に対応するアドレスよりも
前のチータテ−プル１の内容、即ちデータ゛°３″との
大小比較を行う。

この場合、第４図（ｂ）に示すように読み出したデータ
の方が小さいのでデータテーブル並べ換え回路５はデー
タの並べ換えを行わない。次に、読出カウンタ３の計数
値を°３″に歩進させて同様の処理を行う。この場合、
データテーブル読出回路２にて読み出されたデータ”９
″は先頭のデータ”３″よりも大きいので、データテー
ブル並べ換え回路５は第４図（Ｃ）に示すようにデータ
テーブル１のデータの並びを”９　、３　、２　”の順
に並べ換える。

以下同様にして処理を進め、読出カウンタ３の計数値が
”６″となってデータテーブル読出回路２の読み出した
最後のデータ”１″の処理が終わった時点で、データテ
ーブル１内のデータは第２図（ｆ）に示すように”９，
８，７，３，２．１”の順序に並べ換えられ、ソート完
了となる。

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

従来のソート処理装置は以上のように楢成されているの
で、データテーブル１の先頭からデータを順次読み出し
、そのデータとデータテーブル１内の読み出した位置ま
でのデータとを大小比較して昇順もしくは降順に並べ換
えるものであり、データ量が多くなると比較に多大な時
間を要し、ソート処理が遅くなるという課題があった。

この発明は上記のような課題を解消するためになされた
もので、ソートの処理完了時間を大幅に短縮できるソー
ト処理装置を得ることを目的とする。

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

この発明に係るノート処理装置は、データテーブルに格
納されたデータの範囲をアドレスに持つデータ有無テー
ブルを設け、データテーブルより順次読み出したデータ
をアドレスとして前記データ有無テーブルの該当アドレ
スの内容を書き換えてゆき、全データについてデータ有
無テーブルの書き換えが終了すると、データ有無テーブ
ルを昇順もしくは降順に読み出して、データに書き換え
があった場合にそのアドレスをデータとして順番にデー
タテーブルに書き込んでゆくものである。

〔作　用〕

この発明におけるデータ有無テーブル書込回路は、デー
タテーブルより順次読み出されたデータに基づいて、デ
ータ有無テーブルの前記データに該当するアドレスの内
容の書き換えを行い、データテーブル書込回路は、全デ
ータについての前記書き換え処理の終了時点で昇順もし
くは降順に読み出されたデータ有無テーブルのデータよ
り、当該データの書き換えがあったアドレスをデータと
して順番にデータテーブルに書き込んでゆくことにより
、ソートの処理完了までの時間を大幅に短縮することの
できるソート処理装置を実現する。

〔実施例〕

以下、この発明の一実施例を図について説明する。第１
図において、１はデータテーブル、２はデータテーブル
読出回路、３は読出カウンタであり、第３図に同一符号
を付した従来のそれらと同一、あるいは相当部分である
ため詳細な説明は省略する。

６は前記データテーブル１に格納されたデータの範囲（
以下、データレンジという）をアドレスに持つデータ有
無テーブルであり、７は前記データテーブル読出回路２
で読み出されたデータをアドレスとして、このデータ有
無テーブル６の該当アドレスの内容を書き換えるデータ
有無テーブル書込回路である。８はデータテーブル１に
格納された全データについてデータ有無テーブル６の書
き換えが終了した後、データ有無テーブル６を昇順もし
くは降順に読み出してゆくデータ有無テーブル読出回路
であり、９はデータ有無テーブル読出回路８の読み出し
たデータに書き換えがあった場合に、そのアドレスをデ
ータとしてデータテーブル１に順番に書き込んでゆくデ
ータテーブル書込回路である。

次に動作について説明する。今、ソートされるデータの
データレンジが１〜１０であり、その範囲のデータは既
にデータテーブル１に格納されているものとする。従っ
て、データ有無テーブル６は前記データレンジに対応し
たアドレス”１”′〜”１０′′を有し、それら全てが
”０″に初期化されているものとする。

ここで、第２図はその処理イメージを示す説明図である
。まず、読出カウンタ３に初期値”１′′がセットされ
ると、データテーブル読出回路２によってデータテーブ
ル１より当該読出カウンタ３の計数値“１”に対応する
最初のアドレスに格納されているデータ”３″が読み出
され、データ有無テーブル書込回路７に送られる。デー
タ有無テーブル書込回路７は第２図（ａ）に■で示すよ
うに、このデータテーブル読出回路２が読み出したデー
タ”３”をアドレスとしてデータ有無テーブル６をアク
セスし、当該アドレス”３°′の内容を”０′′から”
１′”に書き換える。

次いで、読出カウンタ３を歩進させ、その計数値”２”
に対応したデータテーブル１０２番目のアドレスのデー
タ”２″がデータテーブル読出回路２にて読み出される
。データ有無テーブル書込回路Ｔはそれをアドレスとし
て、第２図（ａ）に■で示すようにデータ有無テーブル
６のアドレス”２”′の内容を”１″に書き換える。以
下同様にして処理が進行し、読出カウンタ３の計数値が
”６パとなってデータテーブル１の最後のアドレスのデ
ータ”１”が読み出され、第２図（ａ）に■で示すよう
にデータ有無テーブル６のアドレス”１”の内容が”１
”に書き換えられる。

データ有無テーブル読出回路８は、このようにしてデー
タテーブル１に格納された全データについてのデータ有
無テーブル６の書き換えが終了したことを知ると、デー
タ有無テーブル６を所定の順序で読み出してゆく。その
際、ソートの指定が昇順であればデータ有無テーブル６
のアドレスの太きいものから小さいものへ、降順であれ
ば小さいものから大きいものへ、順番に読み出してデー
タテーブル書込回路９に出力する。

データテーブル書込回路９はデータ有無テーブル読出回
路８からのデータをチエツクして、それが”１″である
ものについてそのアドレスをデータとし、データテーブ
ル１の先頭から順番に書き込んでゆく。データ有無テー
ブル６内のデータ全てのチエツクが終了すると、昇順の
場合には第２図（ｂ）に示すように９　、８　、７　、
３　、２　、１　”の順に、また、降順の場合には第２
図（Ｃ）に示すように”１　、２　、３　、７　、８　
、９　”の順にデータテーブル１内のデータが並べ換え
られ、ソート完了となる。

なお、上記実施例では、データ有無テーブル１の各アド
レスを１ビツト構成として同一データの重複については
考慮していないものを示したが、各アドレスを１バイト
、１ワード等の複数ビット構成としてもよく、そのよう
に構成することによって、同一データの重複回数をデー
タ有無テーブルに記録するようにすれば、データが重複
するデータテーブルのソートも可能となる。

〔発明の効果〕

以上のように、この発明によれば、データテーブルの各
データに該当するデータ有無テーブルのアドレスの内容
を書き換え、当該データ有無テーブルを昇順または降順
に読み出して、その書き換えられたアドレスをデータと
して順番にデータテーブルに書き込んでゆくように構成
したので、データテーブルからデータを読み出す度にそ
の比較、並べ換えを行う必要がなくなり、ソートの処理
完了までの時間を大幅に短縮することのできるソート処
理装置が得られる効果がある。

【図面の簡単な説明】

第１図はこの発明の一実施例によるソート処理装置を示
すブロック図、第２図はその処理イメージを示す説明図
、第３図は従来のソート処理装置を示すブロック図、第
４図はその処理イメージを示す説明図である。 １はデータテーブル、２はデータテーブル読出回路、６
はデータ有無テーブル、７はデータ有無テーブル書込回
路、８はデータ有無テーブルＵ出回路、９はデータテー
ブル書込回路。 なお、図中、同一符号は同一、又は相当部分を示す。 特許出願人　　　三菱電機株式会社 ト ユー〜−寸［Ｆ］■トの■９

Claims (1)

【特許請求の範囲】
1. 複数のデータが格納されたデータテーブルと、前記デー
   タテーブルに格納されたデータの範囲をアドレスに持つ
   データ有無テーブルと、前記データテーブルより前記デ
   ータを順次読み出してゆくデータテーブル読出回路と、
   前記データテーブル読出回路で読み出されたデータをア
   ドレスとして、前記データ有無テーブルの当該アドレス
   の内容を書き換えるデータ有無テーブル書込回路と、前
   記データテーブルに格納された全データについて、前記
   データ有無テーブルの書き換えが終了すると、前記デー
   タ有無テーブルを昇順もしくは降順に読み出してゆくデ
   ータ有無テーブル読出回路と、前記データ有無テーブル
   読出回路の読み出したデータに書き換えがあった場合、
   当該アドレスをデータとして順番に前記データテーブル
   に書き込んでゆくデータテーブル書込回路とを備えたソ
   ート処理装置。