qsort のアルゴリズムについて

現在Solaris上で作られたソフトウェアをwindowsに乗せ換えるポーティング作業を
行っているのですが、qsortの結果が一致せずに困っています。

比較関数で判定できる範囲は一致するのですが、比較関数が一致するデータ同士の順番が
一致せず、その結果出力される生成物の内容が異なってしまいます。
（同じ生成物が作成されなければポーティング作業完了と成りません）
多分qsortのアルゴリズムの違いだと思うのですが、Solarisのqsortのアルゴリズムがわかる方
いらっしゃいませんか？

Solarisのコンパイラは以下の通り
Sun WorkShop Compiler Csparc 5.0

出来ればqsortのソースコードが有ればよいのですが、軸要素の決定方法だけでも解れば
幸いです。

いくつか、公開されているアルゴリズムを試してみたのですが、一致する物は有りませんでした。
（Windowsのソート結果とも違いました）

因みに、Windowsの開発環境は、
Microsoft Visual Studio 10.0
です。

No.7 回答者： t-okura 回答日時： 2012/06/13 22:15

Open Solaris の qsort ソースは

http://src.opensolaris.org/source/xref/sparks/sp …
ではないでしょうか。

No.6 回答者： root139 回答日時： 2012/05/15 02:39

> 新システムと旧システムでグループ内に新旧で同じレコードが

> グループ化されていないのが問題と成っています。

これがどういった意味で問題となっているのでしょうか？
新・旧システムが連携する必要が有るのでしょうか？
それともポーティングの検証として突合せを行なうためでしょうか？

> お客様に問題の比較関数にキーを追加して旧システムの再構築を行って・・・

という案が出るくらいですから、既存のデータとの一貫性では無いと思いますが。


比較関数が一致するデータ同士の順番については、元のSolaris版でも「キー列の値もデータ数も順番も同じ入力に対しては同じソート結果になる」以上のことは前提としていないはずですので、Windows版で使用するソート関数に同様の前提が成り立つことが確認できれば大丈夫な気もするのですが・・・。


まあ、作業量的に可能ならば、お話の様に比較関数にキーを追加する方が良いとは思います。


ちなみにピボットをデータ列からランダムに選ぶやり方も有るので、「キー列の値もデータ数も順番も同じ入力に対しては同じソート結果になる」という前提の成り立たない QuickSort 実装も有りえます。

No.5 回答者： don_go 回答日時： 2012/05/13 23:33

安定ソートでないqsortを使う限り同等なデータのソート順序

は不定になります。

＞データを追加して実施した所関係の無い所まで順番が変わって
＞しまいました。
＞データを削除したら元に戻りました。
旧システムも今まで気づかれていなかっただけで、同様な結果に
なると思われます。

これを固定化しようとするのであれば、旧システムと出力順が
変わってしまいますが、連番(読み込み順)や作成日時等の項目を
ソートキーとして追加する等の手段をとる必要があります。

出力順が異なる件に関しては、No.3の回答にあるように条件交渉
してみてはどうでしょうか？
＞例えば、下記の様なものも作業完了の条件として考えられるのではないでしょうか？
＞・Solaris版で出力された全データがWindows版でも過不足無く出力されている事
＞・(比較関数の)仕様に従ってソートされている事

この回答への補足

＞同等なデータのソート順序は不定になります。
ソート前の順番にならないだけで、ソートアルゴリズムに則った順番に並びます。

現在、お客様に問題の比較関数にキーを追加して旧システムの再構築を行ってもらい、
同じ修正を新システムに施し、出力結果が一致することによりポーティングＯＫと
しようと言う話に成ってきています。

但し、水平展開として、同じような箇所が無いか調査し、同等な処置を施さなければ
成りません。
ソート対象と成るメモリテーブルは100以上有り、qsort関数の使用箇所は、数百有ります。
そのすべてを調査し、曖昧な比較関数が有れば、ユニークに成る様にキーを追加し、
ソート順を固定化する事による影響を調査し、お客様に、修正依頼をだして再構築して
もらい、出力結果の一致確認を行なう。
気が狂いそうです。

