JPH0334015A - クイックソート技法における入出力の並行処理方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概　劃 ソート処理、特にクイックソート技法を用いたソート処
理中に、ソート処理の終了した部分のレコードを逐次出
力すると共に、この出力されたしコードの空き領域に次
回に処理されるべき新たなレコードを逐次入力するよう
にしてソート処理が行われるクイックソート技法におけ
る入出力の並行処理方法に関し ソート処理が終了した部分のレコード及び新たに処理さ
れるべきレコードの入出力処理をソート処理と並行して
実行し、ソート処理時間の短縮化を目的とし。

レコ−ド群納ｉｌ＋！Ｉｉに入力されたレコードに対し
クインク技法を用いたソート処理を行って出力するソー
ト処理方式において、上記ソート処理中にソート処理が
終了した部分のレコードを逐次レコード格納領域から出
力すると共に、この出力により空きとなったレコード格
納領域へ次回に処理されるべき新たなレコードを逐次入
力する処理構成となし、ソート処理とソート処理が終了
した部分のレコードの出力処理及び次回に処理されるべ
き新たなレコードの入力処理とが並行して処理されるよ
うに構成されている。

［産業上の利用分野］ 本発明は、ソート処理、特にクイックソート技法を用い
たソート処理中に、ソート処理の終了した部分のレコー
ドを逐次出力すると共に、この出力されたレコードの空
き領域に次回に処理されるべき新たなレコードを逐次入
力するようにしてソート処理が行われるクイックソート
技法における入出力の並行処理方法に関する。

近年のコンピュータシステムの高速化の要求に伴い、ソ
ート処理においてもその高速処理化が要求されている。

〔従来の技術〕

従来の外部記憶装置に格納されているレコードを所定の
順１例えば番号の小さい順に並び換える昇順のソート処
理方式は２入力処理、ソート処理及び出力処理を順次独
立的に行って処理していた。

すなわち、第５図は従来のその処理方式を説明している
処理過程説明図であり５例えばディスク等の外部記憶装
置１に格納されているレコードを処理装置２内の入力バ
ッファ３に入力し、入力バッファ３に入力されたレコー
ドをレコード格納領域４に入力する入力処理が行われ、
このレコード格納領域４に格納されたレコードに対し図
示されていないＣＰＵが昇順のソート処理１例えば上記
クイックソート技法によるソート処理を行っていた。

このクイックソート技法は、レコード群の中から任意に
選び出された境界値に対して当該境界値より小さい番号
を有するレコード群と当該境界値以上の番号を有するレ
コード群とに分割する手順を各群が１つのレコードから
なるまで繰り返すことにより、レコードを所定の順に並
び換える技法である。

レコード格納領域４に格納されたレコードについて、こ
のクイックソート技法をソートマージプログラムに適用
して実行し、昇順に並び換えられたレコードを作業バッ
ファ５に出力し、さらに処理装置２から外部記憶装置６
へ出力する出力処理が行われていた。

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

従来の様に、レコード格納領域４に格納されたレコード
に対し上記クイックソート技法が適用されたソート処理
の全部の終了を待って、昇順に並び換えられたレコード
をレコード格納領域４から作業バンファ５へ出力する出
力処理が行われ、またこの出力処理が終了するのを待っ
て入力バッファ３からレコード格納領域４へ次回に処理
されるべき新たなレコードの入力処理が行われていた従
来のソート処理方式では１入力処理、ソート処理及び出
力処理の各処理が完全に終わってはしめて次の処理へ移
る独立型であるため、ソート処理時間が長くなる欠点が
あった。

本発明はソート処理の終了した部分のレコード及び新た
にソート処理されるべきレコードの入出力処理をソート
処理と並行して実行し、ソート処理時間の短縮化が可能
なりイックソート技法における人出力の並行処理方法を
提供することを目的としている。

ソート処理対象の外部記憶装置ｌに格納されているレコ
ード件数との大小に分けて説明する。

