• ベストアンサー
※ ChatGPTを利用し、要約された質問です(原文:ヒープソートは2重ソートできない?)

ヒープソートの2重ソートに関する疑問

takebeの回答

  • ベストアンサー
  • takebe
  • ベストアンサー率65% (17/26)
回答No.1

n1,n2の組について辞書式の順序で整列すればどのソートアルゴリズムでも並び替えられると思います. 辞書式の順序とは,例えば,(5, 7) と (5, 9) とを比べると,n1 の 5 は同じなので n2 を比べて (5, 9) の方が大きいとするような順序です. 順序がつけられない要素でももともと並んでいた順番が保たれるという性質は何か名前がついていたと思いますが,忘れてしまいました.岩波のアルゴリズムとデータ構造の本に書いてあったと思うのですが... n1 のみを比べてソートしようとするなら,マージソートのようにその性質をもった別のソートアルゴリズムを使えばよいと思います.

noname#25358
質問者

お礼

 ありがとうございます。  ためしにクイックソートでロジックを組んでみたところ、見事にプログラムがハングりまして、けっきょくヒープソートでやるしかなさそうです(^_^;  もともと高校が職業高校だった関係上、数学でそういう勉強を一切してないので、中学生並みの知識で理解できる方法しか使えないのです(笑) ヒープソートはインターネットに落ちていたからよかったのですが(^_^;  やはりヒープソートでは無理でしょうかね。

関連するQ&A

  • シェルソートの順位性

     このカテゴリーのNo.137(#35189)の続きなのですが、シェルソートについてご存知の方お願いします。  上記の質問にて、ヒープソートは完全二分割木型で、同一の値であってもその順序は保証されない、ということがわかりました。  そこで、配列の内容をソートする処理をシェルソートで組んでみました。  やろうとしているのは、n1、n2 の2つの配列に値を入れ、n1 が同じ値だったら n2 の値を使ってソートする、という処理です。  しかし実際には、n3、n4と無制限に続く2次元配列なので各配列を個別にソートしなければならず、n2 を先にソートしてから n1 をソートする、という処理を入れています。  ところがこれだと、n1 のソート時に同一の値の順序が崩れると、せっかく行った n2 のソートが無駄になってしまいます。  シェルソートの場合、こういうことは起こるのでしょうか。  よろしくお願いします。 

  • 配列のソートがしたい

    sort関数等調べたのですがうまくできません。 やりたいことは http://q.hatena.ne.jp/1155090363 ↑で見つけた事とそっくりなのですが・・・。 ------------------------------------------- arrItem[n] という配列の一つの要素の中に、 タブで区切られた10個程のデータが入っています。 arrItem[0] = "5 ^ 店名5 ^ 品名5 ^ 価格5 ^ 割引額5 ^・・・^ 備考5" arrItem[1] = "2 ^ 店名2 ^ 品名2 ^ 価格2 ^ 割引額2 ^・・・^ 備考2" arrItem[2] = "11 ^ 店名9 ^ 品名9 ^ 価格9 ^ 割引額9 ^・・・^ 備考9" 一列目はSEQ番号でユニークですが、順番が並んでいません。 この配列をSEQ番号で並べ替えたいのですが、 sortだと文字列比較のためか桁数の違う数字の並べ替えが 上手くできません。数値としてのソート方法 が分かる方いらっしゃいましたらご教授願います。 もし可能なら、1列目を数値降順にしたり昇順にしたり、 また2列目を五十音順にソートしたり、 また4列目を価格の安い順にソートしたり と応用も可能ならばご教授願いたいです。 宜しくお願い致します。

  • クイックソートについて

    下記のソースプログラムのquick_sort_coreの部分がわかりません。 わかる方助けてください。 あとこのソースを降順にした場合の変更点も教えていただけると助かります。 #include <stdio.h> /* printf()利用のため */ #include <stdlib.h> /* rand()利用のため */ #include <time.h> /* clock()利用のため */ #define N 10 /* 整列対象要素数 */ /** * 配列の中身を表示する関数 * @param a 表示する配列 * @param n 配列の要素数 */ void print_array(const int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } /** * 整列されているかどうか確認する関数 * @param a 確認対象配列 * @param n 配列の要素数 */ void is_sorted(const int a[], int n) { int i; for (i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { printf("昇順に整列されていません\n"); return; } } printf("昇順に整列されています\n"); } /** * クイックソートの本体 * @param a 整列対象配列 * @param l 対象の最初の要素番号 * @param r 対象の最後の要素番号 */ void quick_sort_core(int a[], int l, int r) { /* ここを実装する */ } /** * これまでの整列関数のインターフェースにあわせるクイックソート呼び出し関数 * @param a 整列対象配列 * @param n 配列の要素数 */ void quick_sort(int a[], int n) { quick_sort_core(a, 0, n - 1); } int main(void) { int i; int n = N; /* 整列対象要素数 */ int a[N]; clock_t start,end; /* 0からRAND_MAXの一様乱数をn個生成し、配列aに格納 */ for (i = 0; i < n; i++) { a[i] = rand(); /* 出力確認(print_array)するときは a[i]=rand()%100 としておくと見やすい */ } /* 昇順にソートされているか確認(デバッグ用) */ is_sorted(a, n); /* 配列の中身を確認(デバッグ用) */ print_array(a, n); /* 開始時刻の取得 */ start = clock(); /* クイックソート関数の呼び出し */ quick_sort(a, n); /* 終了時刻の取得 */ end = clock(); /* 配列の中身を確認(デバッグ用) */ print_array(a, n); /* 昇順にソートされているか確認(デバッグ用) */ is_sorted(a, n); /* 実行時間の表示 */ printf("%d 個の要素のクイックソートの実行に %f [秒]かかりました\n", n, (double)(end - start) / CLOCKS_PER_SEC); return 0; }

  • qsort/クイックソートについて

    構造体の配列をqsortで昇順に並び替えるプログラムを作成しています。 対象は数値項目で、単純にNo順に並び替えるイメージです。 クイックソートは、配列の内容によって処理時間が変わると聞いたので、一番遅くなる場合の時間を調べたいのですが、どのような並びだと一番遅くなるのでしょうか?

  • 【JavaScript配列のソート】2つのキーで

    JavaScriptのsort()を使用して次の並べ替えをしたいと思っています。 key1, key2, data, data 5/5 , 5/4 , リンゴ, 110 5/3 , 5/6 , バナナ, 130 5/7 , 5/2 , ミカン, 110 5/3 , 5/2 , イチゴ, 150 この配列をkey1を昇順でかつkey2も昇順とし並び変えたいのです。 key1, key2, data, data 5/3 , 5/2 , イチゴ, 150 5/3 , 5/6 , バナナ, 130 5/5 , 5/4 , リンゴ, 110 5/7 , 5/2 , ミカン, 110 str.sort(); これだとkey1のみでソートされてしまいますので、条件を複数指定したいのですがいい方法はないでしょうか? 結果はweb(テーブル等)に表示するのではなく、配列変数のままで獲得したいと思っています。 google apps のスプレッドシート内でスクリプトとして使用したいと思っています。 かなり調べたのですがどれも1項目(key1)のみの検索しかヒットしませんでした。 よろしくお願いします。

  • 多次元配列のソートについて

    名前とテストの点, クラスが格納されている 以下のような多次元配列があるとします。 $data[0][0] = 'yamada'; $data[0][1] = '20'; $data[0][2] = 'B'; $data[1][0] = 'katoh'; $data[1][1] = '45'; $data[1][2] = 'A'; $data[2][0] = 'honda'; $data[2][1] = '15'; $data[2][2] = 'E'; $data[3][0] = 'ooyama'; $data[3][1] = '100'; $data[3][2] = 'C'; 上記の配列を得点順にソートして表示したいのですが どのようにすればうまく(昇順、降順)で表示できるのでしょうか?

    • 締切済み
    • PHP
  • バブルソートの実行時間について

    バブルソートで降順、ランダム順に並んでいるデータを読み込ませて昇順に並び替える実行時間について質問です。 バブルソートにおける計算時間は、データ数が多いほど、並び替える回数が多いほど長くなるはずですが、実際に実行したところ、並び替える回数が多いはずの降順のほうがランダム順よりも早くなりました。 なぜこのようになるのですか? よろしくお願いします。

  • STLのlist どのデータでソートするか分からないデータでソートを行うには?

    class data { public: 文字列型* str; //コンストラクタでN個の配列を生成 int N; //文字列の配列の個数 }; list<data> obj; と書いて、objに対して大量にデータを追加した後、その要素をソートするところで困っています。 データを文字列型のデータの配列の特定のオブジェクトを使ってソートするのに、その方法が見つかりません。 リストのデータの一つ目 str[0] = "abc"; str[1] = "def"; リストのデータの二つ目 str[0] = "ghi"; str[1] = "jkl"; というリストのデータがあったときに、str[0]の要素でソートしたいということなのですが........ メンバのint型などについては、operator<をオーバーロードする方法が見つかったのですが........

  • バブルソートを入れたいのですが

    こんにちは、Perlを始めたばかりの初心者です。 さっそく質問の方失礼します。 乱数1~100までの数字のうち20個をとりだし配列にいれ、数字を昇順に入れ替えして昇順前と昇順後の数字を表示する問題なのですが。 @a[100]=(1..100); srand(time()); for($i=0 ; $i<20 ; $i++){ $a=int(rand(@a)); print"$a\n"; } と上記の乱数20個を取り出すことができたのですが、 そのあとの昇順させようとしてバブルソートを利用したいのですが、どのように組み込めばいいかわかりません。 どのように組み込めばいいのでしょうか? お答えの方ヨロシクお願いします。

    • ベストアンサー
    • Perl
  • 変数の中の数字をforで指定したい。

    変数の中の数字をforで指定したい。 配列として、 $sort1[$t] $sort2[$t] ... $sort10[$t] と1~10と添え字をつけた変数を扱うときにfor等の繰り返し関数を使って利用したいのですが、旨く行きません。 for ($n=1; $n<=10; $n++){ $hensuu = '$sort' . $n . '[$t]'; echo $hensuu; } となどとして、$sort1[$t]、$sort2[$t]・・・に入っているデータを表示したいのですが、表示されるのは、 $sort1[$t] $sort2[$t] ・・・ となります。 どうすれば、この変数に入っている値を表示できるのでしょう? この例では10個までしか無いので、forを使わずに全部書いてしまえば良いのですが… 沢山あるときに、シンプルに処理できると助かります。 よろしくお願いします。

    • ベストアンサー
    • PHP