Aritalab:Lecture/Algorithm/Sorting

Revision as of 00:53, 20 October 2010

概要

ここでは種々の整列（ソーティング）アルゴリズムを紹介します。 アルゴリズムの理解が目的のため、プログラムは整数配列を入力として受け取り、配列の中身を整列させるものとします。 プログラム言語はJavaを用いており、以下のようなmain関数を用意すればそのまま実行できます。

public static void main(String[] args)
  {
    int s = 100;
    java.util.Random R = new java.util.Random();
    int[] A = new int[s];
    for(int i = 0; i < s; i++)
      A[i] = R.nextInt(s) + 1;
    ____Sort(A);
    for(int i=0; i < s; i++)
      System.out.print(A[i] + " ");
    System.out.println();
  }

また配列の要素 i, j を交換するサブルーチンを

static public void swap(int[] A, int i, int j)
  { int t = A[i]; A[i] = A[j]; A[j] = t; }

と書きます。

実用にならないアルゴリズム

Selection Sort

選択ソートでは、左から右へ順にスキャンして i 番目のスキャンにおける最小値を配列の i 番目に格納します。

static public void selectionSort(int[] A)
{
  for(int i=0; i < A.length; i++)
    {
      int min = i;
      for (int j=i+1; j < A.length; j++)
        if (A[j] < A[min]) min = j;
      swap(A, min, i);
    }
}

計算量は常に N²/2 で、何の工夫も無いアルゴリズムです。

Insertion Sort

挿入ソートは、人間がトランプのカードを並べて揃えるときに利用する方法に近い手法です。配列がほとんど整列されている場合に限り、配列長に比例する時間で終了します。

static public void insertionSort(int[] A)
{
  for(int i=1; i < A.length; i++)
    {
      int v = A[i];
      int j = i;
      while (j > 0 && A[j-1] > v)
        { A[j] = A[j-1]; j--; }
      A[j] = v;
    }
}

最悪計算量は n²/2 で、配列が逆順にソートされている場合に生じます。

Bubble Sort

バブルソートはファイルを先頭からスキャンし、隣り合う数の大小が狂っていたら交換します。

static public void bubbleSort(int[] A)
{
  for(int i=A.length; i > 0; i--)
    for(int j=1; j < i; j++)
      if (A[j-1] > A[j])
        swap(j-1, j);
}

最悪計算量は n²/2 で、配列が逆順にソートされている場合に生じます。

一般アルゴリズム

ここで紹介するのは数値以外のソートにも使えるアルゴリズムです。

Shell Sort

挿入ソート法は常に隣どうしだけをみて挿入位置を決めたため、効率が悪くなりました。Donald Shellは数個とびに挿入ソートをかけて大雑把にソートしてから、次第に間隔をせばめて完全にソートする手法（シェルソート）を考案しました^[1]。 類似手法がコムソート (Comb Sort) という名前で出回っていますが、「コムソートは（後述する）クイックソートより速い」といった議論は、計算量の観点からすると不毛です。

static public void shellSort(int[] A)
{
  int N = A.length;
  int h;
  for(h = 1; h < N/9; h = 3*h + 1);// スキップ幅決定
  for(; h > 0; h /= 3)
    for(int i = h; i < N; i++)
      { //幅hの挿入ソート
        int v = A[i];
        int j = i;
        while (j > (h-1) && A[j-h] > v)
          { A[j] = A[j-h]; j -= h; }
        A[j] = v;
      }
}

ここではスキップ幅に増分列...,1093,364,121,40,13,4,1を利用しています。 最悪計算量は挿入ソートに同じで O(n²) になります。

1. ↑ Shell D (1959) "A high-speed sorting procedure" Communications of the ACM 2(7), 30–32. doi:10.1145/368370.368387

Quick Sort

クイックソートはCAR Hoareによって考案された分割統治法によるアルゴリズムです^[1]。 実用上最速といわれます。クイックという名前は種々の解析がなされる前にHoare自身がつけました。

