バラバラのデータをきれいに並べ替える「ソートアルゴリズム」。バブル・選択・挿入・クイック・マージの5つを、仕組み・計算量・安定性の3点でスッキリ整理しましょう。
小夜川 ほのか
ソートって……たしか、並び替えのことですよねぇ?
紫垣 こはる 先生
そうよ。
テストの点数を高い順に並べたり、名前をあいうえお順にしたり。
その「順番どおりに並べる処理」のことね。
星見 めい
並べるなんて簡単じゃん。
小さい順に置いてけばいいだけでしょ?
紫垣 こはる 先生
ふふ、人間ならパッと見て並べられるけれど、コンピュータは一度に全体を見渡せないの。
だから「2つを比べて入れ替える」を地道に繰り返すのよ。
その手順の違いで、いくつもの方法に分かれるの。
蜂谷 まこと
ITパスポートでよく出るのは5つです。
バブルソート・選択ソート・挿入ソート・クイックソート・マージソートですね。
星見 めい
バブルって、あの泡のバブル?
なんで泡なの?
紫垣 こはる 先生
隣り合う要素を比べて、大きい方を後ろへずらしていくの。
すると大きな値が、水中の泡みたいにスーッと後ろへ浮かび上がっていくでしょう?
だからバブルソートよ。
小夜川 ほのか
なるほどぉ。
じゃあ選択ソートはどんな感じなんですかぁ?
蜂谷 まこと
全体を見て一番小さい値を探し、それを先頭に置きます。
次に残りから一番小さい値を探して2番目に置く。
これを繰り返します。
「最小値をひとつずつ選んで確定する」のがポイントです。
星見 めい
挿入ソートはトランプって言ってたよね。
あー、配られた札を整えるときの動きか。
マジか、めっちゃ身近じゃん。
紫垣 こはる 先生
そうそう。
左から順に見ていって、新しい1枚を「ここだ」という位置に差し込んでいくの。
すでに並んでいるデータが多いほど速くなるのが特徴よ。
小夜川 ほのか
うーん、3つとも仕組みは分かりましたぁ。
でも、速さって違うんですかぁ?
蜂谷 まこと
違います。
速さは計算量で比べます。
バブル・選択・挿入はどれもO(n²)で、データが増えると一気に遅くなります。
星見 めい
n²ってことは……10個なら100回、100個なら1万回?
うわ、増え方えぐいじゃん。
紫垣 こはる 先生
そこで登場するのが速い2つ。
クイックソートとマージソートね。
まことさん、共通の作戦を説明してくれる?
蜂谷 まこと
はい。
どちらも分割統治法を使います。
クイックソートはピボットを1つ選び、それより小さい値を左、大きい値を右に振り分けて、各グループでまた同じことを繰り返します。
小夜川 ほのか
大きい問題を、小さく小さくしていくんですねぇ。
マージソートはどう違うんですかぁ?
蜂谷 まこと
マージソートは先にデータを半分・半分とひたすら2つに割っていきます。
1個になったら、今度はソート済みの2つを比べながら1つに併合(マージ)していくんです。
星見 めい
分けてから合体ってことね。
じゃあ速さは2つとも同じなの?
蜂谷 まこと
平均はどちらもO(n log n)です。
ただしクイックソートは運が悪いと最悪O(n²)まで落ちます。
マージソートは常にO(n log n)が保証されるのが強みですね。
紫垣 こはる 先生
整理すると、遅いけど分かりやすい3つがO(n²)、速い2つがO(n log n)。
覚え方は「バ・選・挿は二乗、クイック・マージは速い」よ。
小夜川 ほのか
もう一個分からないのがあるんですぅ。
安定とか不安定って、なんのことですかぁ?
紫垣 こはる 先生
いい質問ね。
安定ソートと不安定ソートの違いよ。
星見 めい
同じ値なんだから、どっちが前でも一緒じゃん?
蜂谷 まこと
それが、データに別の情報がくっついていると効いてきます。
たとえば「出席番号順に並んだ生徒」を点数で並べ替えるとき、安定ソートなら同じ点数の人は出席番号順のまま。
不安定だとその順序が崩れることがあるんです。
星見 めい
あー、なるほど。
同点でも元の並びが残ってるとキレイってことか。
紫垣 こはる 先生
そのとおり。
マージソートと挿入ソートは安定、クイックソートは不安定。
試験では『マージは安定でO(n log n)保証』がよく狙われるわよ。
小夜川 ほのか
ふぅ、たくさん出てきたけど、表で見たらスッキリしそうですぅ。
紫垣 こはる 先生
ええ。
仕組み・計算量・安定性の3点セットで並べて覚えれば完璧よ。
最後にまとめておくわね。
確認クイズ
クイックソートの説明として最も適切なものはどれか。
- 隣り合う要素を順に比較・交換し、常に計算量はO(n²)である
- ピボットを基準に分割を繰り返し、平均計算量はO(n log n)である
- データを半分に分けて併合し、常に安定なソートである
- 最小値を選んで先頭に置く操作を繰り返す単純なソートである
こたえを見る
正解: 2. ピボットを基準に分割を繰り返し、平均計算量はO(n log n)である
クイックソートはピボット(基準値)で小さい組と大きい組に分割し、再帰的に並べる分割統治法のソートで、平均計算量はO(n log n)です。選択肢1はバブルソート、選択肢3はマージソート(安定・常にO(n log n))、選択肢4は選択ソートの説明であり誤りです。なおクイックソートは最悪時O(n²)で、不安定ソートである点も押さえましょう。