（１）外部記憶装置ｌに格納されているレコード件数が
レコード格納領域４のレコード格納数より大きい場合 初期入力により入力バッファ３を介してレコード格納領
域４に入力された全レコードに対し、処理装置２はソー
ト処理を行う、すなわち第２図（Ｂ）図示の如く、任意
に選定された境界値Ｌｌを基にして大小の分割が行われ
る。当該境界値１１以上の番号を有するレコード群のが
レコード格納領域４に格納される。当該境界値ＬＬより
小さい番号を有する残りのレコード群に対し任意に選定
された境界値Ｌ２　（Ｌ２＜ＬＬ）を基にしてその大小
の分割が行われ、当該境界（ｉＬ２以上の番号を有する
レコード群■がレコード格納領域４に格納される。この
様に分割された大きな番号を有する範囲のレコード群を
常にレコード格納領域４に格納し、小さい番号を有する
範囲のレコード群のレコードに対し境界値を定めて分割
してゆくクイックソート技法が用いられ、クイックソー
トのリミット値になるまで繰り返しその処理が行われる
。

分割されてゆくレコード数がリミット値以下になったと
き、隣同志のレコード間でその番号の大小によって位置
の入れ換えを行う直接挿入法が行われる。この直接挿入
法で昇順に並び換えられたレコード群■のレコードが５
　ソート処理が終了したものとして第２図（Ｃ）図示の
如く作業バッファ５へ出力される。

次いで処理装置２は一番最後に分割されレコード格納領
域４に格納されているレコード群■を取り出し、このレ
コード群■のレコードに対し直接挿入法でレコードを昇
順に並び換える。このレコード群■のソート処理中に、
上記ソート処理の終了したレコード群■が作業バッファ
５へ出力されレコード格納領域４内の空き領域■に新た
にソート処理されるべきレコードが第２図（Ｄ）図示の
如く入力バッファ３から入力される。以下同様に次のソ
ート処理中に、このソート処理の終了したレコード群■
が作業バッファ５へ出力され、レコード格納領域４内の
空き領域■に新たにソート処理されるべきレコードが入
力バッファ３から入力される。

更に次に処理装置２は最後から二番目に分割されレコー
ド格納領域４に格納されているレコード群■を取り出し
、このレコード群■のレコードに対し上記説明のクイッ
クソートのリミット値になるまでクイックソート技法で
分割してゆき、すξフト値以下になったらそのレコード
群内のレコードを直接挿入法で並び換える。この直接挿
入法で並び換えられたレコード群を作業バッファ５へ出
力する１作業バッファ５へ出力して空いたレコード格納
領域４に入力バッファ３から新たにソート処理されるべ
きレコードを入力しておく、この様なソート処理をレコ
ード群■に対して行いそのソート処理が終了したとき１
次のレコード群■、■に対しても同様のソート処理が実
行される。

初期入力でレコード格納領域４に格納された全レコード
に対しそのソート処理が終了して作業バッファ５にすべ
てのレコードが出力されたとき。

当該レコード格納領域４には第２回目のソート処理され
るべきレコードが既に格納された状態となっているので
、処理装置２はレコード格納領域４に格納されている全
レコードに対し直ちに第２回目のソート処理が行える。

（ｎ）外部記憶装置ｌに格納されているレコード件数が
レコード格納領域４のレコード格納数より小さい場合 この場合は初期入力の段階で７外部記憶装置ｌから入力
バッファ３を介してレコード格納領域４へソート処理の
対象となっているレコードがすべて入力されている状態
となっており、従ってＮ）の場合におけるソート処理と
出力処理とだけが並行した形で処理される。ソート処理
が終了したレコードが逐次作業バッファ５へ出力されて
いるので、ソート処理に要する時間が短縮化される。

上記説明は昇順についてなされているが降順についても
同様に行うことができる。

第３図は本発明の入出力処理におけるレコードの転送状
態を説明するレコード転送説明図、第４図はその一実施
例タイムチャートである。

レコード格納領域４には初期入力により第１回目のソー
ト処理の対象となっているレコードが既に入力されてい
るものとする。第４図のタイムチャートを参照しながら
説明すると次の如くである。

すなわちレコード格納領域４のレコードに対しソート処
理が開始されると、初期状態で入カバ・ノファ３−１．
１−２が空きのとき、外部記憶装置１に格納されている
レコード（イ）、（ロ）が人カバソファ３−１へ転送さ
れる。この転送終了を待って外部記憶装置１に格納され
ているレコード（ハ）、（ニ）が入力バツファ３−２に
転送される。なお入力バッファ３−１．３−２は説明の
便宜上２つのレコード（イ）ないしく二）でそれぞれ満
杯となる容量として説明する。

