入力した数字を小さい順に並び変えるプログラミング

Question

C言語のプログラミングで、
入力した数字を小さい順に並び変えるプログラミングを組んだのですが、
実行した結果
3 23 25 21 8 6 21 85 99 189
となり中途半端に小さい順になりません。
do のあとにflag=0とするとうまくいくのですが、
どうしてelseで入力するとうまくいかないのでしょうか

#include <stdio.h>

#define N 10 /*要素の数*/

int main(void)
{
  int a[N]={3,85,23,189,25,21,8,6,21,99};
  int i,tmp, flag;

  do
    {
      for(i=0; i<N-1 ; i++)
	{
	  if(a[i]>a[i+1])
	    {
	  tmp=a[i];/*値の交換*/
	  a[i]=a[i+1];
	  a[i+1]=tmp;
	  flag=1;
	}
	  else
	    {
	      flag=0;
	    }
    }
      
}while(flag==1);

for(i=0; i<N; i++)
  {
    printf("%d   ",a[i]);/*結果出力*/
  }

 printf("\n");
return 0;
}

Answer 1

よくわからないときはデバッグしましょう。想定と違うことがわかるはずです。
for文の最下行に以下を付与してもいいでしょう。

printf("%d flag: %d\n", i, flag);

このソートプログラムのアルゴリズムは、本来

• 配列の要素を先頭から順に次の要素と大小を比較、次の要素のほうが方が小さければ次の要素と値を入れ替えflagをたてる。
• 配列をN-1までチェックし、flagが立っていれば(入れ替えが一度で発生していれば)再度配列の始めの要素からチェックする
• (今回のチェックで入れ替え要素がないのに、入れ替えがあったことになってしまうため)再チェックす際は、前回立てたフラグをまず初期化する
  ではないでしょうか？
  flagに関して言えば、一度でも入れ替えがあればwhileの判定までflagを1のままにしておく です。

今の実装は

• リスト「配列の要素を先頭から順に次の要素と大小を比較、次の要素のほうが方が小さければ次の要素と値を入れ替えflagをたてる。」
• リスト「配列の要素を先頭から順に次の要素と大小を比較、次の要素と同じか次の要素の方が大きければflagをおろす(0にする)」
  これだと入れ替えが一度でも発生したか否かに関わらず、flagには配列の最後の比較n-2とn-1番目の比較の結果が反映されるだけです。
  その為、入れ替えが発生しているにも関わらずwhileループが終了してしまう場合が発生してしまいます。

想定通りでないときは、

1. 本来のあるべき想定は何かを整理する。
2. その想定が正しいことを確認する。
3. その想定が問題なく実装されているかチェックしてみる
   といいと思います。

Comments

[sora1111]

初学者の自分にもわかるように詳しく教えていただきありがとうございました