ソート#1 バブルソート 駆け出しエンジニアのプログラミング講座【C#】

C#プログラミングのアルゴリズム講座をしていきます!

慣れないうちは、あまり頭に入ってこなくて楽しくないかもしれませんので、無理せず学んでいきましょう。

第1回目は、アルゴリズムの中では比較的優しい基礎的なソート「バブルソート」について考えていきたいと思います。

メモ

使う言語:C#

エディター:Visual Studio 2019

 

バブルソートとは

バブルソートとは、隣り合う値で順番が崩れているものを入れ替えることによってソートする手法です。

値が泡のように徐々に上がっていくので「バブル」ソートと呼ばれています。

言葉だけの説明だけではイメージが沸かないと思うので、図で見ていきましょう。

この配列で考えてみましょう。目指すのは左が小さく、右に行くにつれて大きくなる配列です。

 

それでは、まず左から2つの数字⑤と➀を取って比べます。

この場合、5>1と左側の5の方が1より大きいので両者の順番を入れ替えます。

となります。次に先ほどひっくり返した⑤と➃を比べます。5>4と5の方が大きいのでまた両者をひっくり返します。

同じように⑤を取って次の数字と比べていきます。

このように⑤が泡のように上がっていきます。今のままではソートし切れていないので、また先頭から比べていきます。

 

➀と➃を比べると1<4と大小関係が成立しているので変更はありません。

 

次に➃と➁を比較します。左の➃の方が大きいのでひっくり返します

 

4>3も➃の方が大きいので入れ替えます。

 

これで順番通りにソートが完了です。

 

バブルソートのコード

バブルコードの理論が分かったところで、これをコードに落とし込んでいきましょう。

public int[] bubblesort(int[] x){
    //配列が空だったら、空の配列を返す。
    if( null == x ) return x;
    //配列の長さを変数に入れる。
    int  n = x.Length;

    //配列の長さ分ループさせる。
    for(int i = n; i > 0; --i){
        for(int j = 1; j < i; ++j){

            //x[j-1]が比べる数字の左側、x[j]が右の数字
            //左の数字が右より大きかったら、Ifの中の処理へ
            if( x[j-1] > x[j] ){
                //仮に、tに左の数字を代入しておく
                int t = x[j-1];
                //左の数字の場所に、右の数字を入れる
                x[j-1] = x[j];
                //右の数字の場所に、仮置きしていた左の数字を入れる
                x[j] = t;
             }
         }
     }//loop end

     //入れ替えた配列を返す。
     return x;
}

次にこのメソッドを実際に使ってみましょう。

// まずサンプルの配列を作成
int[] test = new int[5] { 5, 1, 2, 4, 3 };
// 上記で作成したメソッドを使います。
test = bubblesort(test);

これで、testの配列は[1,2,3,4,5]の順番にソートされました。

  • B!