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

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

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

サンプルコードでは、二重のeachブロックを使い、外側のループで全体を何周も回しながら、内側のループで隣り合う要素を比較・交換しています。arr[j], arr[j + 1] = arr[j + 1], arr[j]のように、多重代入を使って一時変数なしで2つの値を入れ替えられる点もRubyらしい書き方です。

初心者がよくつまずくのが、内側のループの範囲を正しく絞り込めない点です。すでに並び替えが完了した末尾の部分まで毎回比較してしまうと無駄な処理が増えるため、少しずつ比較範囲を狭めていく工夫が必要になります。

実務のコードで自分で書く機会はほぼありませんが、アルゴリズムを学ぶ最初の一歩として定番の題材です。計算量の観点では効率が良いとは言えず、実務ではsortメソッドのような最適化された実装を使うのが基本です。