ソートにはいくつかのアルゴリズムが存在します。 ここではそのアルゴリズムのいくつかをC#等による実装を交えて紹介していきます。

§1 アルゴリズムと特徴

§1.1 ソートの安定性

ソートのアルゴリズムには安定性というものがあります。 ソートの安定性とは、ソートの際に2つの値が同じ場合に並べ替えが起こるか否かのことを言います。

同値の場合にソートの前後で並べ替えが起こらない(ソートの前後で順序が維持される)ものを安定性のあるソート、または安定ソートといい、逆に並べ替えが起こる(ソートの前後で順序が変わる可能性がある)ものを安定性のないソートといいます。

§1.2 内部ソート・外部ソート

ソートに際して、データ自体の格納領域を変更することで並べ替えを行うものを内部ソート、データ以外の一時領域が必要となるものを外部ソートと呼びます。

§2 ソートのアルゴリズム

ソートのアルゴリズムの概要と、各言語の実装例を紹介します。 なお以下で例示する実行結果はソート途中の状態を表すもので、ソートアルゴリズムの処理の量を反映しているわけではありません。

§2.1 単純選択法・選択ソート (Selection Sort)

単純選択法とは、データの並べ替えられていない部分から最小値を一つ選び出し、最初のデータと交換していくという作業を繰り返すことによりソートを行うものです。 単純選択法は、安定性のないソート、内部ソートのアルゴリズムです。

単純選択法
using System;

public class SelectionSort {
  static void Main()
  {
    int[] data = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};

    // 並べ替える前の並びを表示
    Print(data);

    Console.WriteLine("ソート開始");

    // 単純選択法による並べ替え
    for (int i = 0; i < data.Length - 1; i++) {
      // まだ並べ替えられていない部分から最小値を探し出す
      int min = i;

      for (int j = i + 1; j < data.Length; j++) {
        if (data[min] > data[j])
          min = j;
      }

      // 見つかった最小値と最初のデータを入れ替える
      int temp = data[i];

      data[i] = data[min];
      data[min] = temp;

      Print(data);
    }

    // 並べ替えた後の並びを表示
    Console.WriteLine("ソート終了");

    Print(data);
  }

  static void Print(int[] data)
  {
    Console.WriteLine(string.Join(", ", Array.ConvertAll(data, d => d.ToString())));
  }
}
実行結果
8, 3, 5, 4, 9, 2, 6, 0, 7, 1
ソート開始
0, 3, 5, 4, 9, 2, 6, 8, 7, 1
0, 1, 5, 4, 9, 2, 6, 8, 7, 3
0, 1, 2, 4, 9, 5, 6, 8, 7, 3
0, 1, 2, 3, 9, 5, 6, 8, 7, 4
0, 1, 2, 3, 4, 5, 6, 8, 7, 9
0, 1, 2, 3, 4, 5, 6, 8, 7, 9
0, 1, 2, 3, 4, 5, 6, 8, 7, 9
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
ソート終了
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

最小値ではなく最大値を探すことで、降順にソートするようになります。

§2.2 単純交換法・バブルソート (Bubble Sort)

単純交換法とは、データの最後尾から順に読んでいき、その一つ前のデータとの大小関係により交換していくという作業を繰り返すことによりソートを行うものです。 決定項(ソートされたデータ)が先頭に向かって泡のように浮き上がる様子から、バブルソートとも呼ばれます。 単純交換法は、安定性のあるソート、内部ソートのアルゴリズムです。

単純交換法
using System;

public class BubbleSort {
  static void Main()
  {
    int[] data = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};

    // 並べ替える前の並びを表示
    Print(data);

    Console.WriteLine("ソート開始");

    // 単純交換法による並べ替え
    for (int i = 0; i < data.Length - 1; i++) {
      // 最後尾からデータを読んでいく
      for (int j = data.Length - 1; j > i; j--) {
        if (data[j - 1] > data[j]) {
          // 一つ前のデータの方が大きい場合、位置を交換する
          int temp = data[j - 1];

          data[j - 1] = data[j];
          data[j] = temp;

          Print(data);
        }
      }
    }

    // 並べ替えた後の並びを表示
    Console.WriteLine("ソート終了");

    Print(data);
  }

  static void Print(int[] data)
  {
    Console.WriteLine(string.Join(", ", Array.ConvertAll(data, d => d.ToString())));
  }
}
実行結果
8, 3, 5, 4, 9, 2, 6, 0, 7, 1
ソート開始
8, 3, 5, 4, 9, 2, 6, 0, 1, 7
8, 3, 5, 4, 9, 2, 0, 6, 1, 7
8, 3, 5, 4, 9, 0, 2, 6, 1, 7
8, 3, 5, 4, 0, 9, 2, 6, 1, 7
8, 3, 5, 0, 4, 9, 2, 6, 1, 7
8, 3, 0, 5, 4, 9, 2, 6, 1, 7
8, 0, 3, 5, 4, 9, 2, 6, 1, 7
0, 8, 3, 5, 4, 9, 2, 6, 1, 7
0, 8, 3, 5, 4, 9, 2, 1, 6, 7
0, 8, 3, 5, 4, 9, 1, 2, 6, 7
0, 8, 3, 5, 4, 1, 9, 2, 6, 7
0, 8, 3, 5, 1, 4, 9, 2, 6, 7
0, 8, 3, 1, 5, 4, 9, 2, 6, 7
0, 8, 1, 3, 5, 4, 9, 2, 6, 7
0, 1, 8, 3, 5, 4, 9, 2, 6, 7
0, 1, 8, 3, 5, 4, 2, 9, 6, 7
0, 1, 8, 3, 5, 2, 4, 9, 6, 7
0, 1, 8, 3, 2, 5, 4, 9, 6, 7
0, 1, 8, 2, 3, 5, 4, 9, 6, 7
0, 1, 2, 8, 3, 5, 4, 9, 6, 7
0, 1, 2, 8, 3, 5, 4, 6, 9, 7
0, 1, 2, 8, 3, 4, 5, 6, 9, 7
0, 1, 2, 3, 8, 4, 5, 6, 9, 7
0, 1, 2, 3, 8, 4, 5, 6, 7, 9
0, 1, 2, 3, 4, 8, 5, 6, 7, 9
0, 1, 2, 3, 4, 5, 8, 6, 7, 9
0, 1, 2, 3, 4, 5, 6, 8, 7, 9
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
ソート終了
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