static public void quickSort(int[] A)
{ quickSort(A, 0, A.length-1); }

static void quickSort(int[] A, int left, int right)
{
  if (left >= right) return;
  int i = partition(A, left, right);
  quickSort(A, left, i-1);
  quickSort(A, i+1, right);
}

static void partition(int[] A, int left, int right)
{
  swap(A, left, (left+right)/2);
  int p = left;
  //A[left] ... A[p-1]にp未満の値、
  //A[p+1] ... A[right]にp以上の値をいれる
  for(int i = left + 1; i <= right; i++)
    if (A[i] < A[left])
      swap(A, ++p, i);
  swap(A, left, p);
  return p;
}

平均計算量は O(n log n)、最悪計算量は O( n² ) になります。

1. ↑ Hoare CAR (1962) "Quicksort" Computer Journal 5(1),10-15

Merge Sort

マージソートは、クイックソートと同じく分割統治法に基づきます。クイックソート がトップダウンに分けていくのに対し、ボトムアップにマージします。 ソートする配列と同サイズの配列スペースを要しますが、並び順を変えないstableソートで非常に便利です。アクセス領域が局所的なので、外部記憶装置上のデータにも適用できます。

static public void mergeSort(int[] A)
{
  int[] tmp = new int[A.length];
  mergeSort(A, tmp, 0, A.length);
}

static void mergeSort(int[] A, int[] tmp, int left, int right)
{
  if (left >= right) return;
  int p = (left + right)/2;
  mergeSort(A, tmp, left, p);
  mergeSort(A, tmp, p+1, right);
  merge(A, tmp, left, p+1, right);
}

static void merge(int[] A, int[] tmp, int left, int p, int right)
{
  int siz = right - left + 1;
  int left_end = p - 1;
  int t = left;
  while ((left <= left_end) && (p <= right))
    tmp[t++] = (A[left] <= A[p]) ? A[left++] : A[p++];
  while (left <= left_end)
    tmp[t++] = A[left++];
  while (p <= right)
    tmp[t++] = A[p++];
  for(int i=0; i < siz; i++)
    A[right] = tmp[right++];
}

マージソートはどんな入力に対しても正確に2分割します。分割の段数は log n ステップ、各段で長さ n のマージをおこなうので、常に O(n log n) 時間を要します。

Heap Sort

ヒープソートを説明する前に、二進（バイナリ）ヒープ構造について解説します。

二進ヒープ構造

1. 各頂点が二つの子頂点を持つ木で全ての葉の深さが等しいもの（完全二分木）から、葉の部分を右から0個以上取り去った形をもつ
2. 各頂点は値をもち、親頂点の値は子頂点の値より大きいか等しい

この構造は配列を用いて実現できます。添え字が 1 から始まる配列 A において、A[k] の子頂点をそれぞれ A[2k], A[2k+1] と解釈します。逆に A[k] の親頂点は A[k/2] になります。

二進ヒープは、与えられた配列の底辺からボトムアップに以下のプログラムで構築できます。

static public void buildHeap(int[] A, int N)
{
  for(int i = N/2; i >= 0; i--)
    heapify(A, N, i);
}

static public void heapify(int[] A, int N, int i)
{
  int left = 2*i;
  int right = 2*i + 1;
  // i, left, right のうち最大値を求める
  int max = i;
  if ((left < N) && (A[left] > A[max]))
    max = left;
  if ((right < N) && (A[right] > A[max]))
    max = right;
  if (max != i)
    {
      swap(A, i, max);
      heapify(A, N, max);
    }
}

配列 A に buildHeap 処理を施すと、 A[0] に最大値が入ります。

ヒープソート

一度サイズ N のヒープ構造を作成したら、A[0]にある最大値を配列の最後尾にswapし、後は配列長をひとつずつ短くして heapify 操作を繰り返します。

public static void heapSort(int[] A)
{
  int N = A.length;
  buildHeap(A, N);
  for(int i = N-1; i > 0; i--)
    {
      swap(A, 0, i);
      heapify(A, --N, 0);
    }
}

