Pythonコードと図解で理解するバブルソートのアルゴリズム

Pythonには便利なライブラリが多数ありますが、それらを使わずにアルゴリズムを学習することでスタンダードなスキルを身に付けることが出来ます。ここでは、最もシンプルなバブルソートをPythonコードと図解で理解することを目標とします。

こんにちは。wat(@watlablog)です。ここではアルゴリズムの学習として、バブルソートを学習します！

目次（項目クリックでジャンプできます）

アルゴリズムを学ぶ意義

アルゴリズム(Algorithm)とは、問題を解決する手段、手続きそのもののことです。プログラミングの学習でアルゴリズムを学習することは効率の良いプログラムの作成において非常に重要です。

例えば、ある問題を解決するために、Aさんは複雑な条件分岐を駆使して達成、Bさんは数学的手法でわずか数行のアルゴリズムで達成したとします。
同じ問題を解決したとしても、Bさんの方が効率がよく、その後の保守もしやすい点で優れていることは明白です。

世の中にはすでに頭の良い人が考えたいわゆる「定石」ともなっているアルゴリズムが多数存在します。

さらに、アルゴリズムはコンピュータプログラミングの世界に留まらず、実生活で効率の良い仕組みを考える時にも重宝します。

当ブログではこのようなモチベーションから、Pythonを使ったアルゴリズム学習の記事を書いていこうと思います。

ここでは有名なソート（並べ替え）アルゴリズムである「バブルソート」を紹介します。

バブルソートの概要

目標

バブルソート(Bubble sort)とは、最もシンプルなソート(Sort:並べ替え)のアルゴリズムです。

任意の配列、リスト内の要素を昇順、または降順にソートすることが目標です。

以下の図はバブルソートのイメージ図です。横軸に要素番号\(x\)、縦軸に要素の値\(y\)をとった入力データを用意し（左）、データの比較や交換といった操作を行い（真ん中）、最終的に小さい値から大きい値に並べ替える出力を得る（右）ことが目標です。

このソートは数値データ以外にも、辞書型や文字列の並べ替えを行う際にも使うことが可能です。

フローチャートとPythonコードの例

バブルソートはアルゴリズムが非常にシンプルなことが特徴です。

以下にバブルソートのフローチャートを示します。回数の決まった2回のループを回します。

Loop1はiが0から増加するのに対し、Loop2はjが後から前に減少していく特徴を持ち、Loop2の中でj-1番目の要素とj番目の要素を比較、条件に当てはまっていればswap(交換)するというものです。

上記フローチャートをPythonコードで記述した例を以下のコードに示します。本コードはdef関数形式で書いており、配列dataと要素数nを渡してソート後の配列dataを返すという形式です。

ループの回数が決まっているため、forループを使用します。

# バブルソートを行う関数(data=配列データ、n=dataの要素数）
def bubble_sort(data, n):
    for i in range(n):                                      # i=0からnまでのループ
        for j in range(n-1, i, -1):                         # n-1からiまでの逆ループ
            if data[j-1] > data[j]:                         # 隣り合う値を比較
                data[j], data[j-1] = data[j-1], data[j]     # 交換
    return data

# バブルソートを行う関数(data=配列データ、n=dataの要素数）

def bubble_sort(data, n):

for i in range(n): # i=0からnまでのループ

for j in range(n-1, i, -1): # n-1からiまでの逆ループ

if data[j-1] > data[j]: # 隣り合う値を比較

data[j], data[j-1] = data[j-1], data[j] # 交換

return data

以下の動画は上記コードを要素数10個の配列dataに適用し、1操作ずつのdataの中身を可視化、アニメーションにしたものです。

このように、後の方から前にデータが移動していく様が、まるで泡（バブル）が水面に上昇してくるように見える…ということからバブルソートという名前が付いています。

バブルソートは以下の図のように、ソート済のデータが前方に固定されていく特徴を持ちます。

処理回数とオーダー

上の例では要素数10個で最終的に処理回数45までカウントされました。

バブルソートの処理回数はデータ数を\(N\)とすると、\(N(N-1)/2\)と決まっており、処理回数はデータ数の二乗に比例することから、\(O(N^{2})\)のオーダーを持つとも表現することがあります。

データ数の二乗で処理が遅くなるので、アルゴリズムはシンプルでわかりやすいのですが、一般的には遅いソートと言うことが出来ます。