§2.3 単純挿入法・挿入ソート (Insertion Sort)

単純挿入法とは、ソート済みのデータからソートするデータを入れるべき場所を探し、以降のデータを後ろにずらすことで場所を空けてデータを挿入するという作業を繰り返すことによりソートを行うものです。 単純挿入法は、安定性のあるソート、内部ソートのアルゴリズムです。

単純挿入法
using System;

public class InsertionSort {
  static void Main()
  {
    int[] data = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};

    // 並べ替える前の並びを表示
    Print(data);

    Console.WriteLine("ソート開始");

    // 単純挿入法による並べ替え
    for (int i = 1; i < data.Length; i++) {
      if (data[i - 1] > data[i]) {
        // データが一つ前のデータより小さい場合、以降のデータを後ろにずらしていく
        int temp = data[i];
        int j;

        for (j = i; j > 0 && data[j - 1] > temp; j--) {
          data[j] = data[j - 1];
        }

        // ずらした結果空いた部分にデータを入れる
        data[j] = temp;

        Print(data);
      }
    }

    // 並べ替えた後の並びを表示
    Console.WriteLine("ソート終了");

    Print(data);
  }

  static void Print(int[] data)
  {
    Console.WriteLine(string.Join(", ", Array.ConvertAll(data, d => d.ToString())));
  }
}
実行結果
8, 3, 5, 4, 9, 2, 6, 0, 7, 1
ソート開始
3, 8, 5, 4, 9, 2, 6, 0, 7, 1
3, 5, 8, 4, 9, 2, 6, 0, 7, 1
3, 4, 5, 8, 9, 2, 6, 0, 7, 1
2, 3, 4, 5, 8, 9, 6, 0, 7, 1
2, 3, 4, 5, 6, 8, 9, 0, 7, 1
0, 2, 3, 4, 5, 6, 8, 9, 7, 1
0, 2, 3, 4, 5, 6, 7, 8, 9, 1
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
ソート終了
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

§2.4 クイックソート (Quick Sort)

クイックソートとは、データから適当な値を選び出し、その値を中心にして大小に分けていくという作業を繰り返すことによりソートを行うものです。 クイックソートは、安定性のないソートアルゴリズムです。

この例では再帰によってクイックソートを実装していますが、データ数が多い場合はその分だけ再帰的に呼び出されるので注意が必要です。 再帰を使った実装では再帰のために領域が必要であるとみることもできますが、一般的には内部ソートとみなされます。

クイックソート
using System;

public class QuickSort {
  static void Main()
  {
    int[] data = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};

    // 並べ替える前の並びを表示
    Print(data);

    Console.WriteLine("ソート開始");

    // クイックソートによる並べ替え
    QSort(data, 0, data.Length - 1);

    // 並べ替えた後の並びを表示
    Console.WriteLine("ソート終了");

    Print(data);
  }

  // クイックソートの実装
  static void QSort(int[] data, int left, int right)
  {
    int j = left; // データの左端を仮の基準点とする
    int temp;

    for (int i = left + 1; i <= right; i++) {
      if (data[i] < data[left]) {
        // 基準点の値よりも小さい値を前方に移動する
        j++;

        temp = data[j];
        data[j] = data[i];
        data[i] = temp;
      }
    }

    // 仮に置いた基準点の値を新しい基準点に置く
    temp = data[left];
    data[left] = data[j];
    data[j] = temp;

    Print(data);

    // 新しい基準点の位置で範囲を2分割する

    // 基準点の左側に要素がある場合は、さらにその範囲内で並べ替えを行う
    if (left < j - 1)
      QSort(data, left, j - 1);

    // 基準点の右側に要素がある場合は、さらにその範囲内で並べ替えを行う
    if (j + 1 < right)
      QSort(data, j + 1, right);
  }

  static void Print(int[] data)
  {
    Console.WriteLine(string.Join(", ", Array.ConvertAll(data, d => d.ToString())));
  }
}
実行結果
8, 3, 5, 4, 9, 2, 6, 0, 7, 1
ソート開始
1, 3, 5, 4, 2, 6, 0, 7, 8, 9
0, 1, 5, 4, 2, 6, 3, 7, 8, 9
0, 1, 3, 4, 2, 5, 6, 7, 8, 9
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
ソート終了
0, 1, 2, 3, 4, 5, 6, 7, 8, 9