ソートアルゴリズム — 同じ並び替えでも手間が違う
バラバラの数字を小さい順に並べる。やることは同じなのに、手順(アルゴリズム)が違うと、かかる手間が大きく変わります。同じ6枚のカードを並べ替えるのに、何回「比べたか」を数えてみると、その差がはっきり見えてきます。
下の図1で、まずバブルソートを選んで「進む」を押してみてください。となり同士を比べて入れ替えるだけの素朴なやり方です。次にアルゴリズムをクイックソートに切り替えて、同じ並びを並べ替えてみましょう。最後の「比べた回数」がどれだけ違うかが、この記事の核心です。
比べた回数 0
ステップ 1 / 1
アルゴリズムを選んで「進む」を押してください。
図1 — 同じ6枚を並べ替える。色のついた棒が「いま比べているカード」
素朴なやり方ほど、何度も比べる
バブルソートは、となり同士をしらみつぶしに比べていきます。カードが6枚なら必ず15回。10枚なら45回、100枚なら約5,000回と、枚数の2乗のペースで膨らみます(これを O(n²) と呼びます)。
クイックソートは違います。「基準(ピボット)より大きいか小さいか」でグループを2つに割り、さらにその中で割り…と分割していくので、比べる回数はn × log n のペースで済みます。6枚程度では差はわずかでも、データが1万件・100万件と増えるほど、この差は決定的になります。
用語ミニ辞書
- 比較
- 2つの値の大小を調べる操作。ソートの「手間」を測るものさし。
- ピボット
- クイックソートで「これより大きい/小さい」を分ける基準の値。
- O(n²) / O(n log n)
- データが増えたとき手間がどう膨らむかの目安。後者の方がずっと緩やか。
まとめ
どのアルゴリズムも結果は同じ「小さい順」。違うのはそこへ至る手間です。少量なら何を使っても一瞬ですが、データが大きくなるほどアルゴリズムの選び方が速さを左右します。実際のプログラミング言語の標準ソートは、こうした効率の良い手法(クイックソートやマージソートの改良版)を使っています。