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

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

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

サンプルコードでは、二重のfor文を使い、外側のループで全体を何周も回しながら、内側のループで隣り合う要素を比較・交換しています。Pythonではarr[j], arr[j + 1] = arr[j + 1], arr[j]のように、一時変数を使わず2つの値を入れ替えられるのが特徴的な書き方です。

初心者がよくつまずくのが、内側のループの範囲を正しく絞り込めない点です。すでに並び替えが完了した末尾の部分まで毎回比較してしまうと無駄な処理が増えるため、少しずつ比較範囲を狭めていく工夫が必要になります。アルゴリズムを学ぶ最初の一歩として、動きをじっくり目で追いながら理解するのに向いています。

実務のコードで自分で書く機会はほぼありませんが、アルゴリズムを学ぶ最初の一歩として、多くの教科書で取り上げられる定番の題材です。Pythonのsorted()関数はより高速なアルゴリズムで実装されているため、実際の開発では自分でソートを実装することはほとんどありません。