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

ソートアルゴリズム(バブルソート)

今回はソートアルゴリズムについてちょっとまとめて書こうかなと

 

課題に使うので調べていたのですが、自分で理解するのになんか分かりやすく代表的なのをまとめておこうと思ったのでこの記事を書きます

 

そもそもアルゴリズムとは

アルゴリズム....ある問題を解決するための解法

 

コンピュータ関連でいうとある処理を行うときの適切な処理の仕方

データが大きいとか条件によって条件にあったアルゴリズムを用いることで高速な処理にできる

 

今回ピックアップするのはソートアルゴリズムの一つのバブルソートです

 

  バブルソート

        基本の動作

        バブルソートは隣にあるデータと比較、入れ替えをするソートのアルゴリズム

       繰り返し行うことでソートが完了する

       具体的な動き

        例として   24 10 14 71 1 96 67 30 90 31をソートしてみます

    

         1回目

         1  24  10  14  71  30  96  67  31  90

         2回目

         1  10  24  14  30  71  31  96  67  90

         3回目

         1  10  14  24  30  31  71  67  96  90

         4回目

          1  10  14  24  30  31  67  71  90  96

 

   例からわかるように小さい数字がどんどん下に移っていっているのが分かります

   この動きがバブルソートの動作です

 

       実際のソース

       Cで作成したソース例を載せます

//main関数からソートするデータ配列dataを受け取る

int sort(int data[n]){
  //ソートを行う変数check
  //値を一時的に格納する変数dummy
  //比較が終了したデータの個数を格納する変数fin
  int check=n-1,dummy=0,fin=0;
    while(check!=0){
    //比較が終了したデータまでの間比較
    while(check>fin){
      //data[check]>=data[check-1]の時交換しない
      if(data[check]>=data[check-1]){
        check--;
      //data[check]<data[check-1]の時交換する
      }else{
        //元のデータをdummyに格納
        dummy=data[check];
        //一つ下のデータを上に格納
        data[check]=data[check-1];
        //上のデータを下に格納
        data[check-1]=dummy;
        check--;
      }
    }
    fin++;
  }
  return *data;
}      

 こんな感じです

 

このアルゴリズムの長所と短所

  長所

   処理が見やすい

   移動が少ない場合の処理が高速

  短所

 データが大きくなると処理にかかる時間が長くなる

 最悪処理時間はすべてのデータの入れ替えを行うときの時間になる

 

 

長ったらしくなってしまいました

とりあえず自分が知りたかったことはこんな感じなので今日はこれで 

今後時間を見つけて他のアルゴリズムも調べてまとめてみます

 

-------------------------------参考-----------------------

バブルソート - Wikipedia

バブルソート