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

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

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

スポンサーリンク



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

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

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

ソートアルゴリズム並べ方
バブルソート隣り合う2つのデータを逐次交換。
基本選択法データから最大・最小を探すことの繰り返し。
基本挿入法部分的に整列されたデータの適切な位置へ挿入。

基本的なソート

基本的なソートプログラムを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

バブルソート

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

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
スポンサーリンク





カテゴリー

今週よく読まれている記事

  1. 学会・会議で英語が絶望的にできなくて困るケース | オンライン開催で「英語力のなさ」を痛感した場合の対処法

    学会・会議で英語ができなくてに困るケース学会やイベント・会議などが、オンラインで開催される…
  2. r tidyverse 使い方 | 列 filter 絞り込み select関数 – dplyrパッケージ

    tidyverseで1つのデータフレームの列の絞り込みは、dplyrパッケージのselect関数を…
  3. プログラミングで疲れた脳をリフレッシュ 〜 鬼滅の刃「感動」と「やる気アップ」でストレス発散!

    ストレス発散は鬼滅で。「50%OFF」で読む!脳のパフォーマンスを上げるには、適度な休憩と…
  4. AWS ディスク容量不足 新しいボリュームを追加する

    バイオインフォマティクスでは大きなファイルを扱うことがあるので、ディスク不足に陥ることがあります。…
  5. 「知っている」と「知らない」とでは、もしものとき、大違いになる – コロナうつ対策

    コロナうつなどという言葉を聞くようになりましたが、派遣切り、解雇、リストラは、これから本格化します…

人気記事

  1. R言語

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

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

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

おすすめ記事

  1. シェルスクリプト

    シェルスクリプト | ファイル存在チェック・空ファイルチェック
    bashでスクリプトを作成するときに、よく使うのがファイル…
  2. R言語, グラフ

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

    bash 部分文字列・置換・長さ・連結・分割の文字列処理
    bashのよく使う文字列処理、部分文字列・置換・連結・長さ…