検証のためのPythonコード

先ほどは関数部分のみでしたが、実際に配列を作成してバブルソートアルゴリズムを使ってみるコードを以下に示します（コピペでそのまま動くはず）。

サンプルデータはrandomを使ってランダムな数値配列を生成しています。

import random

# バブルソートを行う関数(data=配列データ、n=dataの要素数）
def bubble_sort(data, n):
    for i in range(n):                                      # i=0からnまでのループ
        for j in range(n-1, i, -1):                         # n-1からiまでの逆ループ
            if data[j-1] > data[j]:                         # 隣り合う値を比較
                data[j], data[j-1] = data[j-1], data[j]     # 交換
            print('i=', i, 'j=', j, data)
    return data

# ランダムなサンプルデータを使って関数を実行する
y = random.sample(range(5), k=5)
print('initial array=', y)
y = bubble_sort(y, len(y))

import random

# バブルソートを行う関数(data=配列データ、n=dataの要素数）

def bubble_sort(data, n):

for i in range(n): # i=0からnまでのループ

for j in range(n-1, i, -1): # n-1からiまでの逆ループ

if data[j-1] > data[j]: # 隣り合う値を比較

data[j], data[j-1] = data[j-1], data[j] # 交換

print('i=', i, 'j=', j, data)

return data

# ランダムなサンプルデータを使って関数を実行する

y = random.sample(range(5), k=5)

print('initial array=', y)

y = bubble_sort(y, len(y))

本コードを実行すると、コンソールにソート前の配列（initial array）とソート処理毎の配列が順次プリントされます。確かに最後は昇順になっていることを確認しました。

initial array= [4, 2, 1, 3, 0]
i= 0 j= 4 [4, 2, 1, 0, 3]
i= 0 j= 3 [4, 2, 0, 1, 3]
i= 0 j= 2 [4, 0, 2, 1, 3]
i= 0 j= 1 [0, 4, 2, 1, 3]
i= 1 j= 4 [0, 4, 2, 1, 3]
i= 1 j= 3 [0, 4, 1, 2, 3]
i= 1 j= 2 [0, 1, 4, 2, 3]
i= 2 j= 4 [0, 1, 4, 2, 3]
i= 2 j= 3 [0, 1, 2, 4, 3]
i= 3 j= 4 [0, 1, 2, 3, 4]

initial array= [4, 2, 1, 3, 0]

i= 0 j= 4 [4, 2, 1, 0, 3]

i= 0 j= 3 [4, 2, 0, 1, 3]

i= 0 j= 2 [4, 0, 2, 1, 3]

i= 0 j= 1 [0, 4, 2, 1, 3]

i= 1 j= 4 [0, 4, 2, 1, 3]

i= 1 j= 3 [0, 4, 1, 2, 3]

i= 1 j= 2 [0, 1, 4, 2, 3]

i= 2 j= 4 [0, 1, 4, 2, 3]

i= 2 j= 3 [0, 1, 2, 4, 3]

i= 3 j= 4 [0, 1, 2, 3, 4]

ちなみに、if文の「＞」記号を「＜」に変更することで降順にすることが可能です。

おまけ：バブルソートアニメーション

以下はおまけですが、バブルソート中の1操作毎にプロット画像を生成するためのコードです。

コードは完全に手抜き（同じ文をいたるところに書いていたり、プロットのスケールをサンプルデータに特化させていたり…）ですが、このコードを実行することで、先ほどのアニメーションの元となった画像を生成することが可能です。動きを見ると理解が深まると思いますので、是非参考にして下さい。

import numpy as np
from matplotlib import pyplot as plt

x = np.arange(1, 11, 1)
y = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

