-PR-
解決済み

ヒープソートは2重ソートできない?

  • すぐに回答を!
  • 質問No.35189
  • 閲覧数186
  • ありがとう数1
  • 気になる数0
  • 回答数1
  • コメント数0

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

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

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

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

 これはヒープソートを使用している限り仕方のないことなのでしょうか。あるいは何らかの解決方法を知っている方、よろしくお願いします。
通報する
  • 回答数1
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.1
レベル8

ベストアンサー率 65% (17/26)

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

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

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

n1 のみを比べてソートしようとするなら,マージソートのようにその性質をもった別のソートアルゴリズムを使えばよいと思います.
お礼コメント
noname#25358

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

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

 やはりヒープソートでは無理でしょうかね。
投稿日時 - 2001-02-02 01:24:07
-PR-
-PR-
このQ&Aで解決しましたか?
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


専門家があなたの悩みに回答!

-PR-

ピックアップ

-PR-
ページ先頭へ