レコード格納領域４のレコードに対する上記説明のクイ
ックソートのりξット値になるまでクイックソート技法
で小さい群に分割してゆき、リミット値以下になったら
その範囲を直接挿入法で昇順に並び換えるソート処理を
行い、最初にソート処理が終了したレコード格納領域４
内の■領域のレコード（い）が作業バッファ３−１へ出
力される。この空きとなったレコード格納領域４内の■
領域に入力バッファ３−１のレコード（イ）が入力され
る。第２番目にソート処理が終了したレコード格納領域
４内の■領域のレコード（ろ）が作業バッファ３−１へ
出力される。この空きとなったレコード格納領域４内の
■領域に入力バッファ３−１のレコード（ロ）が入力さ
れる。同様に第３番目、第４番目にソート処理が終了し
たレコード格納領域４内の０５■領域のレコード（は）
。

（に）が作業バッファ５−２へ逐次出力される。

この作業バッファ５−１．５−２も説明の便宜上２つの
レコード（い）ないしくに〉でそれぞれ満杯となる容量
として説明されている。

入力バッファ３−１からレコード格納領域４ヘレコード
（ロ）を出力し終わった後直ちに又は適当なときに、当
該入力バッファ３−１に外部記憶装置１から新たなソー
ト処理の対象となっているレコード（ホ）、（へ）が入
力されるようになっており、またレコード格納領域４か
ら作業バ・ソファ５−１にレコード（ろ）が入力されて
満杯となったとき直ちに又は適当なときに、当該作業バ
ッファ５−１はレコード（い）、（ろ）を外部記憶装置
６へ出力し空きとなっているので、第５番目。

第６番目のソート処理終了に応しレコード格納領域４内
の■、［Ｆ］領領域各レコード（は）、（へ）が作業バ
ッファ５−１へ逐次出力される。またこの出力により空
きとなったレコード格納領域４内の■、［Ｆ］領領域入
力バッファ３−１からレコード（ホ）、（へ）が逐次入
力される。もう一方の入力バッファ３−２及び作業バッ
ファ５−２も入力バッファ３−１及び作業バッファ５−
１と交互に同様の動作が行われ、入出力処理の連続性が
保持されるようになっている。

この様にソート処理が進行する毎に入力処理及び出力処
理が繰り返され、初期入力によりレコード格納領域４に
格納されていた全レコードに対する第１回目のソート処
理が終了したときには、レコード格納領域４には片仮名
で表された新たなレコードが既に格納された状態となっ
ており、直ちに第２回目のソート処理が開始される。

〔発明の効果〕

以上説明した如く２本発明によれば、ソート処理中に入
出力処理が並行して行われるので、ソート処理時間が短
縮化され、かつ全体の処理時間も短縮化される。

【図面の簡単な説明】

第１図は本発明の詳細な説明するためのレコー名々 ド転送説明図、第２図（Ａ）ないしくＤ）！守発明の一
実施例分解処理説明図、第３図は本発明の入出力処理に
おけるレコードの転送状態を説明するレコード転送説明
図、第４図はその一実施例タイムチャート、第５図は従
来のソート処理方法を説明している処理経過説明図を示
している。 図中、ｌは外部記憶装置、２は処理装置、３゜３−１．
３−２は入力バッファ、４はレコード格納領域、５．５
−１．５−２は作業バッファは外部記憶装置を表してい
る。

Claims (1)

1. 【特許請求の範囲】 外部記憶装置（１）に格納されているレコードを処理装
   置（２）内の入力バッファ（３）に入力すると共に、 入力バッファ（３）のレコードをレコード格納領域（４
   ）に入力し、 このレコード格納領域（４）に入力されたレコードに対
   しクイックソート技法を用いたソート処理を行い、 所定の順に並び換えられたレコードをレコード格納領域
   （４）から作業バッファ（５）を介して外部記憶装置（
   ６）へ出力するソート処理方式において、 上記ソート処理中に、 ソート処理が終了した部分のレコードを逐次レコード格
   納領域（４）から作業バッファ（５）へ出力すると共に
   、 このソート処理が終了した部分のレコードが作業バッフ
   ァ（５）へ出力されることにより空きとなったレコード
   格納領域（４）へ入力バッファ（３）からそのレコード
   分を逐次入力する処理構成となし、 ソート処理とソート処理が終了した部分のレコードの出
   力処理及び次回に処理されるべき新たなレコードの入力
   処理とが並行して処理されるようにした ことを特徴とするクイックソート技法における入出力の
   並行処理方法。