バブルソートとは
隣と比べて、逆順なら入れ替える。
隣接する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)$