- ベストアンサー
挿入ソートの性能評価
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
>もう少し詳しく 一瞬、とても不可能なことに思われましたが、チャレンジしてみます＾＾； 普通のプログラム言語では、 処理Ａ 処理Ｂ 処理Ｃ のように進んでいきます。 ココで 処理Ｂが何回行われるか調べたい時には、 処理Ａと処理Ｂの間にカウントする処理を加えます 処理Ａ （処理Ｂの）カウント処理 処理Ｂ 処理Ｃ 処理Ａの後、処理Ｂが実行されるのは、逐次実行型のプログラムではそのように期待できるので、処理Ｂの前にある変数を＋１する処理を書けば、処理Ｂが何回実行されたかカウントすることができます。 int counter=0; の様に初期化しておいて counter++; とするか counter+=1; とするか counter=counter+1; とします。 処理Ｂが比較であっても要素交換であっても同じことですが、 比較の場合は比較の直前、要素交換の場合は要素交換の直前でカウントすればよいです
その他の回答 (2)
- BLUEPIXY
- ベストアンサー率50% (3003/5914)
int cmpCount=0; int swapCount=0; とかしといて、 cmpCount++; if(要素の比較）{ swapCount++; //交換の処理 } みたいな感じで、比較する間に比較回数のカウンタを＋１して 交換する前に交換回数のカウンタを＋１すればいいのでは
- Bonjin
- ベストアンサー率43% (418/971)
＞要素比較回数と要素交換回数を数える なのですから、比較した時と交換した時にそれぞれをカウントアップするだけで良いのではないでしょうか？ ＞うまくいきません 何がどううまくいかないのか書かないと的確なアドバイスは得られませんよ
お礼
回答ありがとうございます。 実は授業についていけておらず、一から参考書を読み直しているレベルです。 配列についてはそこそこ理解しており、挿入ソートを実現したプログラム自体は参考例として与えられているのですが、Bonjinさんがおっしゃっているカウントアップの方法がよくわかりません。 カウントアップの方法をご教授していただければ幸いです。
関連するQ&A
- 単純挿入ソートについて
単純挿入ソートの『選択』、『交換』、『挿入』の回数を出力せよ。という課題が出されたのですが意味がよくわかりません。ちなみに課題前に次のような説明をされました。 『選択』は交換と挿入を行うため、キー値等の比較を行う判定処理 『交換』は選択の結果、2つのキー値の並び替え処理 『挿入』は選択の結果、キー値を決められた並び順の位置に格納する処理 また、『選択』を『比較』、『交換』と『挿入』を合わせて『交換』と言う事もある。 作ったプログラムはこれです。かなり違う気がするので指摘よろしくお願いします。 void insertion(int a[], int n) /* a[]:ソート対象データが格納されている配列 n:データの個数 */ { int i,j; int tmp; int count[3]; /* 配列番号 選択:0 交換:1 挿入:2 */ for(i=1;i<n;i++) { tmp=a[i]; count[1]++; /* 交換カウント */ for(j=i;(j>0)&&(a[j-1]>tmp);j--,count[0]+=2) /* 選択カウント */ { a[j]=a[j-1]; count[1]++; /* 交換カウント */ } if(j > 0) /* 選択カウント */ count[0]+=2; else count[0]++; a[j]=tmp; count[2]++; /* 挿入カウント */ } printf("選択の回数 : %4d\n", count[0]); printf("交換の回数 : %4d\n", count[1]); printf("挿入の回数 : %4d\n\n", count[2]); } テストデータ 60 57 54 51 48 45 42 39 36 33 30 27 24 21 18 15 12 9 6 3 実行結果 選択の回数 : 399 交換の回数 : 209 挿入の回数 : 19
- ベストアンサー
- C・C++・C#
- 単純挿入ソート法の要素の比較回数についての問題
単純挿入ソート法の要素の比較回数、移動回数についての問題 『単純挿入ソート法は、シャトルソート法とも呼ばれ、挿入とシフトを用いるソートである。 下図（添付図）はこのソート法の１ステップを示している。 配列a[0],…,a[n-1]があって、a[i]より前の部分がソートされている。 ここで、a[i]の値をwとする。 a[0],…,a[i-1]の 部分で、w が入るべき位置を探す。 この位置をj とする。配列の範囲 a[j],…,a[j-1]をa[j+1],…,a[i] ヘシフト する。最後に、wをa[j]に格納する。 このような操作を、最後まで繰り返す。 以下の問に答えよ。 問(1)～(3) 省略 問(4)単純挿入ソート法で要素の比較回数のオーダーを答えなさい。ただし、配列の要素数を n とする。 問(5)単純挿入ソート法で要素の移動回数のオーダーを答えなさい。ただし、 配列の要素数を n とする。』 問(1)～(3)は単純挿入ソート法で配列を昇順にソートするC言語で記述されたプログラムに関する問題なのですがそちらは解けました。 問(4)は比較回数のオーダーを S とすると、最悪の場合 n(n-1)/2 回 比較を行う必要があるので、S=n(n-1)/2 問(5)は移動回数のオーダーを T とすると、最悪の場合 n(n-1)/2 回 移動を行う必要があるので、T=n(n-1)/2 と考えているのですが自信がありません。 そもそもここで問われているオーダーとは回数のことをいってるのか、そうではないのかが分かりません。 どなたか説明していただけますと大変助かります。解答以外にもこの問題に関連することに対してのアドバイスなどがありましたら答えてくださると嬉しいです。 時間がなくて少し焦っています。どうか何卒よろしくお願いします。
- 締切済み
- C・C++・C#
- ソート（乱数・比較・交換・時間）
ソート（コームソート）について色々と実験をして確めてみようと思っています。 乱数を５００、１０００、１５００個ずつで、山型、逆ソートなどでで発生させて、さらに比較回数・交換回数・時間を計りたいのですが、プログラムが出来るようでなかなかうまくいきません。 どのようにつくればいいのでしょうか？ また、参考になるホームページがあれば教えていただければありがたいです。
- ベストアンサー
- C・C++・C#
- バブルソートとクイックソート
まだソートについて勉強し始めたばかりですが バブルソートは対象の総数が増えるとそれに伴い比較回数は増加するのに対し クイックソートはそれほど増加しないのはなぜでしょうか？？ 検索してみてもプログラムが書いてあってよくわからないので... 根本的なところなのでしょうがどなたか教えてください!
- ベストアンサー
- C・C++・C#
- クイックソートで並べ替え
友人から情報処理の質問を受けました。ですが、私では良く分からなかったので質問します。 2,4,8,1,6,5,2,7,3,7の整数をクイックソートで並べ替えよ。 また、比較回数を示せ（軸要素は先頭の2要素のうち大きいほうとせよ）。 よろしくお願いします。
- 締切済み
- C・C++・C#
- modified bubble sort
ソーティングについて教えてください． ソーティングの手法に，バブルソートというものがあります(隣接するふたつを入れ替える)．このソーティングでは，最大交換回数は要素数が n のとき， n(n-1)/2 となります． 隣接する要素の交換に加え，先頭と最後の要素の入れ替えも可能だとすると(イメージとしては，サイクリックなバブルソートです)，最大交換回数は n^2/4 となるそうです． この n^2/4 になる，という理由が分かりません(普通のバブルソートが n(n-1)/2 になるのは理解できます)．どなたかご教授頂ければと思います．
- 締切済み
- 数学・算数
- ソートアルゴリズム（選択法とバブルソート）の交換回数
バブルソートと選択法について、交換回数がわかりません。 比較回数については、ネットで検索したり、本に載っているので分かりやすいのですが、交換回数があまり載っていなく…。 選択法の交換回数の最大値は、n-1でしょうか？ バブルソートの交換回数の最大値は、nでしょうか？ 交換回数については、選択法のほうがバブルソートより少なくてすむそうですが、上の答えでいいのかわかりません。 どなたか教えてください。お願いしますm(_ _)m
- 締切済み
- その他([技術者向] コンピューター)
お礼
回答ありがとうございます。 もしよろしければもう少し詳しく教えていただけないでしょうか。お願いします。