C言語 シェルソート スクリプトの書き方

バイオインフォ道場、くまぞうです。

アルゴリズムには、無駄がなく効率的に処理をおこなうための様々な工夫があります。バイオインフォマティクスでは大きなデータを扱うことが多いので、様々なアルゴリズムの考え方を身につけておくと何かの役に立つかもしれません。尚、以前紹介しましたソートの基本形にかわって、代表的な改良形ソートの１つであるシェルソートを紹介します。

ソートアルゴリズムは、比較回数・交換回数により、所要時間に大きな差をうみます。その差は、データ量が多くなると圧倒的なものになります。計算量は、ビッグＯ記法で表現されます。基本形は$$O(n^2)$$・改良形は$$O(nlog_2n)$$や$$O(n^{1.2})$$のオーダーになります。$$O(n^2)$$は、データ数がn倍になると、計算量がn^2になることを示します。実際、データが１００倍になるだけで〜４０倍、１００００倍になると〜２０００倍もの差になります。仕組みを理解するには基本形が良いですが、実際に使用する場合は改良型を使うほうが現実的です。

シェルソート

考え方

シェルソートは、挿入ソートを改良したアルゴリズムです。挿入ソートは、整列済みの数列に対して効率よく整列を行うことが出来ることを活かした整列アルゴリズムです。数列を「飛び飛びの部分数列」に分け、それぞれを基本挿入法でソートします。それぞれ部分数列をソートしつつ、全体をソートする流れです。

飛び飛びの部分数列

シェルソートは「飛び飛びの部分数列」に分けるgapの分け方がいくつかありますが、$$1, 4, 13, 40, 121, 364, \cdots$$という数列でデータ数を超えない最大数を選ぶと良いとされます。これらは、$$h_{i+1} = 3h_i+1$$で表されます。

shell_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define N 20

int* gaps(int* c);

void main(void)
{
  int data[N];
  int i, j, k, h;

  // サンプルデータ生成
  for (i=0; i<N; i++) data[i] = rand()%100;

  for (i=0; i<N; i++) printf("%d ", data[i]);
  printf("\n");

  // どのような分割が良いか？
  int c;
  int *g = gaps(&c);

  int gap;
  for (h=c-1; h>=0; h--) {
    gap = g[h];
    // gap部分数列をソートする
    for (k=0; k<gap; k++) {
      for (i=k+gap; i<N; i+=gap){
  	for (j=i-gap; j>=k; j-=gap) {
  	  if(data[j]>data[j+gap]) {
  	    data[j+gap] ^= data[j];
  	    data[j] ^= data[j+gap];
  	    data[j+gap] ^= data[j];
  	  }
  	  else {
  	    break;
  	  }
  	}
      }
    }
  }
  for (i=0; i<N; i++) printf("%d ", data[i]);
  printf("\n");

  free(g);
}

int* gaps(int* c)
{
  *c = (int)(log((double)N/1.0)/log(3.0));
  int *g = malloc(sizeof(int) * (*c));

  int i, n;
  for (i=0,n=1; (n<N || i<*c); n=n*3+1){
    g[i] = n;
    i++;
  }
  return g;
}

$ gcc shell_sort.c -o shell_sort
$ ./shell_sort 
83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 
15 21 26 26 27 35 36 40 49 59 62 63 72 77 83 86 86 90 92 93