【C言語】交換法（又はバブルソート）による配列データの整列

ある程度プログラミングに慣れた人向けの練習問題の一つとして、整列アルゴリズム（ソート）の実装があります。

この記事では、交換法（バブルソートとも呼ばれる）を用いた配列データの整列をプログラムに実装する方法について解説しています。

交換法（バブルソート）の概要

プログラムを実装する前に、交換法（又はバブルソート）についての簡単な説明を行います。

交換法とは、配列データの要素を整列させる整列アルゴリズム（ソート）の一つです。

アルゴリズム

交換法（バブルソート）では、隣接する要素を比較し、逆順であればその位置を交換するという操作を行います。

長さNの配列が対象の場合、前述の操作を0番目からN-1番目まで、0番目からN-2番目まで…と処理範囲を狭めながら繰り返すことで対象の配列の要素を整列させることが可能です。

計算量

対象の配列の長さをNとすると、交換法では0番目からN-1番目、0番目からN-2番目…の各要素の比較・交換の最大実行回数はそれぞれN-1、N-2…回となります。

比較を行う回数の合計は(N(N-1)/2)回となり、O記法での計算量はO(N^2)です。

入力配列が整列された状態に近い場合は操作を行う回数が抑えられ、効率よく処理を行うことも可能ですが、他のソートに比べて交換回数が多いため、遅くなることが多いとされています。

実際にプログラムを作成してみる

早速ですが、実際にプログラムを作成していきます。

プログラム作成の手順

プログラム作成の手順は以下の通りです。

実装例

上記の手順に従ってプログラムを作成します。使用する言語はC言語です。

#include <stdio.h>

int main(void){
  int data[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int n, i, j, temp;

  /* 整列前のデータを表示する */
  printf("---bubble sort---\nBefore : ");
  for(n=0; data[n]!='\0'; n++){
    printf("%d ",data[n]);
  }

  /* 交換法（バブルソート）を用いてデータを整列する */
  i = n - 1;
  while(i > 0){
    for(j=0; j<=i-1; j++){
      if(data[j] > data[j+1]){
        temp = data[j];
        data[j] = data[j+1];
        data[j+1] = temp;
      }
    }
    i = i - 1;
  }

  /* 整列後のデータを表示する */
  printf("\nAfter  : ");
  for(n=0; data[n]!='\0'; n++){
    printf("%d ",data[n]);
  }

  return 0;
}

このプログラムを実行すると以下の出力結果が得られます。

---bubble sort---
Before : 9 8 7 6 5 4 3 2 1 
After  : 1 2 3 4 5 6 7 8 9 

この出力結果から無事に交換法（バブルソート）が実装できていることがわかります。

おすすめの記事

本記事を読まれた方には、以下の記事もおすすめします。

【中・上級者への道！】C言語の次に勉強するべきプログラミング言語は何？【オススメは○○】