Python3系で学ぶ基本アルゴリズム「バブルソート」

ＯＫバブリー

どうも、日本一ギャグセンスがあるエンジニア、しゅういちです。

IT業界にきて早くも一年が過ぎました。で、先日上司にお題を出されたんですよ。

「ぶっちゃけバブルソート、自分で書けるか？」ってね。

はい、書けますとも！！と即答したはいいのですが。

30分経っても全然解けない

ガーン・・・かけると思っていたのに、力のなさを思い知りましたよｗというわけで、今日は基本的なアルゴリズム「バブルソート」をPython3系を使いながら、解説します。解説すると身に付くっていうしね。うんうん。

バブルソートが書けるようになるために必要な要素は？

プログラミングでバブルソートが書けるようになるには、以下の要素が必要になります。

 
最低限これだけは抑えておきましょう。

では、さっそく以下はバブルソートの例です。

import random
targetArray = list(range(10)) #配列リストを作ります。
random.shuffle(targetArray) #配列リストをシャッフルします。
print(targetArray) #中身がシャッフルされているか確認します。
for i in range(len(targetArray)): #targetArrayの中身の要素の数だけ回します。
	for j in range(len(targetArray)-1, i, -1): #要素の右端から要素の数だけ回します。
		if targetArray[j] < targetArray[j-1]: #隣り合う要素の数を比較します。
			targetArray[j], targetArray[j-1] = targetArray[j-1], targetArray[j] #条件に合っていたら、隣を交換します。
	print(targetArray)

そして結果がこちら

画像をご覧いただくとわかるように、一番右端の数とその隣の数が条件に合致した時に、数が入れ替わっています。
処理が進むごとに数字が右側にずれていっているのがわかります。う、美しい。。。！

具体的にポイントとなる一行を見ていきます

ポイントになるのは2つ目のfor文とその中のif文です。

for j in range(len(targetArray)-1, i, -1):

と書いています。この一文を理解するにはrange関数を理解する必要があります。

range関数リファレンス

上記の一文の場合、targetArrayの配列の数は10でカウントされますが、配列は0から数えるので、最後の要素でエラーが出力されてしまいます。こんな風に
10個目の要素はありませんよ！って怒られました。上記のコードでlen(targetArray)-1の-1を消して実行した結果です。

ということはこのコードを日本語で説明すると、

「targetArrayの要素[9]から-1していく間、iの数になるまで繰り返し処理を行います。」

って書いてあるんです。これわかるかなぁ・・・range関数がわかれば、この一文の意味が分かる。

まとめ

ソートアルゴリズムはプログラミングする上で基本中の基本。だから、是非、これをきっかけに基本的なソートアルゴリズムが書けるようになると、エンジニア未経験の人は、より良いプログラムを書く要素の一つになりますので、チャレンジしてみてくだされ。