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

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

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

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

バブルソートとは

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

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

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

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

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

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

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

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

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

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

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

４＞３も➃の方が大きいので入れ替えます。

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

バブルソートのコード

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

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[ｊ]が右の数字
            //左の数字が右より大きかったら、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]の順番にソートされました。