C言語 バブルソート,基本選択法 スクリプトの書き方

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

無駄がなく効率的なアルゴリズムには様々な工夫があります。バイオインフォマティクスでは大きなデータを扱うことが多いので、様々なアルゴリズムの考え方を身につけておくと何かの役に立つかもしれません。尚、ソートプログラムはシンプルで結果が分り易く、良い課題の１つです。

色々なソートアルゴリズム

ソートは、データをある規則に従って並べ替えたり整列させたりすることです。ソートアルゴリズムには、色々な方法があります。それらは、比較回数・交換回数により、所要時間に大きな差をうみます。基本形にはバブルソートや基本選択法など、改良形にはシェルソートやヒープソートなどがあります。

基本的なソートアルゴリズム

基本的なソート

基本的なソートプログラムをC言語で書いてみました。

基本選択法

データから最大・最小を探すことを繰り返します。データから最小の値を探します。次に残されたデータから最小を探します。このことを残りのデータがなくなるまで繰り返します。

sort1.c

#include <stdio.h>

void main(void)
{
  int data[] = {6, 3, 12, 4, 1, 10, 9, 5, 8, 2};
  const int size = sizeof(data) / sizeof(data[0]);
  int i, j;

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

  int min;
  int pos;
  for (i=0; i<size-1; i++) {
    min = data[i];
    pos = i;
    for (j=i+1; j<size; j++) {
      if (data[j]<min) {
	min = data[j];
	pos = j;
      }
    }
    if (i == pos) continue;

    data[pos] ^= data[i];
    data[i] ^= data[pos];
    data[pos] ^= data[i];
  }

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

$ gcc sort1.c -o sort1
$ ./sort1
6 3 12 4 1 10 9 5 8 2 
1 2 3 4 5 6 8 9 10 12

バブルソート

隣り合う２つのデータを逐次交換します。ある位置で、『「前のデータ」と「後ろのデータ」で比較して、「後ろのデータ」が小さければ交換する』を繰り返します。

sort2.c

#include <stdio.h>

void main(void)
{
  int data[] = {6, 3, 12, 4, 1, 10, 9, 5, 8, 2};
  const int size = sizeof(data) / sizeof(data[0]);
  int i, j, *x, *y;

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

  for (i=0; i<size-1; i++) {
    for (j=size-1; j>i; j--) {
      x = &data[j-1];
      y = &data[j];
      if (*y < *x) {
	*y ^= *x;
	*x ^= *y;
	*y ^= *x;
      }
    }
  }

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

$ gcc sort2.c -o sort2
$ ./sort2
6 3 12 4 1 10 9 5 8 2 
1 2 3 4 5 6 8 9 10 12