Python基礎講座の第5回目です。
ソートアルゴリズムの1つである「バブルソート(Bubble Sort)」について解説します。
基本情報技術者試験にも出題される基本的なアルゴリズムなので、しっかり理解していきましょう。
YouTubeにも解説動画を上げていますので、動画が良い方はそちらをご参考ください。
ソートアルゴリズムとは
ソートとはデータを一定の規則に従って並べ替えるという意味です。
英語のSortのことで、整列と訳されることが多いです。
ソートでよく使われる単語に昇順と降順があります。
小さい順に並べることを昇順、大きい順に並べることを降順と言います。
例えば、[1, 2, 3]は昇順にソートされており、[3, 2, 1]は降順にソートされています。
このソートする方法をソートアルゴリズムといいます。
今回はソートアルゴリズムの中でも簡単なバブルソートを紹介します。
計算量の解説でO記法を使用します。
O記法が分からない方は以下の記事で解説しているので参考にしてみてください。
バブルソートとは
バブルソートは隣り合う2つの要素を比較し、比較した結果によって要素を入れ替えることでデータをソートします。
今回はデータを昇順（小さい順）に並べ替える場合を考えてみましょう。
昇順にソートする場合は、隣り合う2つの要素を比較して以下2パターンの操作を繰り返します。
- 左にある要素より右にある要素の方が大きい場合、何もしない
- 左にある要素より右にある要素の方が小さい場合、左と右の要素を入れ替える
例として、この操作を繰り返すことで、[3, 8, 1, 2]という配列がどのようにソートされていくか見てみましょう。
まず先頭の3と隣の8を比較します。
左にある3より右にある8の方が大きいので何もしません。
次に8と1を比較します。
左にある8より右にある1のほうが小さいので2つの要素を入れ替えます。
次に8と2を比較します。
左にある8より右にある2のほうが小さいので2つの要素を入れ替えます。
データの中で一番大きな8が末尾に来ました。
これで末尾の要素が8に決まります。
同様の操作を繰り返しましょう。
次は末尾から2番目の要素が決まります。
同様の操作を繰り返しましょう。
次は末尾から3番目の要素が決まります。
これで末尾から3番目の要素が決まりました。
まだ決まっていないのは先頭のみですので、最後に残った1が先頭と自動的に決まります。
これで全ての要素の場所が決定しました。
このように隣り合う要素を比較してソートするアルゴリズムをバブルソートといいます。
コード
どのようなアルゴリズムか分かったところでコードに書いてみましょう。
def bubble_sort(data):
length=len(data)
for i in range(1, length):
for j in range(0, length-i):
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j]
if __name__ == '__main__':
data = [3, 8, 1, 2, -1, -10, 4, 2]
bubble_sort(data)
print(data)単純なアルゴリズムでしたがコードにすると少し難しいですね。
1つ1つ解説していきます。
コード解説
1行目
まず1行目でバブルソートを実行するbubble_sortメソッドを定義します。
引数にソートしたいデータ（data）を受けとります。
2行目
2行目でソートしたいデータの数をlengthに入れています。
なぜデータの数が必要か考えていきましょう。
先ほど[3, 8, 1, 2]を昇順でソートした操作をまとめてみます。
- 末尾が8に決まる
- 末尾から1つ前の要素が3に決まる
- 末尾から2つ前の要素が2に決まる
- 先頭は残った1に決まる
操作4は最後に残った1が必然的に先頭と決まるので何も操作していません。
実際に要素を決めているのは操作1~3ですので、[3, 8, 1, 2]のデータをバブルソートするには3回の操作が必要となります。
つまり、4個のデータをソートするには3回の操作が必要です。
ではデータが[3, 8, 1, 2, 6]の場合は何回の操作が必要でしょうか？
ソート後は[1, 2, 3, 6, 8]となりますが、この場合も末尾の8から決まっていき、最後に残った1が先頭に決まります。
2, 3, 6, 8の場所が決まれば全ての要素の場所が決まるので、[3, 8, 1, 2, 6]をソートするには4回の操作が必要となります。
つまり5個のデータをソートするには4回の操作が必要です。
なんとなく見えてきたでしょうか？
データの要素数と必要な操作の回数をまとめると、「操作の回数 = データの要素数 – 1」となります。
このように、必要な操作の回数を知るためにデータの要素数が必要なので、2行目でデータの要素数をlengthに入れています。
3行目
次に3行目でrange(1, length)の範囲でループし、操作が何回目にあたるかを i に入れています。
例えばPythonでは for index in range(1, 5):と書くことで index は1, 2, 3, 4の値をとり、4回ループします。
先ほどみたようにループの回数（操作の回数）はデータの要素数 – 1回となっています。
4行目
4行目でもう1度ループをします。
こちらのループはrange(0, length-i) の範囲でループしています。
range(0, length-i) は何を意味しているでしょうか？
まず結論から言うと、隣り合う要素と比較する回数を表しています。
これを理解するために[3, 8, 1, 2]がどのようにソートされたか思い出しましょう。
まず末尾の8を決める時は以下の操作でした。
data = [3, 8, 1, 2]とすると、末尾の8を決める時は隣り合う要素の比較を次の3回行っています。
- data[0]とdata[1]を比較（3と8を比較）
- data[1]とdata[2]を比較（8と1を比較）
- data[2]とdata[3]を比較（8と2を比較）
そしてこの3回というのは、もう定番になってきていますがデータの数 – 1ですね。
次に末尾から1つ前の要素を3に決める時は以下の操作でした。
末尾から1つ前の要素を3に決める時は隣り合う要素の比較を次の2回行っています。
- data[0]とdata[1]を比較（3と1を比較）
- data[1]とdata[2]を比較（3と2を比較）
先ほどの末尾の要素を8に決めた時と比べると比較回数が1回減っています。
これは末尾が8に決まったため、まだソートできていないデータの数が1つ減ったからです。
まとめると、バブルソートでは末尾から1つずつ要素を決めていきます。
要素が1つ決まるごとに次の要素を決める時の隣り合う要素を比較する回数は1回減るのです。
そしてこの比較回数が1回ずつ減っていくのを range(0, length-i) の length-i で表現しています。
ここまで理解できれば残りは簡単です。
5~6行目
5行目で隣り合う要素を比較し、左の要素の方が右の要素よりも大きいか確認します。
もし大きい場合は6行目で隣り合う要素の入れ替えを行います。
以上がバブルソートのアルゴリズムです。
実行結果
最後にコードを実行して昇順にソートされることを確認しましょう。
ちゃんと昇順にソートされていますね。
計算量
コードの3行目と4行目を見てください。
バブルソートでは2つのループがネスト（入れ子構造*1のこと）しています。
*1：あるモノの中にそれと同じモノを入れた構造のことで、マトリョーシカをイメージすると分かりやすいです。
まず以下のようのなネストしたループの計算量を考えてみましょう。
counter = 1
for i in range(0, 5):
for j in range(0, 5):
print(counter)
counter = counter + 1このコードのように2つのループがネストしており、それぞれのループが5回繰り返されるとすると、ループは合計5 x 5 = 25回実施されます。
つまりネストしたループの計算量は（1つ目のループの回数）x（ 2つ目のループの回数 ）となります。
ネストしたループの計算量が理解できたところで、バブルソートの計算量を考えていきましょう。
データ数をNとした時、バブルソートでは2つのループがネストしており、それぞれのループの数はデータ数Nに比例します。
これをO記法を使って表すとO(N) x O(N)となります。
（O記法については前回学んだO記法の説明を思い出してください。）
まとめると、バブルソート全体の計算量はO(N2)と表されます。
最後に & 関連書籍
以上、第5回目はバブルソートについてでした。
基本情報技術者試験に出てくる基本のアルゴリズムですので、しっかり理解しておきましょう。
以下の記事で他のソートアルゴリズムについても解説しています。
興味があれば読んでみてください。
以下では探索アルゴリズムを解説しています。
こちらも基本のアルゴリズムとなりますので、しっかり理解しておきましょう。
分かりにくいところや「もっとこうしてほしい」などのご意見がありましたら、ツイッターから連絡いただけると幸いです。
質問に関してもお気軽にお問い合わせください。
以下は関連書籍です。
コメント