たとえばクラスや社員の名前がまとまった名簿などを、出席番号や年齢、五十音順で並べ替えることは、表計算ソフトを使えばそう難しいことではありません。

表計算ソフトには普通に付いているこの機能は、どんな場面でも必要とされる大切な機能です。

しかしそのプログラムを正常に、かつ高速に動かすために色々なノウハウが詰まっていると考える方はそう多くないでしょう。

我々の社会を根底で支える「整列のアルゴリズム」の数々を、少しだけ覗いてみませんか？

スポンサーリンク

整列の方法は一つじゃない

整列のアルゴリズムには色々あり、それぞれが違う長所短所を備えているので、最も効率が良いのはこれ、と決めることはできません。

整列のアルゴリズムには「安定ソート」であるかどうか、という注目点が一つあります。安定ソートとは、並べ替えをした後も初期の順位関係が保たれているソート方法のことです。（「ソート」とは整列の意味）

五十音順に並んでいる社員名簿を、後から年齢順に安定ソートで整列させた場合、同じ年齢であっても五十音順で並んだ状態になっています。

このように、整列させたいリストの対象によっては安定ソートであることが求められる場合があります。それぞれのアルゴリズムがどのような特長をもっているのか、見てみましょう。

バブルソート

全体を見ながら並べ替えるのではなく、隣り合った数字同士を比べて並べ替える、という動作を何度も繰り返すという、ごく単純な整列方法です。

1番目と2番目を比べて、より小さい方を1番に入れ替えます。次に2番目と3番目を比べて、より小さい方を2番へ持ってきます。次に3番と4番…を最後まで繰り返したら、もう一度1番目と2番目の入れ替えからやり直します。

これを、入れ替えが発生しなくなるまで続けます。延々続けると、最も小さい数字が前へ、大きい数字は後ろへと移動していくので、いずれ整列します。安定ソートなので、始めの並び順を保ちます。

「時間のかかるやり方だなあ」とは思いませんか？　例として、トランプでの並べ替えを行ってみましたが、非常に時間がかかります。

実際のところ、最も基本的で初歩的な整列方法であり、ほとんどの整列アルゴリズムはバブルソートが抱える問題を改善するために考案されています。

単純なアルゴリズムであり、例のトランプでいえば、手に持った状態での並べ替えができます（コンピュータのメモリが少なくても済む）ので、状況次第では使われることもあるようです。

しかし出番のほとんどは、他のアルゴリズムを学習、比較対象とするための非効率的な手法でもあります。

スポンサーリンク

挿入ソート

1番目と2番目を比べて、小さい方が1番になるよう交換します。続いて3番目の数字が2番までよりも少ない場合は、1番目か2番目の都合の良い場所に「挿入」します。

同じことを4番目、5番目と続け、最後まで繰り返します。

バブルソートと同じく「安定ソート」です。速度に関しては、全体を比較する回数が減っているために早く終わらせることができます。また、ほぼ整列している状態ならばすぐに終了できるのも特長です。

バケットソート

文字通り、バケツの中に放り込んでいくようなイメージの整列アルゴリズムです。

トランプを例とした場合、1から13の番号を振っておいたバケツに次々と置いていきます。ちょうど、「7並べ」の完成図を作るような感覚といえます。トランプの整列においては、最も効率のよい整列方法ではないでしょうか？

高速での処理が可能なアルゴリズムであり、出番は多いようです。

ただし、基本的に安定ソートではありません。さらに、これまで紹介したソート方法のように、トランプを手に持った状態での整列ができません。

これはコンピュータ上では大きな違いであり、億単位の膨大な量のデータを並べ替える場合は、それぞれを配置することができる「記憶容量」が必要になります。

クイックソート

1960年、イギリスでアントニー・ホーア氏が開発したアルゴリズムであり、世界的に最も使われているアルゴリズムであると知られています。

文字通り速度に特化したソート方法であり、一般的に他のどのソート方法と比べても高速ですが、その動きはかなり複雑なため、大雑把な説明にとどめておきます。

整列する対象の中からひとつ取り出し「軸要素」を決定します。この軸要素より大きい数字と小さい数字を交換し、大きい数字が後へと回るように交換し、これを繰り返します。

交換した場所で山を二つに分けて「軸要素」を決定し、同じことを繰り返します。

トランプでやってみると、色々と考えなければいけないので決して速くはありませんが、コンピュータならば非常に効率よく並べ替えが可能です。

しかし一つ重大な欠点があり、ほとんど整列に等しい状態のリスト（綺麗に並んだリストの最後に一つだけ追加した場合など）を整列する場合、アルゴリズムが終了するまで非常に長い時間がかかってしまいます。

現在使われているアルゴリズムは？

最も高速といわれている「クイックソート」が使われやすい傾向にあるようですが、大きな弱点を埋めるためにこれを派生、あるいは他のアルゴリズムを取り入れるような方法で使われています。

整列のアルゴリズムは、スーパーや銀行など、金銭をあつかう場では常に必要とされており、そういう意味では生活の中に溶け込んだ重要で身近な要素です。

数々の研究者、プログラマーの手により、意識せずその恩恵を得られることに感謝したいですね。

スポンサーリンク