クイックソートがバブルソートを圧倒する理由

アルゴリズムって聞くとやっぱりソート、つまり並べ替えが思い浮かびませんか？ええ、代表的ですよね。 バラバラのデータを順番に並べる、ただそれだけのことのはずなのに、なんでこんなにたくさんの種類があるんでしょう。 今回は、お預かりした資料をもとに、ソートアルゴリズムの代表格、バブルソートとクイックソート、 この二つの性格と、そして速さの秘密に迫っていきたいと思います。はい。 例えば、100枚のカードを並べ替えるのに、隣同士を1枚ずつ地味に比べるのと、 賢くグループ分けして一気に片付けるので、どれくらい結果が変わるのか、一緒に見ていきましょう。 ええ、本編のゴールは、単に手順を覚えることじゃないんですよね。と言いますと、 なぜ、一見シンプルで合理的に見える方法が、ある状況では全く役に立たないのか。 そして、ほんの少し視点を変えるだけで、どれだけ劇的に効率が上がるのか。 その問題解決のアプローチ、そのものを体感していただくのが目標です。いや、面白そうですね。 なんだか子供の頃の整列を思い出しますよ。整列ですか？ええ、背の順に並ぶ時、 とりあえず隣の子と背比べして、自分の方が高かったらごめん変わってって。あぁ、やりますね。 それを端まで繰り返すっていう、あれはまさにバブルソートだったんだなと資料を読んで思いました。 素晴らしい例えですね。まさにバブルソートの本質です。じゃあ、まずはこの一番直感的なバブルソートから見ていきましょうか。 はい。やることは、今おっしゃった通り、隣り合う二つの要素を比べて、もし順番が逆だったら入れ替える。 これをデータの端から端まで何度も何度も繰り返す。もうただそれだけです。シンプルですね。 1、2、1、2と本当に一歩ずつ進むような非常に地味な方法ですね。このバブルっていう名前も面白いですよね。 資料にあった、水の中の泡がプクプク浮かんでくるイラスト、あれが名前の由来なんですか？ええ、その通りです。 この操作を繰り返していくと、軽い要素、つまり小さい数字が、水中の泡、バブルのようにですね、 自然とリストの先頭に向かってプクプクと浮かび上がってくる。へぇ、なるほど。その様子から名付けられました。 誰でも思いつく簡単な方法だからこそ、プログラミングを学び始めた人がまず最初に挑戦するアルゴリズムの代表例なんです。 でも正直なところ、これで十分じゃないかとも思うんですよ。とおっしゃいますと、 今のコンピューターってものすごく計算が速いじゃないですか。この地道な方法でも、 人間が気づかないくらいの速さで、あっという間に終わらせてくれるんじゃないかなって。ええ、良い視点ですね。 確かにデータが数十個とか、まあ100個くらいなら全く問題ありません。ですよね。 しかし、このアルゴリズムの本当の弱点は、データの数が大きくなった時に牙を剥きます。牙を剥く。 比較と入れ替えの回数が、私たちの想像を絶する勢いで、爆発的に増えるんです。爆発的ですか。はい。 この効率の悪さを測る物差しとして、計算量という概念があります。計算量。どれくらい手間がかかるかの指標ですね。 それがバブルソートの場合、どう表現されるんでしょう。バブルソートの計算量はこう表現されます。はい。O、n、2乗。 O、n、2乗。ええ、アルファベットのOに括弧をつけて、中にnの2乗が入っている形。数式で書くとON2。 なんだかすごく重々しい響きですね。このnの2乗が爆発的に増えるということの正体ですか？ まさに。このnはデータの数を表しますからね。nの2乗が意味するのは、データ数が10倍になったら、 処理にかかる時間や手間は、10倍じゃないんです。えっと、10の2乗、つまり100倍になるということです。 へぇ、100倍ですか。そうなんです。じゃあデータが100倍になったら時間は100倍じゃなくて、 100の2乗で、ええ、1万倍になるってことですか？ご名答です。その通りです。 データが1000倍になれば時間は100万倍。うわぁ。データが増えれば増えるほど加速度的に効率が悪くなって、 もう現実的な時間では終わらなくなってしまう。なるほど。これがバブルソートが教育用とされて、 実際の現場ではほとんど使われない最大の理由です。真面目で実直なんですけど、残念ながら要領が悪い働き者といったところでしょうか。 真面目だけでは乗り越えられない壁ですね。そこで登場するのが、もう一方の主役。はい。 資料の一つにソートの王様とまで書かれていたクイックソート。ええ、その名の通り非常に高速です。 そして、その速さの秘密は、バブルソートとは全く異なる大胆なアプローチにあります。メモにクイックソートの革新は、 パカっと分ける一瞬にあると面白い表現がありましたね。ええ。この分けるというのが具体的にどういうことか教えていただけますか？ それがまさにクイックソートの真髄で、分割統治という考え方に基づいています。分割統治。 まず、ごちゃ混ぜのカードの山から、基準となるカードを1枚適当に選びます。これをピボットと呼びます。 ピボット。バスケの軸足みたいなものですね。まさに。そのピボットを軸にして、残りの全てのカードを二つの山に分けるんです。 二つの山に。ピボットの数字より小さいカードの山と、ピボットの数字より大きいカードの山。たったこれだけです。 はぁ、なるほど。たった1回パカっと分けるだけで、小さい山にあるカードと大きい山にあるカードは、 もうお互いに一つ一つ比べる必要が一切なくなるわけですね。その通りです。そこがこのアプローチの最も賢い点です。 すごい。バブルソートが一軒一軒隣の家を訪ねて背比べしている間に、クイックソートは、 はい背の低い人たちは右、高い人たちは左、と一瞬で交通整理してしまうようなものです。でもちょっと待ってください。 その最初のピボット選びがすごく重要そうですね。お、もし変な数字、例えば一番大きい数字とか一番小さい数字を毎回選んでしまったら、 グループが全然均等に分かれないんじゃないですか？うんうん。片方が空っぽで、もう片方に全部みたいに。 素晴らしい、非常に重要な指摘です。あ、やっぱり。ええ、それはクイックソートが抱える唯一にして最大のアキレス腱に関わる話です。 その点については最後にじっくりお話しするとして。あ、はい。まずは理想的な働き方を見ていきましょう。 うまく分割できたとして、その分けたグループの中ではどうするか。あ、そうか。分けたグループの中でまた同じことをすればいいんですね。 ご名答です。分けたそれぞれのグループの中で、また新しいピボットを選んで、さらに小さいグループに分ける。 これをグループの要素が一つになるまで再帰的に繰り返していくんです。再帰的。自分で自分を呼び出すような処理ですね。 まさに。ロシアのマトリョーシカ人形をイメージしてみてください。マトリョーシカ。大きな人形を開けると、 中に同じ形の小さな人形がいて、それを開けるとまた中に。クイックソートはこの人形を次々と開けていくように、 分けたグループに対して自分と全く同じ仕事をさせて、問題をどんどん小さくしていく。これが分割統治の考え方です。 ははぁ。つまり本当の勝負は、入れ替えの速さじゃなくて、そもそも比べる必要のないペアをいかに早く、 そして大量に見つけ出すか、という点にあるわけですね。そういうことです。その結果、全体の比較回数が劇的に少なくなる。 ではこちらの計算量はどうなるか。気になりますね。クイックソートの効率の良さを示す計算量はこうなります。O、n、log、n。 O、n、log、n。はい。数式ではO(n log n)と書きます。先ほどのnの2乗と比べると、なんだか複雑な形をしていますね。 log nというのがいまいちピンとこないのですが。形は少し複雑に見えますが、このlog nというのが魔法のスパイスなんです。 魔法のスパイス。ざっくり言うと、分厚い電話帳から特定の名前を探す時の動きに似ています。電話帳ですか？ まず真ん中を開いて、探す名前が前半か後半か判断して、関係ない半分を捨てますよね。あー、やりますね。 次に残った半分のまた真ん中を開く。この繰り返す回数がlog nのイメージです。データが倍になっても探す手間はたった1回増えるだけ。 へぇー。だからnが100万、1000万と大きくなっても、nにかける相手であるlog nが驚くほど小さいままで済むんです。 なるほど、nの2乗はデータが増えると掛け算の相手も同じだけ増えるけど、 n log nはnが増えても掛け算の相手はほんのちょっとしか増えないということですか？そういうことです。 この差は圧倒的ですよ。データが100万件あったと仮定しましょう。100万件。バブルソートのnの2乗は100万の2乗で、 1兆回という途方もない計算が必要になります。1兆。一方、クイックソートのn log nは大体2000万回程度で済んでしまう。 1兆回と2000万回。もう同じ土俵で語るのがおかしいくらいの差ですね。ええ、これは確かに王様です。 だからこそ、多くのプログラミング言語で標準のソート機能として採用されているわけです。いやぁ、面白いです。 ここまでをまとめると、本当に性格の違いという言葉がぴったりですね。うんうん。隣同士をコツコツと見比べる、地味で実直なバブルソート。 そして、まず全体を大きく捉えて、賢き分割して一気に方を付ける。クレバーな戦略家のクイックソート。 ええ、同じ並べ替えというゴールを目指しているのに、考え方が違うだけで、これほどまでに性能が変わるとは。 そして、ここが一番お伝えしたい点なのですが、これは単なるコンピューターの中だけの話ではないんです。と言いますと、 私たちが日常で何か問題解決をする時の思考法にそのまま通じるものがあります。日常での問題解決ですか。はい。 例えば、あなたが大量のタスクリストを抱えているとします。そのタスクをリストの一番上から順番に、ただひたすら片付けていく。 あぁ。これはまさにバブルソート的なアプローチです。着実ではありますが、もしタスク同士の関連性とか、 優先順位を考えないと、非常に効率が悪くなる可能性がある。あぁ、わかりますそれ。とりあえず目の前のことから手をつけて、 後になって、あぁ先にこっちをやっておけばさっきのタスクはやる必要もなかったのにって後悔するパターンですね。 一方で、クイックソート的なアプローチはこうです。まずタスク全体を眺めて、ある基準、例えば今日中に絶対にやるべきことと、 今週中にやればいいことという大きな塊にパカっと分ける。なるほど。これがピボットを使った大の分割です。 なるほど、旅行の計画を立てる時にも似ていますね。最初に行き先も宿もアクティビティも全部決めようとするとパニックになりますけど、 ええ、まずアジアかヨーロッパかを決め、次にどの国にするかを決め、最後にどの都市に何泊するかを決める。 とやるとスムーズに進みます。これもクイックソート的ですね。素晴らしい例えです。まさにそれです。 問題を解決可能なサイズにまで分割していく。うんうん。最初に全体を仕分けることで、頭が混乱しなくなるし、 本当に集中すべきことが明確になる。どういうアプローチを選ぶかで、最終的にかかる時間や労力が文字通り点と地ほど変わってくる。 はぁ。アルゴリズムの世界から学べる非常に普遍的な教訓がここには隠されているんです。 今回はバブルソートとクイックソートという二つのアルゴリズムを通して、問題解決におけるアプローチの違いがいかに絶大な効果をもたらすかを見てきました。 ええ。ただ早い、遅いという表面的な話ではなく、その背後にある考え方こそが重要だということが腑に落ちました。はい。 ということは、もうバブルソートの出番はなくて、どんな時でもクイックソートを使えば間違いないということなんでしょうか。 いい質問ですね。ほとんどの場合はその通りです。だからこそ王様と呼ばれている。はい。しかし、ここで一つ考えてみてほしいのです。 先ほどあなたが鋭く指摘した点を思い出してください。私が指摘した点。あぁ、ピボットの選び方ですか。ええ。 もしこのクイックソートが毎回毎回分割するための基準、つまりピボットとして考えうる限り最悪の選択をし続けてしまったら、 一体どうなるでしょう。最悪の選択。つまり、分けたグループが片方はすごく大きくて、 もう片方はたった一つ、みたいな状況がずっと続くということですか？ええ、その通りです。 あの賢い戦略家がある特定の条件下では、信じられないほど非効率に、それこそあの地味なバブルソートと変わらないくらい遅くなってしまう瞬間は果たしてあるのか。 うわぁ。その点を少し考えてみると、アルゴリズムという世界のさらなる奥深さが見えてくるかもしれないですね。