並べ替え_バブルとクイックソート

スマホの写真フォルダとか、音楽のプレイリスト、ネットショッピングの検索結果。僕たちの周りって実は、並べ替えの技術で溢れてるんですよね。 今日はその裏側で頑張ってくれてるソートアルゴリズムの中から、特に有名な2つ、バブルソートとクイックソートの世界を一緒に覗いてみましょうか。 なんか難しそうですけど大丈夫。驚くほどシンプルな仕組みなんですよ。 いや分かります。バブルソートにクイックソートって名前だけ聞くと、なんか専門的で難しそうって感じしちゃいますよね。 でも大丈夫です。今日のこの話では難しい数式は一切出てきません。 もっと身近な例えを使って、この2つの賢いやり方の違いを誰もが「あ、なるほどね」って思えるように解説していきますね。 ではまず一番イメージしやすい方からいきましょうか。それがこのバブルソート。 プログラミングを初めて学ぶ人が大体最初に出会うアルゴリズムなんです。 なんでかっていうと、その考え方がもうめちゃくちゃシンプルで僕たちの感覚にすごく近いからなんですね。 バブルソートを理解するための魔法の言葉。それはもうたった一つ。「お隣さんと比べる」。 本当にこれだけなんです。バラバラに並んだ数字のカードがあったらまず左の2枚を見て、順番が逆なら入れ替える。 次に一個ずれてそのまた隣のペアを見てっていうのをひたすら繰り返していく。地味ですけど確実な方法ですよね。 じゃあなんでバブル、つまり泡なんて名前がついてるんでしょうね。このイラストがまさにその答えなんです。 ちょっと想像してみてください。水の中に大小様々な泡があったら、重い泡はだんだん底に沈んで、軽い泡はふわふわっと上に登ってきますよね。 バブルソートも全く同じで、比較と交換を繰り返していくと自然と大きな数字がリストの最後に、 小さな数字が先頭に集まってくるんです。上手いこと名付けたもんですよね。 じゃあ具体的にどうやるかっていうと本当にこの3ステップを繰り返すだけ。まずリストの左端からスタートして、ステップ1「隣を見る」。 ステップ2「自分のほうが大きかったら入れ替える」。これをカチッカチッと右端まで続けていくとどうなると思います？ そう、このリストの中で一番大きな数字がまるで王様みたいに、一番右の席にどーんと座ることになるんです。 で、また左端から同じことを繰り返す。これを何度もやることで、少しずつ全体が綺麗に並んでいくっていうわけですね。 でもですよね、こんなにシンプルってことは、まあやっぱり弱点もあるわけです。 データが10個くらいなら全然問題ないんですけど、これが何千何万っていう量になったらどうでしょう。 一つ一つ隣と比べていたらいや気が遠くなる作業になっちゃいますよね。 そこで賢い人たちは考えたわけです。「もっと効率よく早くやる方法はないもんか」と。 さあ、お待たせしました。そこで登場するのが今日のもう一人の主役、その名もクイックソート。 いや、名前からして速そうですよね。 バブルソートの一個ずつコツコツっていうアプローチとは全く違う画期的なアイデアで、この速さの問題に立ち向かいます。 クイックソートの心臓部。一番大事な考え方はズバリ「分割して統治せよ」です。 これって例えば、散らかりきった部屋を片付ける時、いきなり全部やろうとしないで、 まず本はこっち服はあっち、みたいにエリア分けしますよね。あれと全く同じです。 ごちゃっとした大きな問題をまず扱いやすい小さな問題に分けてしまう。これが速さの最大の秘密なんです。 じゃあどうやって分けるのって話なんですけど、ここで出てくるのがピボット、つまり基準点です。 これ言葉だけ聞くと難しそうですけど大丈夫。学生の時やりましたよね。背の順に並ぶやつ。 先生が「よし、じゃあ真ん中の君を基準にするぞ」って一人指名する。この基準にされる人こそがピボットなんですよ。 やり方は驚くほど頭がいいんです。まずステップ1で基準になるピボットを一人決めますよね。 で、ステップ2先生が号令をかけるわけです。 「ピボット君より背が高い人は右、低い人は左に集まれ」って。どうです？ たった一回の指示で、ごちゃごちゃだった集団が大まかに二つのグループに分かれちゃいますよね。 あとはその分かれたグループの中でまた同じことを繰り返していくだけ。 隣の人と何度も何度も背比べする必要なんてない。 これが圧倒的な速さの理由なんです。 まさにこの言葉の通り。一人ずつ隣を見ていく地味なバブルソートと比べて、 基準を決めて全体をざっと大きく動かす。 この発想の転換こそが、クイックソートを文字通りクイックたらしめている核心部分なんですね。 力技じゃなくて戦略で勝つ、って感じでかっこいいですよね。 さあというわけでいよいよ直接対決と参りましょう。 地味でコツコツ派のバブルソート対頭脳派でスピード自慢のクイックソート。 一体どっちがどんな場面で輝くのか、それぞれの戦略とスピードをちょっとだけ数字も交えながら比べてみましょう。 この表を見ると一目瞭然ですよね。特に見てほしいのがこの「平均速度」の欄。 なんかOの2乗とか謎の暗号みたいなのが書いてありますけど、これ超簡単に言うと、 データの量が増えた時のしんどさレベルみたいなもんです。 バブルソートのNの2乗っていうのは、データが10倍になるとしんどさは100倍になるってこと。 一方、クイックソートは、 それよりずっと緩やかに大変さが増えていく。この差がデータが大量になった時にとんでもないスピードの差を生むわけです。 さてここまで二つのアルゴリズムを見てきましたけど、 じゃあ今日これだけは覚えて帰ってほしいっていう一番大事なポイントを最後にぎゅっとまとめておきましょう。この二つのイメージさえあればもうバッチリです。 はいこれです。まずバブルソートは、そう、お隣同士の交換。 一歩一歩着実に進むカメさんみたいなイメージですね。分かりやすいのが長所。 で、一方のクイックソートは分割して統治。 最初にドカンと大きく分けて、あとは賢く片付けていくウサギさん。とにかく早い。 このカメとウサギのイメージ、これで完璧じゃないでしょうか。 最後にちょっと周りを見渡してみてください。 あなたがいつも聞いている音楽のプレイリスト、通販サイトのおすすめ商品、ネットの検索結果。 これらが一瞬であなたにぴったりの順番で表示される裏側では、 まさに今日話したようなアルゴリズムたちが物凄い勢いで働いてるんですよね。 単純なバブルソートで十分な時もあれば、一瞬の遅れも許されないクイックソートみたいな技術が必要な時もある。 僕たちの便利な生活って、実はこういう賢い並べ替えの戦略に支えられてるんだなと思うとなんだかワクワクしませんか？