C言語でバブルソート

バブルソートとは

隣と比べて、逆順なら入れ替える。

隣接する2項を比較し、$a_{i-1} < a_i$となるように、右から左に操作（入れ替え）する。この場合、最左端が最小値となる。

サンプルコード

ここでは、int型の配列を、バブルソートを用いて小さい順に並べ替える。

bubble_sort.c

# include<stdio.h>

/* 値を入れ替える関数 */
void swap (int *x, int *y) {
  int temp;    // 値を一時保存する変数

  temp = *x;
  *x = *y;
  *y = temp;
}

/* バブルソート */
void bubble_sort (int array[], int array_size) {
  int i, j;

  for (i = 0; i < array_size - 1; i++){
    for (j = array_size - 1; j >= i + 1; j--){   //　右から左に操作
      if (array[j] < array[j-1]) { swap(&array[j], &array[j-1]); }
    }
  }
}

int main (void) {
  int array[10] = { 2, 1, 8, 5, 4, 7, 9, 0, 6, 3 };
  int i;

  printf("Before sort: ");
  for (i = 0; i < 10; i++) { printf("%d ", array[i]); }
  printf("\n");

  bubble_sort(array, 10);

  printf("After sort: ");
  for (i = 0; i < 10; i++) { printf("%d ", array[i]); }
  printf("\n");

  return 0;
}

実行結果

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

性能

• 比較回数
  • $i=0,1,\cdots,n-1$のそれぞれについて、$j=i+1,i+2,\cdots,n$の$n-1$回の比較を行う。
  • 比較回数は$\sum^{n-1}_{i=0}{(n-1)}=n(n-1)/2\to O(n^2)$
• 交換回数
  • 最良の場合：0回
  • 最悪の場合：$n(n-1)/2$回$\to O(n^2)$