JPH03231326A - ソーティング方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はソーティング方法に関し、特に地理情報処理、
コンピュータグラフィックス、ＶＬＳＩ設計、ＣＡＤ、
パターン認識、生態学、結晶学。

数値計算、形状科学などの分野で、ソーティングのキー
が複数存在し各キーが完全に独立していない場合に、計
算幾何学上ある程度あいまいなソーティングを必要とす
る際に適用されるソーティング方法に関する。

〔従来の技術〕

従来、−次元処理であるソーティングを多次元に拡張す
る場合は、その次元分のキーに順位を設定し、高順位の
キーから順次ソーティングを行っていた。

例えば、第３図のようにＸＹ平面上にランダムに点が存
在している場合、これらの点を座標の小さい順に並べる
ために、第１キーとしてＹ座標値を第２キーとしてＸ座
標値を設定しソーティングを行う。すなわち、ソーティ
ング処理としては、比較すべき２点を抽出してまず第１
キーのＹ座標値を比べ、そこで大小関係が決定すれば比
較処理は終了するが、もし同一値であった場合には更に
Ｘ座標値を比べ大小関係を決定する方法である。

この手法を第３図の魚群に適用した結果を示したのが第
４図であり、Ｙ座標値が最小のＡ点から最大のＢ点まで
配列の順に直線で結んである。

この手法を使用すると、本来間等の立場であるＸ座標値
とＹ座標値に明確な優劣を設けてしまうので、Ｙ座標値
の差が前面に出て第４図のようなＸ座標値の移動が激し
いソーティング結果しか得られない。

そこで、この難点を解消するため、第１キーであるＹ座
標値に一定のステップを設定し、このステップ幅内では
Ｙ座標値は同じであるという定義に基づいた処理を行う
と、Ｘ座標値の激しい移動を少なくした結果を得ること
ができる。この手法を第３図の魚群に適用した結果が第
５図である。

第５図には、その効果を見やすくするため、Ｙ座標値が
点線で示しであるステップラインの両側にありＸ座標値
の移動量が極端に大きい２点を結ぶ直線は省略しである
。

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

しかしながら、上述した第１キーにステップを与えてソ
ーティングする手法は、ステップを固定的に与えざるを
得ないため、ステップラインをまたいだ２点は非常に接
近していてもソーティングするとかなり離れた順番に位
置することになる。

しかも、ステップは第１キーの値で固定的に指定するわ
けであるから、多少あいまいなソーティング結果を得た
い場合にも、この指定値が特有の意味を持ち、ソーティ
ング結果にもステップラインを境界とする区画が明確に
表れるという問題点がある。

本発明の目的は、二つのキーの特定値に固定的な意味を
付与することなく、多少あいまいなソーティングを容易
に実施できるソーティング方法を提供することである。

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

本発明のソーティング方法は、与えられたデータ群を第
１キーと第２キーとでソーティングする第１の手順と、
選択された基準値に対して第１キーがあらかじめ与えら
れた値以内の一対のデータ要素をクイックソートの手法
で抽出する第２の手順と、前記第２の手順で抽出された
一対のデータ要素を第１キーと第２キーとを入れ代えて
クイ・ツクソートの手−法で評価し直す第３の手順と、
前記第１の手順でソーティングされた状態のデータ群に
対し前記第２及び第３の手順をクイックソートの手法で
データ群に属するすべてのデータ要素の再評価が終了す
るまで再帰的に繰り返す第４の手順とを備えて構成され
゛ている。

〔実施例〕

次に、本発明の実施例について図面を参照して説明する
。

第１図は本発明の一実施例の動作を示すＳＰＤ形式のフ
ローチャードであり、第３図に示した魚群に対する適用
例を示している。

第１図のフローチャードは、与えられたデータ群をＹ座
標−値を第１キー、Ｘ座標値を“第２キーとしてソーテ
ィングする第１の手順Ｓ１と、選択された基準値に対し
てＹ座標値があらかじめ与えられた値以内の一対のデー
タ要素をクイックシー下の手法で抽出する第２の手順Ｓ
２と、第２の手順Ｓ２で抽出された一対のデータ要素に
対して、Ｘ座標値を第１キーにＹ座標値を第２キーにし
てクイックソートの手法で評価し直す第３の手順Ｓ３と
一２第１の手順Ｓ１でソーティングが終了した状態のデ
ータ群に対して第２の手順Ｓ２及び第３の手順Ｓ３をク
イックソートの手法でデータ群に属するすべてのデータ
要素の再評価が終了するまで再帰的に繰り返し実行する
第４の手順Ｓ４とを備えている。