ヒープソートは再帰を使わず使用するメモリも少ないため、大きな集合のソートにも利用できます。速度はマージソートよりも少々遅くなります。最初のbuildHeapが　O(n log n) 時間。Heapify処理は高々 log n ステップで終了するので、最悪計算量は O(n log n) です。

Radix Sort

数字のソートであれば、線形時間アルゴリズムが多数知られています。 数字の桁数が有限と仮定して、桁毎にそろえる手法を一般に基数ソートといいます。 ただしソートできるのは整数値（浮動小数は無理）に限り、値の正負やバイト数をよく把握した上で適用しなくてはなりません。

桁の左側からそろえる場合と右側からそろえる場合でアルゴリズムが異なります。

Radix Exchange Sort

左側（大きい桁）からそろえていく場合を基数交換ソートといいます。 この手法は基本的にクイックソートと同じで、ピボットとして 2^b を用いるだけです。

static public void radixExchangeSort(int[] A)
{ radixExchangeSort(A, 0, A.length-1, 32-1); }

static void radixExchangeSort(int[] A, int left, int right, int b)
{
  if (left >= right || b < 0) return;
  int i = left;
  int j = right;
  while (i < j)
    {
      while ( (bit(A[i], b) == 0) && i < j ) i++;
      while ( (bit(A[j], b) == 1) && i < j ) j--;
      swap(A, i, j);
    }
  if (bit(A[right], b) == 0) j++;
  radixExchangeSort(A, left, j-1, b-1);
  radixExchangeSort(A,  j, right, b-1);
}

static int bit(int number, int b)
{  return (number >> b) & 0x1; }

各桁について配列全体をスキャンするので、最悪計算量は桁数を b とすると O(n b) になります。

Straight Radix Sort

右側（小さい桁）からそろえていく場合を直接基数ソートといいます。直接基数ソートで　d 桁目を揃えるとき、 d-1 桁までは既に揃えてあるので順番を崩さないように並び替えるところがポイントです。各桁ごとに配列 tmp と配列 A の間で丸コピーしていますが、配列を交互に使えば省略可能です。

public static void straightRadixSort(int[] A)
{
  final int bits = 32-1;
  final int letters = 2;
  int[] tmp = new int[A.length];
  for(int d = 0; d <= bits; d++)
    {
      int[] count = new int[letters];
      for(int i = 0; i < A.length; i++)
        count[bit(A[i], d)]++;
      for(int i = 0; i < letters-1; i++)
        count[i+1] += count[i];
      for(int i = A.length-1; i >= 0; i--)
        {
          tmp[ count[bit(A[i], d)]-1 ] = A[i];
          count[bit(A[i], d)]--;
        }
      for(int i = 0; i < A.length; i++)
        A[i] = tmp[i];
    }
}

計算量は、桁数を b とすると　O(n b) になります。 例えば、2ビットずつまとめて0-3の文字とみなす、3ビットずつまとめて0-7の文字とみなす、とすればcount配列のサイズを大きくする代わりに高速化が見込めます。 このまとめ方を使うと、文字数を c として O(n (b + c)) 時間になります。

Counting Sort

ラディックスソートとは異なりますが、類似の手法として、分布数えソートを紹介します。 ソート対象が1からkまでとわかっていれば、各要素に対して、その要 素より小さい値が何個あるかを数えることで、その要素が何番目に来るべきかを線形時間で計算できます。

static public void countingSort(int[] A, int maxValue)
{
  int[] tmp = new int[A.length];
  int[] C = new int[maxValue+1];
  for(int i = 0; i < A.length; i++)
    C[A[i]]++;
  for(int i = 1; i < maxValue+1; i++)
    C[i] += C[i-1];
  for(int i = 0; i < A.length; i++)
    tmp[C[A[i]]-- -1] = A[i];
  for(int i = 0; i < A.length; i++)
    A[i] = tmp[i];
}