目次

キーワード

概要

まあ、結局の所、今現在世の中で使われているソートアルゴリズムの大半は、マージソートか「クイックソート」をベースにしたものです。 （基本的にこの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

外部記憶の必要性

配列をソートする際に、 配列内の要素の交換だけでソートできる物を内部ソートと呼びます。 逆に、ソートしたい配列の他に、余分に記憶領域を確保して、 そちらに一時的にデータを保存しなければならない物を外部ソートと呼びます。

大半のソートアルゴリズムは内部ソートだったりします。 有名どころのうちで、例外はマージソートのみ。

オーダー

ソートに限らず、アルゴリズムの良し悪しの判断基準として最も重要なのは計算量でしょう。 計算量の評価は、厳密に行うのは難しい場合も多く、 大まかな見積もりにとどめる場合もあります。

計算量の大まかな見積もり指標の1つがオーダーです。

単純なソート

O(n2)の物。

ちょっと高速な物。

高速なソート

O(n lon n)の物。

整数限定のソート

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

ソースファイル

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

ソースファイル

更新履歴

ブログ