def bubble_sort(data, n):
    count = 0
    axis = np.arange(1, 11, 1)

    # ここからグラフ描画
    # フォントの種類とサイズを設定する。
    plt.rcParams['font.size'] = 14
    plt.rcParams['font.family'] = 'Times New Roman'

    # 目盛を内側にする。
    plt.rcParams['xtick.direction'] = 'in'
    plt.rcParams['ytick.direction'] = 'in'

    # グラフの上下左右に目盛線を付ける。
    fig = plt.figure()
    ax1 = fig.add_subplot(111)
    ax1.yaxis.set_ticks_position('both')
    ax1.xaxis.set_ticks_position('both')

    # 軸のラベルを設定する。
    ax1.set_xlabel('x')
    ax1.set_ylabel('y')
    ax1.set_xticks(np.arange(1, 11, 1))
    ax1.set_xlim(0, 11)
    ax1.set_ylim(0, 14)

    # データプロットの準備。
    ax1.bar(axis, data, label='initial')
    ax1.bar(0, 0, label='operated')
    ax1.bar(0, 0, label='sorted')
    plt.text(1, 12, 'N=' + str(count), fontsize=20)

    # グラフを表示する。
    fig.tight_layout()
    fig.legend()
    plt.savefig('fig_' + str("{:05}".format(count)) + '.png')
    plt.close()


    for i in range(n):
        for j in range(n-1, i, -1):
            count += 1
            if data[j-1] > data[j]:
                data[j], data[j-1] = data[j-1], data[j]
            # ここからグラフ描画
            # フォントの種類とサイズを設定する。
            plt.rcParams['font.size'] = 14
            plt.rcParams['font.family'] = 'Times New Roman'

            # 目盛を内側にする。
            plt.rcParams['xtick.direction'] = 'in'
            plt.rcParams['ytick.direction'] = 'in'

            # グラフの上下左右に目盛線を付ける。
            fig = plt.figure()
            ax1 = fig.add_subplot(111)
            ax1.yaxis.set_ticks_position('both')
            ax1.xaxis.set_ticks_position('both')

            # 軸のラベルを設定する。
            ax1.set_xlabel('x')
            ax1.set_ylabel('y')
            ax1.set_xticks(np.arange(1, 11, 1))
            ax1.set_xlim(0, 11)
            ax1.set_ylim(0, 14)

            # データプロットの準備。
            ax1.bar(axis, data, label='initial')
            ax1.bar([j, j+1], [data[j-1], data[j]], label='operated')
            ax1.bar(axis[:i], data[:i], label='sorted')
            plt.text(1, 12, 'N=' + str(count), fontsize=20)

            # グラフを表示する。
            fig.tight_layout()
            fig.legend()
            plt.savefig('fig_' + str("{:05}".format(count)) + '.png')
            plt.close()


    # ここからグラフ描画
    # フォントの種類とサイズを設定する。
    plt.rcParams['font.size'] = 14
    plt.rcParams['font.family'] = 'Times New Roman'

    # 目盛を内側にする。
    plt.rcParams['xtick.direction'] = 'in'
    plt.rcParams['ytick.direction'] = 'in'

    # グラフの上下左右に目盛線を付ける。
    fig = plt.figure()
    ax1 = fig.add_subplot(111)
    ax1.yaxis.set_ticks_position('both')
    ax1.xaxis.set_ticks_position('both')

    # 軸のラベルを設定する。
    ax1.set_xlabel('x')
    ax1.set_ylabel('y')
    ax1.set_xticks(np.arange(1, 11, 1))
    ax1.set_xlim(0, 11)
    ax1.set_ylim(0, 14)

    # データプロットの準備。
    ax1.bar(0, 0, label='initial')
    ax1.bar(0, 0, label='operated')
    ax1.bar(axis, data, label='sorted')
    plt.text(1, 12, 'N=' + str(count), fontsize=20)

    # グラフを表示する。
    fig.tight_layout()
    fig.legend()
    plt.savefig('fig_' + str("{:05}".format(count+1)) + '.png')
    plt.close()

    return data


sort = bubble_sort(y.copy(), len(y))
print(y)
print(sort)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

import numpy as np

from matplotlib import pyplot as plt

x = np.arange(1, 11, 1)

y = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

def bubble_sort(data, n):

count = 0

axis = np.arange(1, 11, 1)

# ここからグラフ描画

# フォントの種類とサイズを設定する。

plt.rcParams['font.size'] = 14

plt.rcParams['font.family'] = 'Times New Roman'

# 目盛を内側にする。

plt.rcParams['xtick.direction'] = 'in'

plt.rcParams['ytick.direction'] = 'in'

# グラフの上下左右に目盛線を付ける。

fig = plt.figure()

ax1 = fig.add_subplot(111)

ax1.yaxis.set_ticks_position('both')

ax1.xaxis.set_ticks_position('both')

# 軸のラベルを設定する。

ax1.set_xlabel('x')

ax1.set_ylabel('y')

