Aritalab:Lecture/Algorithm/Sorting

概要

ここでは種々の整列（ソーティング）アルゴリズムを紹介します。 アルゴリズムの理解が目的のため、プログラムは整数配列を入力として受け取り、配列の中身を整列させるものとします。 プログラム言語はJavaを想定しており、 また配列の要素 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 シェルソート

挿入ソート法は常に隣どうしだけをみて挿入位置を決めたため、効率が悪くなりました。Shellは数個とびに挿入ソート法をかけて大雑把にソートしてから、次第に間隔をせばめて完全にソートする手法を考案しました。 類似の手法がコムソート (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²) になります。

Quick Sort クイックソート

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

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

static public 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 public 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² ) になります。

Merge Sort マージソート

クイックソートと同じく分割統治法に基づきます。クイックソート がトップダウンに分けていくのに対してボトムアップにマージします。 ソートする配列と同サイズの配列スペースを要しますが、並び順を変えないstableソートで有用です。 外部記憶を用いたソートによく用いられます。

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

public 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);
}

public 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[p] = A[left] = A[p)
    A[right] = tmp[right++];
}

}