ソートにはいくつかのアルゴリズムが存在します。 ここではそのアルゴリズムのいくつかをC#等による実装を交えて紹介していきます。
アルゴリズムと特徴
ソートの安定性
ソートのアルゴリズムには安定性というものがあります。 ソートの安定性とは、ソートの際に2つの値が同じ場合に並べ替えが起こるか否かのことを言います。
同値の場合にソートの前後で並べ替えが起こらない(ソートの前後で順序が維持される)ものを安定性のあるソート、または安定ソートといい、逆に並べ替えが起こる(ソートの前後で順序が変わる可能性がある)ものを安定性のないソートといいます。
内部ソート・外部ソート
ソートに際して、データ自体の格納領域を変更することで並べ替えを行うものを内部ソート、データ以外の一時領域が必要となるものを外部ソートと呼びます。
ソートのアルゴリズム
ソートのアルゴリズムの概要と、各言語の実装例を紹介します。 なお以下で例示する実行結果はソート途中の状態を表すもので、ソートアルゴリズムの処理の量を反映しているわけではありません。
単純選択法・選択ソート (Selection Sort)
単純選択法とは、データの並べ替えられていない部分から最小値を一つ選び出し、最初のデータと交換していくという作業を繰り返すことによりソートを行うものです。 単純選択法は、安定性のないソート、内部ソートのアルゴリズムです。
最小値ではなく最大値を探すことで、降順にソートするようになります。
単純交換法・バブルソート (Bubble Sort)
単純交換法とは、データの最後尾から順に読んでいき、その一つ前のデータとの大小関係により交換していくという作業を繰り返すことによりソートを行うものです。 決定項(ソートされたデータ)が先頭に向かって泡のように浮き上がる様子から、バブルソートとも呼ばれます。 単純交換法は、安定性のあるソート、内部ソートのアルゴリズムです。
単純挿入法・挿入ソート (Insertion Sort)
単純挿入法とは、ソート済みのデータからソートするデータを入れるべき場所を探し、以降のデータを後ろにずらすことで場所を空けてデータを挿入するという作業を繰り返すことによりソートを行うものです。 単純挿入法は、安定性のあるソート、内部ソートのアルゴリズムです。
クイックソート (Quick Sort)
クイックソートとは、データから適当な値を選び出し、その値を中心にして大小に分けていくという作業を繰り返すことによりソートを行うものです。 クイックソートは、安定性のないソートアルゴリズムです。
この例では再帰によってクイックソートを実装していますが、データ数が多い場合はその分だけ再帰的に呼び出されるので注意が必要です。 再帰を使った実装では再帰のために領域が必要であるとみることもできますが、一般的には内部ソートとみなされます。