ソートアルゴリズム：バブルソートとは

ソートアルゴリズムとは

ソートアルゴリズムの意味は、ソートとアルゴリズムの意味を理解すれば分かります。

ソートとは、ある規則に則って、データを並び替えることを指します。

アルゴリズムは、ある課題に対してどのように解決するのかその方法や考え方を指します。

したがって、ソートアルゴリズムとは、バラバラのデータを規則的にどのように並び替えるのかという考え方のことです。

その中の１つであるバブルソートを紹介します。

今回は、バラバラの数値データを昇順に並び替えることを考えます。

バブルソートとは

バブルソートは、隣の値を比較して、並び替える方法です。バブルは日本語で泡です。

並べ替えの過程でデータが下から上へ移動する様子が、泡が浮かんでいくように見えることが「バブル」という由来になっています。

下の動画は、バブルソートを可視化したものになります。値が大きい方から決定しており、バブルには見えませんが、値が小さい方からだとバブルに見えます。

こちらはフォークダンスでバブルソートを再現しています。個人的になかなか面白いです。

プログラムで書いてみよう

Pythonでバブルソートのプログラムを書いてみようと思います。

他のサイトでは、逆ループをしておられる記事がたくさんありましたが、正直、自分がいちから考えるならこうします。逆ループをしなくてもできます。

考え方として、隣り合う2つの値を比較し、要素番号が大きい方の値が要素番号が小さい方の値より小さい場合、両者の要素番号を入れ替えて、それ以外は、スルーする繰り返し文を作ればいいということが分かります。

def bublle(data):
    length=len(data)
    for j in range(length-1):
        if data[j]>data[j+1]:
            data[j],data[j+1] = data[j+1],data[j]
    return data

data=[5,4,3,2,1]
print(data)
cdata=bublle(data)
print(cdata)

実行結果

[5, 4, 3, 2, 1]
[4, 3, 1, 2, 5]

3行目でlength-1にしているのは、lengthにすると最後、要素数を超えて比較をしてしまうので、それを防ぐためです。

5の要素が一番大きく、要素番号が一番大きい要素になりました。しかし、これを更に繰り返し処理をしなければなりません。

今回の例では、一番大きい要素番号は、比較する必要がありません。

ですので、

そう考えると、2重に繰り返し処理をしなければならないことが分かります。

def bublle(data):
    length=len(data)
    for i in range(1,length):
        for j in range(length-i):
            if data[j]>data[j+1]:
                data[j],data[j+1] = data[j+1],data[j]
            print(data)
    return data

data=[5,4,3,2,1]
print(data)
cdata=bublle(data)
print(cdata)

いざ、実行。