ax1.set_xticks(np.arange(1, 11, 1))

ax1.set_xlim(0, 11)

ax1.set_ylim(0, 14)

# データプロットの準備。

ax1.bar(axis, data, label='initial')

ax1.bar(0, 0, label='operated')

ax1.bar(0, 0, label='sorted')

plt.text(1, 12, 'N=' + str(count), fontsize=20)

# グラフを表示する。

fig.tight_layout()

fig.legend()

plt.savefig('fig_' + str("{:05}".format(count)) + '.png')

plt.close()

for i in range(n):

for j in range(n-1, i, -1):

count += 1

if data[j-1] > data[j]:

data[j], data[j-1] = data[j-1], data[j]

# ここからグラフ描画

# フォントの種類とサイズを設定する。

plt.rcParams['font.size'] = 14

plt.rcParams['font.family'] = 'Times New Roman'

# 目盛を内側にする。

plt.rcParams['xtick.direction'] = 'in'

plt.rcParams['ytick.direction'] = 'in'

# グラフの上下左右に目盛線を付ける。

fig = plt.figure()

ax1 = fig.add_subplot(111)

ax1.yaxis.set_ticks_position('both')

ax1.xaxis.set_ticks_position('both')

# 軸のラベルを設定する。

ax1.set_xlabel('x')

ax1.set_ylabel('y')

ax1.set_xticks(np.arange(1, 11, 1))

ax1.set_xlim(0, 11)

ax1.set_ylim(0, 14)

# データプロットの準備。

ax1.bar(axis, data, label='initial')

ax1.bar([j, j+1], [data[j-1], data[j]], label='operated')

ax1.bar(axis[:i], data[:i], label='sorted')

plt.text(1, 12, 'N=' + str(count), fontsize=20)

# グラフを表示する。

fig.tight_layout()

fig.legend()

plt.savefig('fig_' + str("{:05}".format(count)) + '.png')

plt.close()

# ここからグラフ描画

# フォントの種類とサイズを設定する。

plt.rcParams['font.size'] = 14

plt.rcParams['font.family'] = 'Times New Roman'

# 目盛を内側にする。

plt.rcParams['xtick.direction'] = 'in'

plt.rcParams['ytick.direction'] = 'in'

# グラフの上下左右に目盛線を付ける。

fig = plt.figure()

ax1 = fig.add_subplot(111)

ax1.yaxis.set_ticks_position('both')

ax1.xaxis.set_ticks_position('both')

# 軸のラベルを設定する。

ax1.set_xlabel('x')

ax1.set_ylabel('y')

ax1.set_xticks(np.arange(1, 11, 1))

ax1.set_xlim(0, 11)

ax1.set_ylim(0, 14)

# データプロットの準備。

ax1.bar(0, 0, label='initial')

ax1.bar(0, 0, label='operated')

ax1.bar(axis, data, label='sorted')

plt.text(1, 12, 'N=' + str(count), fontsize=20)

# グラフを表示する。

fig.tight_layout()

fig.legend()

plt.savefig('fig_' + str("{:05}".format(count+1)) + '.png')

plt.close()

return data

sort = bubble_sort(y.copy(), len(y))

print(y)

print(sort)

まとめ

本記事では、有名なソートアルゴリズムであるバブルソートの概要を説明し、実際にPythonプログラムで実装してみました。

アルゴリズムは効率の良いプログラミングの実現に大変役立つため、継続して色々なアルゴリズムを紹介していこうと思います。

バブルソートを習得しました！アニメーションにすると理解しやすいですね！
Twitterでも関連情報をつぶやいているので、wat(@watlablog)のフォローお待ちしています！

アルゴリズムを学ぶ意義

バブルソートの概要

目標

フローチャートとPythonコードの例

処理回数とオーダー

検証のためのPythonコード

おまけ：バブルソートアニメーション

まとめ

コメント

コメントを残すコメントをキャンセル

最近の投稿

アーカイブ

カテゴリー

アルゴリズムを学ぶ意義

バブルソートの概要

目標

フローチャートとPythonコードの例

処理回数とオーダー

検証のためのPythonコード

おまけ：バブルソートアニメーション

まとめ

SNSでもご購読できます。

コメント

コメントを残す コメントをキャンセル

最近の投稿

アーカイブ

カテゴリー

コメントを残すコメントをキャンセル