バブルソートの仕組みを理解する

このレッスンでは、Juliaでバブルソートのアルゴリズムを実装する方法を学び、並び替えの仕組みを基礎から理解することを目標にします。「Julia バブルソート 実装」で調べている方向けです。

バブルソートは、隣り合う2つの値を比べて、順番が逆なら入れ替える、を繰り返して並び替えるシンプルなアルゴリズムです。「大きい泡が少しずつ水面に浮かび上がっていく」ようすに似ていることからこの名前が付きました。

サンプルコードでは、二重のfor文を使い、内側のループで隣り合う要素arr[j]とarr[j+1]を比較して、順番が逆ならarr[j], arr[j+1] = arr[j+1], arr[j]というタプルの多重代入で入れ替えています。Juliaならではの簡潔なスワップの書き方に注目してみましょう。

初心者がよくつまずくのが、計算量の観点で効率が良いとは言えない点です。実務のコードで自分で書く機会はほぼありませんが、アルゴリズムを学ぶ最初の一歩として、多くの教科書で取り上げられる定番の題材です。

実務ではsort()のような最適化された関数を使うのが基本ですが、内部で何が行われているかを理解する上で学習用として重要なアルゴリズムです。