ヒープソートは２重ソートできない？

質問

ソートに関して詳しい方、相談にのっていただけたらと思います。

　ＣＧＩを使ってヒープソートするロジックを組みました。
　そのルーチンはただ単項データをソートするだけでなく、たとえば、配列変数 n1 と 配列変数 n2 にそれぞれデータが入っていたとき、n1 をソートすると、それに連動して n2 の中身も一緒にソートされます。
　言うならば、バラバラに並んだビデオテープを番号順に並べ替えると、一緒にタイトルも並べ変わる感じです。

　ところが、配列 n1 をソートしていてたまに同じ数字が入っていることがあります。そういうときは n2 の順にしたいのです。

　そこで、先に n2 をソートしてから n1 をソートするといいのではと考え、そのようにプログラムを組んでみました。
　ところが実際には、n1 をソートした瞬間に、せっかく並べ替えた n2 の内容がバラバラになってしまうのです。
　「n1 の内容が同じ場合は n2 を昇順に並べる」という処理を記述していても、実際には n2 の内容はバラバラです。

　これはヒープソートを使用している限り仕方のないことなのでしょうか。あるいは何らかの解決方法を知っている方、よろしくお願いします。

回答No.1

takebe · ベストアンサー

n1，n2の組について辞書式の順序で整列すればどのソートアルゴリズムでも並び替えられると思います．

辞書式の順序とは，例えば，(5, 7) と (5, 9) とを比べると，n1 の 5 は同じなので n2 を比べて (5, 9) の方が大きいとするような順序です．

順序がつけられない要素でももともと並んでいた順番が保たれるという性質は何か名前がついていたと思いますが，忘れてしまいました．岩波のアルゴリズムとデータ構造の本に書いてあったと思うのですが...

n1 のみを比べてソートしようとするなら，マージソートのようにその性質をもった別のソートアルゴリズムを使えばよいと思います．

お礼

ありがとうございます。
　ためしにクイックソートでロジックを組んでみたところ、見事にプログラムがハングりまして、けっきょくヒープソートでやるしかなさそうです(^_^;

　もともと高校が職業高校だった関係上、数学でそういう勉強を一切してないので、中学生並みの知識で理解できる方法しか使えないのです(笑)　ヒープソートはインターネットに落ちていたからよかったのですが(^_^;

　やはりヒープソートでは無理でしょうかね。