ソート概要 (アルゴリズムとデータ構造)

概要

まあ、結局の所、今現在世の中で使われているソートアルゴリズムの大半は、マージソートかクイックソートをベースにしたものです。（基本的にこの2つのソートを使い、途中から挿入ソートというソートに切り替えるという手法が有名。）

ですが、そこに至るまでの道筋には先人達の試行錯誤があったわけで、その試行錯誤の中で生まれ、現在に至るまでその名を残すアルゴリズムは結構な種類存在します。そして、アルゴリズム入門書籍・ウェブサイトでは、その手のソートアルゴリズムが必ずといっていいほど頻繁に取り上げられています。

これは、以下のような理由で、アルゴリズム入門として記事にしやすいからでしょう。

いろんな種類のアルゴリズムがある
それぞれの特徴が分かりやすい・説明しやすい
オーダーの違うアルゴリズムの圧倒的差を体感できる

ということで、このページでも様々なソートアルゴリズムについて説明したいと思います。

はじめに

まずはじめにいくつか留意点を。

「アルゴリズムとデータ構造」インデックスページでも書いたように、サンプルプログラムには C# を用います。また、C# 2.0 の機能であるジェネリックスを使用します。

それから、ソートでは、アルゴリズムの種類を問わず、 2つの要素を入れ替えるスワップという処理をよく使用します。なので、スワップは以下のように関数化しておきます。

/// <summary>
/// a と b の中身を入れ替える。
/// </summary>
/// <param name="a">オペランドa</param>
/// <param name="b">オペランドb</param>
public static void Swap<T>(ref T a, ref T b)
{
  T c = a; a = b; b = c;
}

ref というキーワードに関しては「引数の参照渡し」を、 <T> という部分に関しては「ジェネリクス」を参照してください。

安定性

数あるソートアルゴリズムを分類する方法の1つに、安定性の有無があります。

安定なソート（stable sort）とは、順序的に同等な要素が複数あったときに、その並びが元のまま保たれるもののことを言います。そうでない場合は不安定（unstable）。

整数などの、単純な数値型の配列を比較する場合には安定性の有無は問題になってきませんが、以下のようなケースを考えて見ましょう。

具体的な例として、年齢と名前のペアを作り、その配列で名簿管理みたいなことをしたいとします。そして、年齢の大小でソートすることを考えて見ましょう。まず、年齢と名前のペアは Entry と言う名前で以下のように実装します。

class Entry : IComparable<Entry>
{
  public int age;
  public string name;

  public Entry(int age, string name)
  {
    this.age = age;
    this.name = name;
  }

  int IComparable<Entry>.CompareTo(Entry other)
  {
    return this.age.CompareTo(other.age);
  }
}

これを使って、以下のようなリストを作ります。

Entry[] list = new Entry[]{
  new Entry(10, "a"),
  new Entry(11, "b"),
  new Entry(12, "c"),
  new Entry(11, "d"),
  new Entry(13, "e"),
  new Entry(10, "f"),
  new Entry(12, "g"),
  new Entry(14, "h"),
};

この状態では、名前順に並んでいますね。そして、10歳、11歳、12歳のエントリーがそれぞれ複数含まれています。これを、Array.Sort メソッドを使ってソートしてみましょう。

Array.Sort(list);
foreach (Entry entry in list)
{
  Console.Write("{0}, {1}\n", entry.age, entry.name);
}

結果は以下のようになります。

10, f
10, a
11, d
11, b
12, g
12, c
13, e
14, h

名前の順序がばらばらになっていることが分かります。 Array.Sort は、おそらくクイックソートを使っている物と思われます。クイックソートには安定性はなく、名前の順序を元のまま保てません。もしも、これを安定なソートアルゴリズムを使ってソートするならば、結果は以下のようになります。

10, a
10, f
11, d
11, b
12, c
12, g
13, e
14, h

「シェルソート」

高速なソート

O(n lon n)の物。

整数限定のソート

範囲が予め分かっている整数に限って、 O(n) で計算できる物。制限が強いけども、超高速。

「バケットソート」
「基数ソート」

ソースファイル

紹介したソートプログラムのソースファイルを置いておきます。

ソースファイル

[お問い合わせ](q)

ソート概要

目次

キーワード

概要

はじめに

安定性

外部記憶の必要性

オーダー

単純なソート

高速なソート

整数限定のソート

ソースファイル

ソート

コレクション

その他のアルゴリズム