バブルソートで並べ替え

質問

学校でC言語入門をやっています。今回「バブルソート」で配列の要素を降順（大きい順）に並べ替えるということをやっています。
　バブルソートの原理はわかりましたが、書き方がよくわかりません。まず簡単な配列として、a[5]={5,2,24,8,31}　というものを考えています。

　for(k=0;k<n-1;k++){
if(a[k]<a[k+1]){
t=a[k];a[k]=a[k+1];a[k+1]=t;
}
}
とすると、全範囲の中でバブルソートをおこなうので一番小さい"2"が
a[4] に入り、位置の確定ができます。

　今度は確定していない範囲でバブルソートをおこなうと
for(m=0;m<k;m++){
if(a[m]<a[m+1]){
t=a[m];a[m]=a[m+1];a[m+1]=t;
}
}
と先ほどと同様に書け、この中で一番小さい"5"が a[3] に確定します。以下同様に、範囲をせばめていきあと２つ for文を書くと全ての要素の位置が確定することになりますが、これは要素の数が多くなるととても大変なので複数の for文を１つのfor文でまとめたいのですがよくわかりません。

　あと、バブルソートには上と下から(左と右から)の両方から査定する「カクテルシェイカソート」というものもあるらしいのですが、今回は一方向からの査定でやるという指示なのでよろしくお願いします。

回答No.4

noname#48699 · ベストアンサー

No2です。
お尋ねの事とは違いますが、
「補足」欄のソースを見て、まず思ったのは、トップのデータが一番大きい場合、iBasyoが不定の状態で[]内に使われることとなりますね。

お尋ねの
＞何がいけないのかわからない
については、下のソースの全角空白をタブコードに一括変換し、実行してみて下さい。
期待どおりの結果になると、思いますが・・・。

#include <stdio.h>
#define　CNT　7
void　main()
{
　int　iA[CNT] = { 10, 20, 30, 40, 50, 60, 70 };
　int　k, m, iBasyo, iMax, iTemp;

　for( k = 0; k < ( CNT - 1 ); k++ ){

　　iMax = iA[k];

　　iBasyo = -1;　// ★★★「補足」欄では割愛されている★★★

　　for( m = ( k + 1 ); m < CNT; m++ ){

　　　if( iA[m] > iMax ){　// 順位変動あるか

　　　　iBasyo = m;
　　　　iMax = iA[m];　// 暫定
　　　}
　　}
　　if( 0 <= iBasyo ){　// ★★★同上★★★

　　　iTemp = iA[k];
　　　iA[k] = iMax;
　　　iA[iBasyo] = iTemp;
　　}
　}
　for( k = 0; k < CNT; k++ )　printf( "%2d\n", iA[k] );
}
注：タブの代わりに、全角空白を用いています。

お礼

よくわかりました。おかげさまでちゃんと動作しました！
本当にありがとうございました。

回答No.3

noname#48699

No2です。
中程の
　　for( m = k; m < iCnt; m++ ){
は、
　　for( m = ( k + 1 ); m < iCnt; m++ ){
に修正願います。

動作は同じですが、「考え方」が正しく伝わりませんので・・・。
同様に、大外の for文も、
for( k = 0; k < ( iCnt - 1 ); k++ ){
「でもいい」のですが・・・これは、「動作」だけの話で・・ 。

失礼しました。

回答No.2

noname#48699

「ソート」って、「コロンブスの卵」に似たところがあると思います。
知ってしまえば、「な～んだ、簡単じゃん」と言うところが・・・。
でも、けっこうその簡単が「落とし穴」であったりして・・・？？？。
プログラミングの都度、いろんなデータを入れて、検証しましょう。

＞今回は一方向からの査定でやるという指示・・・

No1回答者様が「後ろから」を示されましたので、私は★「前から」・・・。

for( k = 0; k < iCnt; k++ ){ // 「前から査定」し、後から前へ泡を・・

　　iMax = iA[k];
　　iBasyo = -1;

　　for( m = k; m < iCnt; m++ ){

　　　if( iA[m] > iMax ){　// 大小入れ替えあるか

　　　　iBasyo = m;
　　　　iMax = iA[m];　// 暫定の「大」
　　　}
　　}
　　if( 0 <= iBasyo ){　// 「大」確定、入れ替え

　　　iTemp = iA[k];
　　　iA[k] = iMax;
　　　iA[iBasyo] = iTemp;
　　}
}
注：タブの代わりに、全角空白を用いています。

補足

ご回答ありがとうございます。先ほどの配列、a[5]={5,2,24,8,31}　はうまく降順に並べ替えることができました。
　次にやりたいことは、配列に初期値を与えずにデータを読み込み(Ctrlキー + Dを押すまで最大１００個まで)、同様に降順に並べ替えるというものです。初期値を与えたときは正しく出力されますが、教えてくださったものをデータを読み込めるように下のように書くと、一部が正しく表示されず困ってしまいました。

#include<stdio.h>
void main()
{
int a[100],k,m,n,t,iMax,iBasyo;

for(k=0;k<100;k++){

n=k+1;

if(scanf("%d",&a[k])!=EOF)

printf("%2d %2d\n",k+1,a[k]);

else break;
}

printf("\n");

for( k = 0; k < n-1; k++ ){

iMax=a[k];

for( m = k+1; m < n; m++ ){

if( iMax<a[m] ){

iBasyo = m;
iMax = a[m];
}
}

t = a[k];
a[k] = iMax;
a[iBasyo] = t;

}

for(k=0;k<n-1;k++)

printf("%2d %2d\n",k+1,a[k]);

printf("\n");

}

　例えば、10,20,30,40,50,60,70, ctrl+D,の順にデータを入力すると、70,60,50,40,10,20,10 と出力され、"30"と表示されてほしいところに10が出てきてしまいます。
　また、試しに最初の配列　a[5]={5,2,24,8,31}　を入力してみるとうまく表示されました。何がいけないのかわからないのでどうかよろしくお願いします。

回答No.1

php504

forループを2重にすれば出来ます

for (k = n-1; k > 0; k--){
for (m = 0; m < k; m++){
if (a[m] < a[m+1]){
t = a[m]; a[m] = a[m+1]; a[m+1] = t;
}
}
}

お礼

ありがとうございました。ちゃんと動作したので助かりました！わかりやすかったです＿