【アルゴリズム解説】バブルソートとは

2020/5/26 2020/5/26 書き溜め

今回は、アルゴリズムの整列問題「バブルソート」について書き溜め
新しく計算機科学を学ぶ人のためのマイルストーンを残していく。

概要

バブルソート

大きい数字が泡のように浮いてくる

バブルソートとは、ソート(整列問題)に関するアルゴリズムの一つで、基本交換法ともよばれます。
隣り合う要素の大小を比較しながら整列させていきます。

バブルソートのアルゴリズム

バブルソートのアルゴリズムはWikipediaを参照する。

全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行なう。
なおこの繰り返しは、入れ替えが起こらなくなった時点で（それ以降は何度繰り返しても変化が起こらなくなるので）中断することができる。

全要素を１つずつ比較して大きいものを右に集めていくイメージです。

バブルソートの計算量は

データ数nのときのアルゴリズム計算量はO(n^2)である。

学習用途で利用されるアルゴリズムで
ライブラリなどで採用されることはほぼ無い。

バブルソートをPython3で実装する

バブルソートをPython3実装すると下記のようになる。

arr = [8, 3, 4, 10, 2, 7, 5, 6];
print(arr)
print("====START====")
no_swap = True
while no_swap:
  no_swap = False
  for j in range(len(arr)-1):
    print(arr[j], " vs ", arr[j+1])
    if arr[j] > arr[j+1]:
      tmp = arr[j]
      arr[j] = arr[j+1]
      arr[j+1] = tmp
      print("Swap")
      no_swap = True
      print(arr)

print("====END====")
print(arr)

arr = [8, 3, 4, 10, 2, 7, 5, 6];

print(arr)

print("====START====")

no_swap = True

while no_swap:

no_swap = False

for j in range(len(arr)-1):

print(arr[j], " vs ", arr[j+1])

if arr[j] > arr[j+1]:

tmp = arr[j]

arr[j] = arr[j+1]

arr[j+1] = tmp

print("Swap")

no_swap = True

print(arr)

print("====END====")

print(arr)

(*天才による指摘はいつでも受け付けている)

バブルソートをJavaで実装する

バブルソートをJava実装すると下記のようになる。

class BubbleSort {
  public static void main(String[] args){
    int[] arr = { 8, 3, 4, 10, 2, 7, 5, 6 };
    System.out.println("start");
    for (int i=0; i<arr.length; i++) System.out.print(arr[i]);
    boolean noSwap = true;
    while (noSwap) {
      noSwap = false;
      for (int i=0; i < arr.length-1; i++){
        if (arr[i] > arr[i+1]){
          int tmp = arr[i];
          arr[i] = arr[i+1];
          arr[i+1] = tmp;
          noSwap = true;
        }
      }
      if (noSwap == false) break;
    }
    System.out.println("");
    System.out.println("end");
    for (int i=0; i<arr.length; i++) System.out.print(arr[i]);
    System.out.println("");
  }
}

class BubbleSort {

public static void main(String[] args){

int[] arr = { 8, 3, 4, 10, 2, 7, 5, 6 };

System.out.println("start");

for (int i=0; i<arr.length; i++) System.out.print(arr[i]);

boolean noSwap = true;

while (noSwap) {

noSwap = false;

for (int i=0; i < arr.length-1; i++){

if (arr[i] > arr[i+1]){

int tmp = arr[i];

arr[i] = arr[i+1];

arr[i+1] = tmp;

noSwap = true;

}

if (noSwap == false) break;

}

System.out.println("");

System.out.println("end");

for (int i=0; i<arr.length; i++) System.out.print(arr[i]);

System.out.println("");

}

(*天才による指摘はいつでも受け付けている)

バブルソートを説明しプログラムを書いてください。

さて、先程の説明を読んだ人は、バブルソートを説明できますね。
余裕の有る方は、好きな言語でバブルソートを実装してみてください。

ノートやメモに書くでも、Twitterに呟くでもYoutubeにアップロードするでも構いません。
今日知った情報をアウトプットしてみましょう。

じゃあね〜〜〜。