C言語でバブルソート

概要

普段は主にSwiftの勉強をしていますが、一番最初に触ったC言語を忘れたくないと思い息抜き程度にアルゴリズム初級のバブルソートについて記事を書きます。

バブルソートとは

配列の先頭から最後まで順番にみていって昇順・降順に並び替えるというものです。
今回は昇順ソートです。

実装

コードをみていきましょう。

main.c

# include <stdio.h>
# define LENGTH 7

int main(void){
    
    int array[LENGTH] = { 3, 5, 1, 9, 4, 6, 23};
    int tmp = 0;
    
    printf("before: ");
    for(int i = 0; i < LENGTH; i++) {
        printf("%d ", array[i]);
    }
    
    puts("");
    
    #1
    for(int i = 0; i < LENGTH; i++) {
        for(int j = 0; j < LENGTH; j++) {
            if (array[j] > array[i]) {
                tmp = array[j];
                array[j] = array[i];
                array[i] = tmp;
            }
        }
    }
    
    printf("after: ");
    for(int i = 0; i < LENGTH; i++) {
        printf("%d ", array[i]);
    }
    
    
}

上から順番にarrayは適当な順番のint型配列です。
tmpは値を入れ替えるときの一時的に格納する変数です。

#1をみてください。ここが今回のソートの肝になります。
i番目の値とj番目の値を比較するために二重ループを用います。

1回目
i
3 5 1 9 4 6 23

j
3 5 1 9 4 6 23

同じなので入れ替えなし

2回目
i
3 5 1 9 4 6 23

  j
3 5 1 9 4 6 23

j(5)の方が大きいので入れ替えなし。

2回目
i
3 5 1 9 4 6 23

    j
3 5 1 9 4 6 23

j(1)の方がちいさいので入れ替える。

      ・
      ・
      ・

これをn回目まで繰り返すようにする。

こんな感じでソートします。イメージはつかめましたか？
実際の値の入れ替えの処理はこちらです。

if (array[j] > array[i]) {
    tmp = array[j];
    array[j] = array[i];
    array[i] = tmp;
}

j番目の値がi番目の値より大きければ入れ替える。
簡単ですね！

Swiftでのソート

C言語では標準でsortする関数がないので自分で実装しないといけないですがSwiftなどのモダンな言語は標準でsort関数があるので楽ですね。
Swiftでのコードは

main.swift

var array = [3, 5, 1, 9, 4, 6, 23]
array.sort( { $0 > $1 } )

で実現できます。
めっちゃ簡単ですね笑

まとめ

今回紹介したバブルソートですが、実装が簡単なぶん配列の長さ^2の回数値を比較しないといけないのであまり長い配列に使うと計算回数が多くなってしまいます。
オーダーにするとO(N^2)になります。
ソートのアルゴリズムでは最低のものになっています。
なので大きな配列を扱う際は、クイックソートorマージソートなどのO(N log N)のものを使いましょう。

また、main関数内に処理を書いてしまうとmain関数が長くなってしまって可読性が低下したり他の配列をソートしたいと思った時の再利用性にかけるのでsort関数を作りましょう。その際はポインタで配列を引数に渡さないと元の配列の値が変更されないので気をつけましょう。

今回は以上です。