C言語の質問です

質問

以下のコードは100個までの数値を受け取り、ソートするプログラムです。

#include <stdio.h>

int main(void)
{
int item[100];
int a, b, t;
int count;

/* 数値を読み込む */
printf("数をいくつ入力しますか？ ");
scanf("%d", &count);
for(a=0; a<count; a++) scanf("%d", &item[a]);

/* ここでバブルソートを使用して数値を整列させる */
for(a=1; a<count; ++a)
for(b=count-1; b>=a; --b) {
/* 隣接する要素を比較する */
if(item[b-1] > item[b]) {
/* 要素を交換する */
t = item[b-1];
item[b-1] = item[b];
item[b] = t;
}
}

/* 整列後のリストを表示する */
for(t=0; t<count; t++) printf("%d ", item[t]);

return 0;
}

バブルソートする部分が分かりません。
比較、交換するコードは分かるのですが…
どなたか詳しく教えていただけないでしょうか？

回答No.3

chie65536 · ベストアンサー

＞バブルソートする部分が分かりません。

for(a=1; a<count; ++a)
の１回目のループでは、aは1です。従って
for(b=count-1; b>=a; --b) {
のbは「最後の要素から、a(つまり1、先頭の１つ手前)になるまで」回ります。

１回目は「最後の要素と、最後の一つ手前の要素を比べ、最後の要素の方が小さいなら前に入れ替え」します。

そして、２回目は「最後の一つ手前の要素と、最後の二つ手前の要素を比べ、最後の一つ手前の要素の方が小さいなら前に入れ替え」します。

最後は「先頭の要素と、先頭の一つ次の要素を比べ、先頭の一つ次の要素の方が小さいなら前に入れ替え」します。

for(b=count-1; b>=a; --b) {
のループが終ると「配列の先頭に、１番小さな値」が来ます。

そして
for(a=1; a<count; ++a)
のループが「aが2になって」繰り返すので「先頭を除外した、２番目から最後まで」で「同じ事」をします。つまり「配列の２番目に、２番目に小さな値」が来ます。

これを「最後の一つ手前と、最後の２個を比べるまで」繰り返すと、すべてがソートされて終了します。

お礼

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

インクリメントがa++、b--ではなく、++a、--bになっているのは
どういう意図があるんでしょうか？
よろしければ教えてください！

回答No.7

chie65536

蛇足ですが。

後置演算子と前置演算子のどっちを使うかで、最も気になるのは「インテル80386系CPUでポインタを使った時」です（つまり、昔で言うDOS/V機、今で言うWindows-PCをターゲットにした時）

インテル80386系CPUは、ストリング操作命令と言う「ストリング操作した後に自動でアドレスを増減する」と言う命令を持っています（ストリング操作命令については、以下のページを参照）
http://hp.vector.co.jp/authors/VA014520/asmhsp/chap6.html

つまり、
　*dst++ = *src++;
や
　*dst-- = *src--;
が、機械語の１命令で済んでしまうのです。

しかし、この機械語命令は「操作した後に自動でアドレスを増減する」のですから「後置演算子」に相当します。言い換えれば「後置演算子だけサポートしている」のです。

つまり「前置演算子を使うと、便利な機械語命令があるのに、それが使われない場合がある」のです（言い換えれば「高速な命令が使われず、実行速度が落ちてしまう場合がある」と言うこと）

ですので、インテル80386系CPUをターゲットにプログラミングする際「前置演算子で書けば判りやすいのに、あえて前処理を追加して、ポインタ操作は後置演算子だけで書く」なんて事をしたりします。

＞今まで(使っている本の勉強している所までで)、後置演算子だったのが、
＞いきなり前置演算子になったんで
上記のような理由もあって「前置演算子は滅多に使わず、後置演算子を頻繁に使う」と言う流れがあります。参考書の書き手もその流れで、殆どを後置演算子で説明してしまっているのでしょうね。

お礼

三度の回答ありがとうございます。勉強になります！
chie65536 さんは"専門家"でも良いような気がするのですが…
また、質問していたら、回答してやってください。
蛇足ぶんも含めて、三度の回答本当にありがとうございました。

回答No.6

chie65536

＞インクリメントがa++、b--ではなく、++a、--bになっているのは
＞どういう意図があるんでしょうか？

「結果は同じ」ですが「無駄なコード生成を省き、最適化しやすくする」意味があります（但し、処理系に依存する）

「++a」と書いた場合、この「式の値」は「インクリメント後のa」になります。
「a++」と書いた場合、この「式の値」は「インクリメント前のa」になります。

ある処理系で「式の計算結果は、０番レジスタに求める」と決められていたと仮定します。

++aは
　inc.l [a]　　;aをlongサイズでインクリメント
　move.l [a],r0　　;インクリメント後のaをr0レジスタにロード
と言うコードが生成されるでしょう（命令コードは、説明用の仮想コード）

a++は
　move.l [a],r0　　;インクリメント前のaをr0レジスタにロード
　inc.l [a]　　;aをlongサイズでインクリメント
と言うコードが生成されるでしょう（命令コードは、説明用の仮想コード）

ここまでは「命令コードの順序が違うだけ」で、速度的に何も変わりません。しかし、この後に「forループの条件比較と分岐」が行われます。

そのコードは、以下のようになるでしょう。
　move.l [a],r0　　;aをr0レジスタにロード
　comp.l [count],r0　　;r0(a)レジスタとcountを比較
　jl forloop1　　;r0(a)が小さければループの最初へジャンプ

これを、先ほどのインクリメント文と並べてみましょう。

++aの場合
　inc.l [a]
　move.l [a],r0
　move.l [a],r0
　comp.l [count],r0
　jl forloop1

a++の場合
　move.l [a],r0
　inc.l [a]
　move.l [a],r0
　comp.l [count],r0
　jl forloop1

お気付きのように、前者の「++a」では、同一の命令コード「move.l [a],r0」が２つ続きます。

コンパイラのオプティマイザ（コード最適化）の性能が低いとしても、(副作用のない)同一の命令コードが２つ続いたなら１つにするくらいはやってくれる筈です。

++aの場合、最終的には、以下のような４命令のコードになります。
　inc.l [a]
　move.l [a],r0
　comp.l [count],r0
　jl forloop1

しかし、a++の場合、オプティマイザの性能が悪いと、以下のように無駄な命令コードが１つ残ります。
　move.l [a],r0
　inc.l [a]
　move.l [a],r0
　comp.l [count],r0
　jl forloop1

このように「熟練したＣプログラマは、生成される機械語コードを予測しながら、複数の記述方法の中から最短最速になるだろう記述を瞬時に選んで、最適なソースコードを書ける」のです。

この「差」は「コンパイルオプションでオプティマイズ（最適化）をオフにしてコンパイルしてみる」と、ハッキリと実行速度の差として表面化します。けっして「書き手の好みの話」だけでは済まないのです。

とは言え、最近のコンパイラのオプティマイザはとても高性能で、命令コードの順序を入れ替えたり、ＣＰＵのパイプラインを考慮したりして「最適コード」を生成するので、プログラマが「どんな機械語コードが生成されるか」を気にする必要が無くなっています。

お礼

丁寧な回答ありがとうございます！
やはり、意図するものがあったんですね！
今まで(使っている本の勉強している所までで)、後置演算子だったのが、
いきなり前置演算子になったんで、おかしいなと思っていたんです！
これで、謎が解けました！安心して次のページに進めそうです！！
回答ほんとうにありがとうございました！

回答No.5

asuncion

> インクリメントがa++、b--ではなく、++a、--bになっているのは
> どういう意図があるんでしょうか？

今回のプログラムでは、どちらでも同じです。
書き手の好みの話でありましょう。

お礼

回答ありがとうございます！
書き手の好みですか…。なぜ、前置演算子を使ったのか疑問でしたけど、
asuncion さんの回答で、気にせずにいこうと思うようになりました。
回答ありがとうございました。

回答No.4

gjgjhono

++a;
と
a++;
の違いですが、以下のような感じです。

< ++aの例 >
int a=0;
int kai=0;

kai = ++a;
printf("a=%d kai=%d",a,kai);
------------------
a=1 kai=1
------------------

< a++の例 >
int a=0;
int kai=0;

kai = a++;
printf("a=%d kai=%d",a,kai);
------------------
a=1 kai=0
------------------

つまり
++が前にあると a=a+1を実行した後にkai=aを実行
++が後にあると kai=aを実行した後にa=a+1を実行
といった感じになります。

上記を参考にされればよいかと思います。

お礼

回答ありがとうございます！！
後置演算子と前置演算子の違いは分かります。
でも、ここで前置演算子を使う意味がわかりません。
for文のインクリメント(デクリメント)部だから、
結局、前置も後置も一緒な気がするのですが…

回答No.2

php504

間違えた
1ループ目
9,2,7,4,0
9,2,7,0,4
9,2,0,7,4
9,0,2,7,4
0,9,2,7,4
2ループ目
0,9,2,7,4
0,9,2,4,7
0,9,2,4,7
0,2,9,4,7
3ループ目
0,2,9,4,7
0,2,9,4,7
0,2,4,9,7
4ループ目
0,2,4,9,7
0,2,4,7,9
終了

お礼

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

隣接する要素を比較して、交換するというのは想像できました。
しかし、バブルソート部分の２つのfor文がなぜそうなるのかわかりません。
また、a++、b--ではなくて++a、--bなのも分かりません。

回答No.1

php504

具体例で雰囲気でも
1ループ目
9,2,7,4,0
9,2,7,0,4
9,2,0,7,4
9,0,2,7,4
0,9,2,7,4
2ループ目
0,9,2,7,4
0,9,2,4,7
0,9,2,4,7
0,2,9,4,7
0,2,9,4,7
3ループ目
0,2,9,4,7
0,2,9,4,7
0,2,4,9,7
0,2,4,9,7
0,2,4,9,7
4ループ目
0,2,4,9,7
0,2,4,7,9
0,2,4,7,9
0,2,4,7,9
0,2,4,7,9
終了