【Go言語でソートアルゴリズムを学ぶ】バブルソート

バブルソートとは

隣接する値どうしの比較、入れ替えを繰り返すことで、値を大きい順または小さい順に整列させる方法です。

計算量は O(n^2)です。 Go言語でのコード例は以下の通りです。

Embedded content: https://gist.github.com/sena-anny/54ceff9d7950239f1f541236e5fcf518

数字の配列の先頭から隣り合う数字を比較していき、右隣の数字が小さかった場合は順序を入れ替えるというのを最後尾までやります。

例）初期状態: [2, 1, 5, 4, 3]

1ループ目: [1, 2, 4, 3, 5] 先頭から隣り合うものを並べ替え（4回）

2ループ目: [1, 2, 3, 4, 5] 2番目から隣り合うものを並び替え（3回）

3ループ目: [1, 2, 3, 4, 5] 3番目から隣り合うものを並び替え（2回）

4ループ目: [1, 2, 3, 4, 5] 4番目から隣り合うものを並び替え（1回）

例では2ループ目には並べ替えは終了していましたが探索は続けられます。