Algorithms/Sorting/Shell Sort

Shell Sort

シェルソート

Outline

シェルソートはInsertion Sort?を少しだけ拡張したソーティングアルゴリズムである.
挿入ソートがあまり速くないのは、ある要素を適切な位置に挿入するために
一つ隣の要素との交換を繰り返していくからである.
シェルソートでは、データ列をh要素間隔ずつ選んだ部分列をソートする.
こうすることで、ある要素の挿入すべき位置がその要素の現在位置から遠くにあっても
挿入ソートよりも高速に整列することができる.

シェルソートで重要になるのが、pをどのように決定するかであるが
これについてはいくつかの良い選択が分かっている.
良い増分列には&mimetex(h=3*h+1);というものがあり、
以下のプログラムではこの増分列を用いてる.
逆に悪い増分列もあり、例えば&mimetex(h=2*h);という増分列は
上記の増分列よりも効率が悪い.

Program

サイズnの配列dataに対してシェルソートを行う関数.

void shell_sort(int data[], int n) {
  int h = 1, j, v;

  while(3 * h + 1 < n) {
    h = 3 * h + 1;
  }

  while(h > 0) {
    for(int i = h ; i < n ; i++) {
      v = data[i];
      j = i;

      while(j >= h && data[j - h] > v) {
        data[j] = data[j - h];
        j -= h;
      }

      data[j] = v;
    }

    h /= 3;
  }
}

Consideration

シェルソートの実行時間は詳しく解析されていない.
何故なら、それは増分列に依存するからである.
上記の&mimetex(h=3*h+1);の増分列に対する実行時間は

#mimetex(\Theta(N(N \log_{2}N)^2))
であると予想されている.