読者です 読者をやめる 読者になる 読者になる

川のブログ

川の適当気ままなブログです。 

頼まれたやつ・・・2/19に向けて

こんにちは川です。お久しぶりです。

今回は頼まれて単純ソートと単純選択法とバブルソートの解説をします。

自分も若干の勘違いをしていたので、自分に教えてもらった人は気を付けてください。

計算量などの説明は今回はしませんのでご了承ください。

全部昇順で出力しています。

単純ソート

 まぁ普通のやつですね。簡単です。

 絵で表すとこんな感じです。

f:id:nakanaka1826:20160217141943p:plain

まず一巡目では、配列の最初の要素を決定させます。

配列の0番目の要素と1番目の要素を見比べ小さかった場合入れ替えます。

次は0番目と2番目、0番目と3番目と比べていきます。0番目と9番目を比べ終わると次は1番目と2番目・・・・・と続けていき、最終的に昇順に並べ変わるといったものですね。

やってみた結果は下にのせています。

 

f:id:nakanaka1826:20160217140235p:plain

ソースコードです。

 

int  i,j,tmp;
int  box={7,5,2,3,9,1,8,10,4,6};
 for(i=0;i<10;i++){
  for(j=i+1;j<10;j++){
   if(box[i]>box[j]){
     tmp=box[i];
     box[i]=box[j];
     box[j]=tmp;
   }
  }
 }

 

単純選択法

 これも見ればわかりますね。簡単です。

 下の絵を見てください。

 

f:id:nakanaka1826:20160217144711p:plain

 まず配列の0番目の要素の値を別の場所で保存しておきます。次にその値と配列の1番目の要素を比べ、小さかった場合、値を小さいほうに更新します。それを2番目、3番目と繰り返します。9番目まで比べた後、別の場所に保存していた値と同じ値が入っている配列の値と0番目の値を入れ替えます。これを1番目、2番目と繰り返し、最終的に入れ替わっているというやつです。

 これは絵を見たほうがわかりやすいです。 

f:id:nakanaka1826:20160217150831p:plain

ソースコードです。

int  tmp,place;
int  box={7,5,2,3,9,1,8,10,4,6};
 for(i=0;i<10;i++){
  tmp=box[i];place=i;
  for(j=i+1;j<10;j++){
   if(tmp>box[j]){
    tmp=box[j];
    place=j;
   }
  }
  tmp=box[i];
  box[i]=box[place];
  box[place]=tmp;
 }

 

バブルソート

 少しややこしいかもしれませんが、簡単です。

 

f:id:nakanaka1826:20160217152216p:plain

 これは前の二つと違い後ろから比べていきます。まず配列の9番目の要素と8番目の要素を比べ前の要素が大きいならば入れ替えます。それを0番目まで調べると、配列の0番目の値が決まります。これを繰り返すと最終的に並べ変わるというやつです。

 

f:id:nakanaka1826:20160217153405p:plain

ソースコードです。

int  tmp;
int  box[]={7,5,2,3,9,1,8,10,4,6};
 for(i=0;i<10;i++){
  for(j=9;j>0+i;j--){
   if(box[j-1]>box[j]){
    tmp=box[j-1];
    box[j-1]=box[j];
    box[j]=tmp;
   }
  }
 }

 

参考サイトを紹介しておきます

単純ソート 

http://lecture.ecc.u-tokyo.ac.jp/~cichiji/cp-05/cp-05-06-2.html

単純選択法

http://www1.cts.ne.jp/~clab/hsample/Sort/Sort3.html

バブルソート 

https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88

 

今回は絵を描くのに時間がかかりましたね。物理の勉強を削った罪として、あとでどら焼きをおごってもらいたいです。