単純挿入ソートについて

質問

単純挿入ソートの『選択』、『交換』、『挿入』の回数を出力せよ。という課題が出されたのですが意味がよくわかりません。ちなみに課題前に次のような説明をされました。

『選択』は交換と挿入を行うため、キー値等の比較を行う判定処理
『交換』は選択の結果、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

回答No.3

sakusaker7 · ベストアンサー

まず、変数の初期化は忘れずにしましょう。具体的には配列 countです。
デバッグバージョンだったりすると正常に動くように見えるかもしれませんが、ごみが入っていると回数がめちゃくちゃになります。
しかし、この例の場合それぞれのカウントは独立した変数で行ったほうが意味的にもわかりやすくなると思うのですがなにか理由があったのでしょうか?

次に、この例題だと最悪のケースの回数を計測しているようですが、
その場合の比較回数は 0+1+2+3+..17+18+19 つまり
n * (n -1) / 2 となるはずなので、実行結果は間違っています。

交換回数を、挿入場所を空けるために行った移動の回数とすれば
同じく最悪のケースで
要素が一つ→ 0回
要素が二つ→ 1回
要素が三つ→ 2回 ・・・
で同じく n * (n - 1)/2 となるはずです。

挿入の回数はあってますね。

選択の回数はすなわち、a[j-1] > tmp で比較を行った回数ですから、for文のインクリメント式で数えると数え間違います(なぜかは宿題)。
そもそも +2 していくのが意味不明なんですがなぜですか?

お礼

回答、ありがとうございます。

>選択の回数はすなわち、a[j-1] > tmp で比較を行った回数ですから、for文のインクリメント式で数えると数え間違います
1回目のfor文実行時、カウントされないからですよね？

>そもそも +2 していくのが意味不明なんですがなぜですか?
補足に書きましたが、番兵を用いたプログラムと比較するために
for文の j>0 と a[j-1]>tmp を別々にカウントする必要があるからです。
説明不足ですみませんでした。

補足

この問題には続き（2問目）があってその問題というのが番兵を用いたプログラムに書き換え、最初のプログラムと選択、交換、比較回数を比べよ。という問題です。

回答No.4

sakusaker7

なるほど j > 0 と a[j-1] > tmp をそれぞれ一回としてカウントするということですか。
しかし、その場合でも j > 0 は配列の添え字をオーバーランしていないかどうかの
チェックですから、ソートアルゴリズムで考えるところの回数の勘定には入らないような気がするのですが。
両者の合計が必要であるとしても、別個に数えて後で合算するほうが理解しやすいと思います。

でほとんど答えになっちゃいますが、番兵を置くことで変わるのは
選択要素の挿入場所を探すために配列を走査するときに添え字の
オーバーランが起きないかどうかをチェックしないですむということで、
そのほかの比較や選択には影響しません。

お礼

>チェックですから、ソートアルゴリズムで考えるところの回数の勘定には入らないような気がするのですが。
>両者の合計が必要であるとしても、別個に数えて後で合算するほうが理解しやすいと思います。
私もそう思います。課題なので2つの処理をまとめてカウントしましたが・・・。

最初のプログラムも番兵を用いたプログラムも作ることができました。回答された方、ありがとうございました。

回答No.2

mizuneko

逆順に並んでいる"最悪"のデータを
提示していることからみて、おそらく問題の趣旨としては、

選択の回数:n*(n-1)/2
交換の回数:n*(n-1)/2
挿入の回数:n-1

と出力させたいのではないかと思います。

選択の回数:190
交換の回数:190
挿入の回数:19

でしょう。

お礼

回答ありがとうございます。

交換の回数:n*(n-1)/2は単純挿入法のオーダーですよね？
交換の回数は190になったんですど、他の2つがまだうまくいきません。もうちょっと頑張ってみます

回答No.1

agricap

何とも曖昧な課題でいろいろな解釈ができそうですが・・・私ならこう解釈する、
という程度でとらえてください。ちゃんとした説明ができれば、いろいろな答え
があるようにも思えます。

全体として、「Ｃ言語」を実行過程における回数を数えているように見えますが、
考えすぎではないでしょうか。純粋に配列の動きだけを追う、と考えるのが
妥当だと思います。
多分そこまでは求めていません。

・最初の「count[1]++」は不要ではないでしょうか。
　これはなぜ必要と考えましたか？
　for文の中が１回も実行されない場合は、a[i]の値はそのまま動かないのだ
　から、選択は０回と考えるべきと思います。
　「tmp=a[i]」と「a[j]=tmp」も交換１回とカウントしていますか？

・for の中の、「count[0]+=2」は、「count[0]++」でいいでしょう。
　for を抜けた後の、if の場合分けは不要でしょう。一律、「count[0]++」で
　いいと思います。
　forループの中の j>0 も１回の選択、と数えているように見えますが、考えす
　ぎだと思います。

・最後の「count[2]++」のところは、「if (j<i)」という条件をつけた方がいい
　と思います。j=i ならば、a[i]の位置はそのままだから、挿入が発生しなかっ
　た、という解釈が妥当ではないでしょうか。

お礼

回答ありがとうございます。

>最初の「count[1]++」は不要ではないでしょうか。
そうですね。よく考えたらいらないことに気がつきました。

>for の中の、「count[0]+=2」は、「count[0]++」でいいでしょう。
これは番兵を用いた単純挿入ソートの選択回数を比較するために必要みたいです。

>最後の「count[2]++」のところは、「if (j<i)」という条件をつけた方がいい
>と思います。j=i ならば、a[i]の位置はそのままだから、挿入が発生しなかっ
>た、という解釈が妥当ではないでしょうか。
ここの部分直したら、挿入回数が正常になりました。ありがとうございます。