旧システムのqsort関数のソースコードが有れば、又、軸要素の決定方法が解れば
ユーザ関数としてsort関数を作成し、システム上のqsort関数の使用箇所を、一括置換で
ユーザー関数に置き換えて再構築し、最終出力結果の一致確認だけで良いので
何とか成らないかと、探している状況です。

補足日時：2012/05/14 00:35

No.4 回答者： Fewhellton 回答日時： 2012/05/13 15:36

qsortアルゴリズムの違いよりは、ソート対象のデータ型の違いか、データの文字コードの違い（UTF16LE（またはSJIS）、EUC）、CPUレベルでのバイト順（Big Endian, Little Endian）の違いの方が疑わしいと思います。

アルゴリズムの違いを疑うのであれば、アセンブラコードをデバッガを使ってトレースすればはっきりするでしょう。

この回答への補足

文字コードの違いやEndianの問題はデータの移行時に変換されています。
またソート対象キーは数値フィールドなので文字コードは関係ありませんし、
キー単位でのソートは出来ています。
キーが同じレコードの順番が新旧システムで違うので、qsortアルゴリズムの違いと断定
しました。
旧システムは、旧システムはお客様が業務で使用しているので、デバッガでトレース
なんて荒業は行うことは出来ません。

補足日時：2012/05/13 23:38

No.3 回答者： root139 回答日時： 2012/05/13 14:18

直接的な回答ではなく恐縮ですが・・・。

問題の本質は作業完了の条件が不適切だったいうことでは無いでしょうか。
比較関数が一致するデータ同士の順番は、仕様としては特に意味が無いわけですよね？

であるならば、依頼者側に作業完了の条件を修正してもらう様に交渉してはいかがでしょうか？
契約の内容の見直しも考える事になるのかも知れませんが、解決できるかどうかも分らなく、かつ本質的に不要な作業に無駄な工数を掛けるよりも建設的かと。

例えば、下記の様なものも作業完了の条件として考えられるのではないでしょうか？
・Solaris版で出力された全データがWindows版でも過不足無く出力されている事
・(比較関数の)仕様に従ってソートされている事

この回答への補足

＞比較関数が一致するデータ同士の順番は、仕様としては特に意味が無いわけですよね？
どうも、データ作成時に特定のキーでソートし同一キー内で連番を付加し（この番号が、
新旧で順番が異なる）、その後別の複数のキーでソートし(此方はキーにてユニークに
成るので新旧で同じになる)データをメモリテーブルに登録されます。
その後別のプログラムで付加された番号単位でレコードをグループ化し、
（1番目のグループ、２番目のグループ、３番目の・・・）グループ単位で
処理を行っている様なのですが。
新システムと旧システムでグループ内に新旧で同じレコードがグループ化されていない
のが問題と成っています。（グループ内が同じレコードでグルーピングされていれば順番、
グループ番号が一致しなくても問題ないのですが。）

補足日時：2012/05/13 23:15

No.2 回答者： don_go 回答日時： 2012/05/13 13:25

＞同じデータを読ませる限り同じ結果になる事は確認済みです。

同等なデータのソート前の順序は、ソート後も同じですか？
または、データ1件追加した時に順番がどうなりますか？

この回答への補足

＞同等なデータのソート前の順序は、ソート後も同じですか？
それは新システムも旧システムもソート前と変わっています。
但し新システムと旧システムでは順序が違うのが問題です。

＞データ1件追加した時に順番がどうなりますか？
旧システムはお客様が業務で使用しているのでデータの追加は出来ません。
新システムは元データに無理やりデータを追加して実施した所関係の無い所まで
順番が変わってしまいました。
データを削除したら元に戻りました。

補足日時：2012/05/13 21:49

No.1 回答者： don_go 回答日時： 2012/05/13 07:24

qsort(クイックソート)は、安定ソートではありません。

※（あんていソート、stable sort）ソート（並び替え）の
　アルゴリズムのうち、同等なデータのソート前の順序が、
　ソート後も保存されるもの。
従って、同等なデータがある場合のソート順は不定となります。

Solaris上で作られたソフトウェアで作成されたデータが毎回
同じ結果になるかは、確認してみましたか？

この回答への補足

同じデータを読ませる限り同じ結果になる事は確認済みです。
しかし、新システムと旧システムで結果が違っているので困っています。

補足日時：2012/05/13 09:26