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

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

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

スポンサーリンク



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

シェルソート

考え方

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

飛び飛びの部分数列

シェルソートは「飛び飛びの部分数列」に分ける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 
スポンサーリンク





ピックアップ記事

  1. R plot 重ねる方法3パターン サンプルでわかるRの使い方

    Rでグラフ (plot) を重ねる方法は、「単純な追加」「図に重ねて描画」「濃淡で重なり表現」の3…
  2. R subset関数 データフレームやmatrixからの条件指定による行・列の抽出

    R の subset関数は、データフレームやマトリックスから条件にマッチした部分集合を取り出します…
  3. tidyverse – distinct関数でデータフレームの重複行を削除 dplyrパッケージ

    tidyverseでデータフレームの重複行の削除を行う場合、dplyrパッケージのdistinct…

人気記事

  1. R データ型 - 文字列・ベクター・データフレーム・マトリックス など-, R言語, スクリプト

    R subset関数 データフレームやmatrixからの条件指定による行・列の抽出
    R の subset関数は、データフレームやマトリックスか…
  2. IGV, 解析ツール

    IGV 使い方 インストール〜便利な使い方まで | リファレンス・マッピングデータ・アノテーションを読み込んで表示しよう
    IGV(Integrative Genomics View…
  3. Excel, その他, 統計

    z-score 計算方法 エクセル(Excel) 編
    統計処理で、大きく変化しているなどの判断基準にも使われる値…

おすすめ記事

  1. awk, bash 文字列操作, シェルスクリプト

    bash 部分文字列・置換・長さ・連結・分割の文字列処理
    bashのよく使う文字列処理、部分文字列・置換・連結・長さ…
  2. R言語, グラフ

    R 使い方 軸・ラベルの調整(向き・サイズ・色など) グラフの描き方
    Rによるplot(グラフ)の描画は、手軽で大変便利です。た…
  3. bash 応用, シェルスクリプト

    シェル スクリプト ファイル存在チェック・空のファイルチェック
    bashでスクリプトを作成するときに、よく使うのがファイル…