アルゴリズムとデータ構造編【整列】 第0章 はじめに

この章の概要

この章の概要です。

イントロダクション

この先の章では、整列アルゴリズムを扱います。 整列アルゴリズムは、ソートアルゴリズムとも呼ばれます。

整列アルゴリズムは、配列のようなデータの集まりを、何らかの基準に従って並び替えるアルゴリズムです。 ここでいう基準は多くの場合、値の小さいデータから大きいデータの順に並べる昇順か、 その反対に大きいデータから小さいデータの順に並べる降順のいずれかを指しています。

平均的に見て、高い性能を発揮するクイックソート(第9章)のようなアルゴリズムは、 多くのプログラミング言語で、標準ライブラリ等の形で用意されています。 例えば、C言語なら qsort関数(⇒リファレンス)を使えます。
そのため、アルゴリズムの詳細を知らなくても、単純な整列アルゴリズムを利用することは簡単にできます。 しかし、アルゴリズムの特性を理解していないと、性能改善ができなかったり、うまく整列できない理由が分からなかったりするでしょう。

安定なソート

整列アルゴリズムは、安定なソート安定でないソートとに分類できます。

ここで安定というのは、もしソート対象のデータ列の中に同じ値が複数存在したとき、 ソート前後で、それらのデータの位置関係が変化し得るかどうかを表しています
例えば、次のようなデータ列を昇順にソートするとします。

8, 4, 7, 2, 1, 4, 6, 3

ここには、4 が 2つ含まれています。 左側の 4 を 4a、右側の 4 を 4b と呼ぶことにします。
ソートを行った結果、次のようになったとします。

1, 2, 3, 4b, 4a, 6, 7, 8

この場合、ソート前は 4a の方が 4b よりも左側にあったのに、ソート後には 4a の方が右側に来ています。 このような結果を生むのが、安定でないソートです。
ただし、これは安定でないソートを使うと必ず位置関係が崩れるということではなく、 崩れてしまう可能性を持っているという意味です。

一方、安定なソートを行うと次のようになります。

1, 2, 3, 4a, 4b, 6, 7, 8

4a と 4b の位置関係が保たれています。 安定なソートを使った場合は、位置関係は必ず保たれます

安定性が重要な場面では、必ず安定な整列アルゴリズムを選択しなければなりません。 ですから、各整列アルゴリズムが安定であるかどうかは、理解しておく必要があります。

ただし、安定でない整列アルゴリズムを使っても、データに何か補助的な情報を持たせておく等の工夫を加えれば、 安定なソートを実現することは可能です。 この場合、多少の性能低下を招くことにはなりますが、場合によっては有効な手段になり得ます。
これが有効な手段になるかどうかは、いつもそうですが、実測してみるしかありません(【導入】第2章参照

内部ソートと外部ソート

もう1つ、整列アルゴリズムの分類方法として、 内部ソートであるか外部ソートであるかという点があります。

この分類の解釈は幾つかあるようですが、その1つの解釈としては、 ソート作業を行うときに、対象のデータ列の中だけで完結できるかどうかです。 他の場所に作業領域を確保しなければならないアルゴリズムは外部ソートに分類され、 そうでなければ内部ソートに分類されます。
例えば、対象のデータ列が配列だとして、その配列内で要素を並び替えていくだけでソート作業が完了できるのなら内部ソートです。 一方、配列のコピーを作ってから、そちらでソート作業を行わなければならないようなら、外部ソートになります。

メモリ上だけで完結するか、ハードディスクなどの外部記憶装置を必要とするかという観点で分類されることもあるようです。 あるいは、作業領域がどのくらい必要になるかで分類することもあります。

この分類方法はそれほど深く気にする必要はないと思いますが、作業領域がどの程度必要になるのかは、知っておくべき事柄です。 アルゴリズムの選択を誤ると、大量のデータのソート時にメモリ不足に陥るといった問題が起こる可能性があるのです。


参考リンク

更新履歴

'2012/4/30 新規作成。



次の章へ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