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ループを使用します。

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

バブルチャート処理の様子を表した動画

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

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

バブルソートの説明図(図解)

処理回数とオーダー

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

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

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

検証のためのPythonコード

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

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

本コードを実行すると、コンソールにソート前の配列(上)とソート後の配列(下)がプリントされます。確かに昇順になっていることを確認しました。

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

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

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

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

まとめ

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

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

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

  • このエントリーをはてなブックマークに追加

SNSでもご購読できます。

コメント

コメントを残す

*