第12講 様々な並び替えの方法
第4話 並び替えその2

結論を言うと、最小値と最大値の両方を対象から除外していく方法はあります。
次のようにすればよいのです。
char ikn,ikx;
for(i=0;i<2;i++){
  for(j=i;j<N-i;j++){
    ikn=Mn(a,i);
    w=a[N-1-i];
    a[N-1-i]=a[ikn];
    a[ikn]=w;
    ikx=Mx(a,i);
    w=a[i];
    a[i]=a[ikx];
    a[ikx]=w;

  
}
}

     

     ・
     ・
char Mx(int* p,int n){
  int i,ik;
  int Max=0;
  for(i=n;i<N-n;i++){
    if(p[i]>Max){
      Max=p[i];
      ik=i;
    }
  }
  textBox6->Text=Max.ToString();
  return(ik);
}

char Mn(int* p,int n){
  int i,ik;
  int Min=100;
  for(i=n;i<N-n;i++){
    if(p[i]<Min){
      Min=p[i];
      ik=i;
    }
  }
  if(n==0)textBox7->Text=Min.ToString();
  return(ik);
}

では皆さん、この方法を適用して

の並び替えを実行してください。並び替えの基準は、合計としましょう。
解答例は、第18講で示します。皆さんかなり大変だと思いますが、是非ご自分の力で挑戦してみましょう。
プログラミングには粘りが必要です。

ここでは、並び替えの2番目の方法を考えます。
例えば、データの並びが
91,4,2,53,92として考えてみましょう。
今回試したい方法は、隣同士を比較して大きい順に並び替えていってそれを繰り返したら並び替えに成功するかです。
2つを比較して大きい方を前にもってくるのです。
では動かしてみましょう。○数字は試行回数です。
1ループ目
@ 91,4,2,53,92 (変更なし)
A 91,4,2,53,92 (変更なし)
B 91,4,53,2,92 (変更あり)
C 91,4,53,92,2 (変更あり)
2ループ目
@ 91,4,53,92,2 (変更なし)
A 91,53,492,2 (変更あり)
B 91,53,92,4,2 (変更あり)
C 91,53,92,4,2 (変更なし)
3ループ目
@ 91,53,92,4,2 (変更なし)
A 91,92,53,4,2 (変更あり)
B 91,92,53,4,2 (変更なし)
C 91,92,53,4,2 (変更なし)
4ループ目
@ 92,91,53,4,2 (変更あり)
A 92,91,534,2 (変更なし)
B 92,9153,2 (変更なし)
C 92,9153,,2 (変更なし)

4ループが終わった段階で並び替えに成功しています。
これはいかなる場合にも成り立つのでしょうか。
また、今回は4ループで終わっていますが、ループ数は常に同じでしょうか。

データを変えて実験してましょう。
データを82,21,16,18,95とすると、
1ループ目
@ 82,21,16,18,95 (変更なし)
A 82,21,16,18,95 (変更なし)
B 82,21,18,16,95 (変更あり)
C 82,21,18,95,16 (変更あり)
2ループ目
@ 82,2118,95,16 (変更なし)
A 82,21,1895,16 (変更なし)
B 82,21,9518,16 (変更あり) 
C 82,21,9518,16 (変更なし)
3ループ目
@ 82,21,9518,16 (変更なし)
A 82,95,2118,16 (変更あり)
B 82,95,2118,16 (変更なし)
C 82,95,21,18,16 (変更なし)
4ループ目
@ 95,82,21,18,16 (変更あり)
ABCは変更なし。
今回も見事に並び変わりました。
しかも、4ループ目は同じです。

事例が2つしかないので偶然かもしれません。
しかし、有力な方法でありそうだという見当は付きました。
後の実験はコンピュータにやらせましょう。
現在の仮説は、『5つのデータであれば4ループで並び替えは終了する』
一般化すれば『n個のデータであれば(n−1)回のループで並び替えは終了する』

では、皆さんプログラミングに挑戦しましょう。

皆さん、プログラミングで大事なことはアイデアなのです。
いくらプログラミング言語の文法に詳しくなっても、アイデアがなければ話になりません。
プログラミングは、真に創造的な取り組みなのです。
もし、私の考えた方法でうまくいった場合は、皆さん独自の方法も考えてみましょう。

第11講第6話へ  第12講第3話へ 第12講第5話へ 第13講第1話へ

vc++講義第1部へ
vb講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座へ