• 締切済み

C言語、ソートの効率を考える問題について

繰り返しソートとバブルソート、改良バブルソートの中でどれが一番効率的であるかを理論的な比較回数やプログラムの量、使用するメモリの量から考えたいんですけどわかりません。教えてください。

みんなの回答

回答No.2

カウンタ用変数を２つ用意し、 一方はif文が実行されるごとに１UP 一方は、データのコピー(代入）されるごとに１upするようにすればよいのでは？

yt1012
質問者

お礼

ありがとうございます 参考にさせて頂きます

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

まず, 評価すべき値である「比較回数」, 「プログラムの量」や「使用するメモリの量」を定義してください.... 「理論的」はどこまでかかるんだろう? 次に, 比較する 3つのソートのアルゴリズムを書いてください. 最後に, 「あなたがわからないところ」を明確にしてください.

yt1012
質問者

お礼

ありがとうございます そうですね もう一度考えてみます

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • バブルソートとクイックソート

    まだソートについて勉強し始めたばかりですが バブルソートは対象の総数が増えるとそれに伴い比較回数は増加するのに対し クイックソートはそれほど増加しないのはなぜでしょうか？？ 検索してみてもプログラムが書いてあってよくわからないので... 根本的なところなのでしょうがどなたか教えてください!

  • ソートの問題

    ソートの問題なんですが、選択ソートの交換回数はどのような場合も等しくなるんでしょうか??また、バブルソートと挿入ソートの交換回数は等しくなるのか教えてください＞＜

  • ソートアルゴリズム（選択法とバブルソート）の交換回数

    バブルソートと選択法について、交換回数がわかりません。 比較回数については、ネットで検索したり、本に載っているので分かりやすいのですが、交換回数があまり載っていなく…。 選択法の交換回数の最大値は、n-1でしょうか？ バブルソートの交換回数の最大値は、nでしょうか？ 交換回数については、選択法のほうがバブルソートより少なくてすむそうですが、上の答えでいいのかわかりません。 どなたか教えてください。お願いしますm(_ _)m

  • 比較回数が少なくなるソート

    大量にある画像に人間が優劣を判定し、その結果をソートしたいです。（順位を付けたい） 画像はすでにデジタルデータ化されてパソコンの中にあります。 二つの画像を人間に見せて判断を求める事を繰り返すプログラムを作成しようと思うのですが、人間が行う操作（比較の判断）をなるべく少なくする為には、どのようなソートのアルゴリズムを選択したら良いでしょうか？ ソートのアルゴリズムの説明などを読むと、例えば、「バブルソート」及び「選択ソート」ではｎ(ｎ－１)／２の比較が必要になるそうですが、この比較の回数が最も少ない方法を探しています。 また、例えばA,B,Cの比較に置いて、 A＞B、B＞Cの比較後にはAとCは比較せずともA＞Cの関係が成り立つのですが、こういった事も考慮した上での比較回数の最も少ないソートの方法が知りたいです。 以上、ご指導のほど、よろしくお願い申し上げます。

  • C言語についての問題です。

    この問題はできるのでしょうか？？ 教えてください。 /*例題*/ 観測回数 3 X座標 X軸方向の流速 34.333 9.762 Y座標 Y軸方向の流速 448.111 -17.032 サイズ サイズの変化量 9.000 2.000 0.000 0.000 3 34.333 9.762 448.111 -17.032 9.000 2.000 0.000 0.000 3 20.615 5.329 688.385 -17.115 13.000 -1.000 0.000 0.000 3 1.200 0.200 1018.667 -17.333 15.000 1.000 0.000 0.000 3 0.375 0.042 1065.000 -17.500 8.000 2.000 0.000 0.000 3 53.750 17.114 22.333 -16.758 12.000 1.000 0.000 0.000 ・ ・ ・ ・ ・ 2 2014.273 -0.352 1233.727 17.727 11.000 3.000 0.000 0.000 2 2014.000 -0.625 1282.500 17.500 12.000 4.000 0.000 0.000 1 22.088 19.302 3.971 -20.493 34.000 6.000 0.000 0.000 1 19.636 16.812 122.909 -17.326 11.000 -6.000 0.000 0.000 のデータが6000個あります。 まず観測回数で昇順にソートして、その昇順に表示したものを x軸方向の流速 ＋ ｙ軸方向の流速 で昇順にソートして並べて表示する問題です。 x座標、y座標、サイズ、サイズの変化量は今ないものとします。 良ければプログラムおしえていただきたいのですが？？

  • ソートプログラムで

    １．２つの配列a、bをマージする場合、比較回数が最大となる必要十分条件、最小となる必要十分条件 ２．マージソートプログラムと選択ソートプログラムの比較回数について、要素数をｎとしたときに、比較回数をｎで表す にはどうしたらよいですか？初心者なので全然わかりません。教えてください。

  • 実行計画の「メモリを使用したソート回数」と「ディスクを使用したソート回

    実行計画の「メモリを使用したソート回数」と「ディスクを使用したソート回数」は なにによって変わってくるのでしょうか？ メモリの容量におさまる程度のソートでしたら「メモリを使用したソート回数」で メモリにおさまらないくらいの大量データのソートならば「ディスクを使用したソート回数」と いうことでしょうか？

  • バブル・ソート、クイック・ソート

    N個（N=4,5,6）のデータが全て等しいデータ列（例えばN個の数字全部が1のとき）をバブルソートで並び替えたとき、データの交換回数は何回か。また、同じデータ列をクイックソートで並び替えたときはどうか。 という問題があるのですが、どう比較するのかがわかりません。詳しい方、説明よろしくお願いします。

  • Ｃ言語　ソートについて

    #include <stdio.h> #include <stdbool.h> #define NUM_ARRAY 4 #define NUM_DATA 5 int count_swap = 0; // 交換回数 int count_comparison = 0; // 比較回数 void selection_sort(int a[], int n) { } int main(void) { int data[NUM_ARRAY][NUM_DATA] = {{9, 7, 5, 6, 8}, {9, 8, 7, 6, 5}, {5, 6, 7, 8, 9}, {5, 6, 8, 7, 9}}; for (int i = 0; i < NUM_ARRAY; i++) { count_swap = 0; count_comparison = 0; int d[NUM_DATA]; copy_array(data[i], d, NUM_DATA); // 配列のコピー printf("----------------\n"); print_array(d, NUM_DATA); // ソート前の配列の表示 selection_sort(d, NUM_DATA); // 挿入ソートの実行 print_array(d, NUM_DATA); // ソート後の配列の表示 printf("比較回数: %d\n", count_comparison); // 比較回数の表示 printf("交換回数: %d\n", count_swap); // 交換回数の表示 } } 上の雛形を使って選択ソートを実行するという問題なのですが途中までそれっぽいのは出来たのですが上手くいかないので解答をお願いします。 下に自分が今書いているものを置いておきます。 #include <stdbool.h> #include <stdio.h> #define NUM_ARRAY 4 #define NUM_DATA 5 int count_swap = 0; int count_comparison = 0; void swap(int d[], int i, int j) { count_swap += 1; printf("swap a[%d] = %d, a[%d] = %d\n", i, d[i], j, d[j]); int temp = d[i]; d[i] = d[j]; d[j] = temp; } void copy_array(int *a, int *b, int n) { for (int i = 0; i < n; i++) { b[i] = a[i]; } } void print_array(int d[], int n) { for (int i = 0; i < n; i++) { printf("%d ", d[i]); } printf("\n"); } bool compare(int d[], int i, int j) { count_comparison += 1; printf("compare a[%d] = %d, a[%d] = %d\n", i, d[i], j, d[j]); if (d[i] > d[j]) { return true; } else { return false; } } void selection_sort(int d[], int n) { int min; for (int i = 0; i < n - 1; i++) { min = i; for (int j = i + 1; j < i; j++) { if (compare(d, min, j)) { min = j; } } swap(d, i, min); print_array(d, n); } } int main(void) { int data[NUM_ARRAY][NUM_DATA] = { {9, 7, 5, 6, 8}, {9, 8, 7, 6, 5}, {5, 6, 7, 8, 9}, {5, 6, 8, 7, 9}}; for (int i = 0; i < NUM_ARRAY; i++) { count_swap = 0; count_comparison = 0; int d[NUM_DATA]; copy_array(data[i], d, NUM_DATA); // 配列のコピー printf("----------------\n"); print_array(d, NUM_DATA); // ソート前の配列の表⽰ selection_sort(d, NUM_DATA); // 挿⼊ソートの実⾏ print_array(d, NUM_DATA); // ソート後の配列の表⽰ printf("⽐較回数: %d\n", count_comparison); // ⽐較回数の表⽰ printf("交換回数: %d\n", count_swap); // 交換回数の表⽰ } }

  • ソートについて

    今、色々なソートのプログラムを作っているのですが、 ソートにおいて、実行速度と実行時の使用メモリ、どちらを重要視しますか?

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する