すなわち、第１の手順Ｓ１で通常のソーティングを行っ
た後、公知のクイックソートの手法に若干の修正を加え
たあいまいソーティングを第４の手順Ｓ４（第２の手順
Ｓ２と第３の・手順Ｓ３から成る）により実行するもの
である。

クイックソートの手法のアルゴリズムは、データ群のほ
ぼ中央から一つのデータ要素を選択し、キー値か選択し
たデータ要素のキー値（基準値）以上および未満の一対
の要素をデータ群の両端から順次抽出して両者を入れ替
える操作を繰り返すことにより、データ群を基準値未膚
および以上のキー値を有する二つのサブデータ群に分割
する処理を、分割された各サブデータ群に対して再帰的
に繰り返してソーティングを行うものである。

上述した第２の手順Ｓ２と第３の手順Ｓ３は、それぞれ
上記のクイックソートの構成手順と同様であり、クイッ
クソートの既存のプログラムの一部を修正することによ
り容易にコーディングすることができる。

上述したこの発明のあいまいソーティングの手法は、基
本アルゴリズムにクイックソートを使用しており、クイ
ックソートの手法か細分化されたサブデータ群に再帰的
に処理を積み重ねる手法であるため、あいまいさが全体
に波及することなく部分的な並べ替えにとどまり、本発
明の目的とするあいまいなソーティングにうまくマツチ
ングしている。

第２図は第３図に示した魚群に対し、本実施例のソーテ
ィング方法を適用した結果を示す説明図である。第２図
に示すＸ座標軸に平行な点線は第５図のステップライン
を参考のために示したものであり、また第５図と同様に
Ｘ座標値の移動が極端に激しい２点を結ぶ直線は図面を
見やすくするため省略しである。

第２図の例は、あいまいソーティングを施すためにあら
かじめ与えられるＹ座標値のあいまい距離を、ステップ
ライン間隔と同じに設定して実施したものである。その
結果は第２図に見られるように、第５図の手法の利点を
残したままＹ座標の固定的なステップラインに拘束され
ないソーティング結果が得られている。

〔発明の効果〕

以上詳細に説明したように、本発明のソーティング方法
は、複数のキーの一方を単純な優先キーとして完全に分
離せずに適度に関連し合ってソーティングが実行される
ため、多次元のソーティングとしである程度あいまいな
並べ替えを必要とする場合に、従来はソーティング結果
に明確に表れていたキーの優先度や特定値の意味が表現
されず融通性の高いソーティング結果が得られる効果が
ある。又、そのソーティングの基本アルゴリズムにクイ
ックソートを使用したことにより、比較的簡単にコーデ
ィングすることができ容易に実施できる利点がある。

【図面の簡単な説明】

第１図は本発明の一実施例の動作を示すＳＰＤ形式のフ
ローチャート、第２図は本発明の適用結果の一例を示す
説明図、第３図はソーティング例を説明するための魚群
の配置図、第４図および第５図は従来の方法を用いたソ
ーティング結果の説明図である。 Ｓｌ・・・・・・第１の手順、Ｓ２・・・・・・第２の
手順、Ｓ３・・・・・・第３の手順、Ｓ４・・・・・・
第４の手順。

Claims (1)

【特許請求の範囲】
1. 　与えられたデータ群を第１キーと第２キーとでソーテ
   ィングする第１の手順と、選択された基準値に対して第
   １キーがあらかじめ与えられた値以内の一対のデータ要
   素をクイックソートの手法で抽出する第２の手順と、前
   記第２の手順で抽出された一対のデータ要素を第１キー
   と第２キーとを入れ代えてクイックソートの手法で評価
   し直す第３の手順と、前記第１の手順でソーティングさ
   れた状態のデータ群に対し前記第２及び第３の手順をク
   イックソートの手法でデータ群に属するすべてのデータ
   要素の再評価が終了するまで再帰的に繰り返す第４の手
   順とを備えたことを特徴とするソーティング方法。