【C言語】バブルソートを実装してみた

ソースコード

#include <stdio.h>
// バブルソートを実行するプログラム
// 左から小さい順に並べる
int comparison(int num1, int num2);
void swap(int *num1, int *num2);
void enumerate(int array[], int size);
void bubbleSort(int array[], int size);

int main(void) {
  int array[] = {42, 7, 19, 93, 5, 23, 76, 1, 58, 34};
  int size = sizeof(array) / sizeof(array[0]);
  enumerate(array, size);
  bubbleSort(array, size);
  enumerate(array, size);
  return 0;
}

int comparison(int num1, int num2) {
  if (num1 > num2) {
    return 1;
  } else {
    return 0;
  }
}

void swap(int *num1, int *num2) {
  int tmp = 0;
  tmp = *num1;
  *num1 = *num2;
  *num2 = tmp;
}

void enumerate(int array[], int size) {
  for (int i = 0; i < size; i++) {
    printf("%d ", array[i]);
  }
  printf("\n");
}

void bubbleSort(int array[], int size) {
  int flag = 0;
  for (int i = 0; i < size - 1; i++) {
    for (int j = 0; j < size - 1 - i; j++) {
      flag = comparison(array[j], array[j + 1]);
      if (flag == 1) {
        swap(&array[j], &array[j + 1]);
      }
    }
  }
}

出力結果

42 7 19 93 5 23 76 1 58 34 
1 5 7 19 23 34 42 58 76 93 

メモ

swap関数

定義のときはポインタ(*num1, *num2)を使う。
呼び出したいときはアドレス(&array[ j ], &array[ j+1 ])を使う。

enumerate関数

sizeは引数で指定する。
関数の中で「sizeof(array)/sizeof(array[0])」としてはいけない。

計算量

最悪の場合も平均も$${O(n^2)}$$です。
最良の場合はすでに整列している場合で$${O(n)}$$です。

計算量の考え方

配列の要素数を$${n}$$として、
$${n + (n - 1) + (n - 2) + … + 2 + 1 = \frac{n(n+1)}{2}}$$
計算量を考える場合、係数は大きな問題にならないので、$${n^2 + n}$$
加えて、最高次の項も大きな問題にならないので、$${n^2}$$
そういう訳で$${O(n^2)}$$です。

補足

係数とか次数が小さい項をなんで無視していいのかわからないときは具体例を考えるとしっくりきます。
$${n = 1000}$$のとき、$${n^2 = 1000000}$$に比べたら$${n = 1000}$$って小さいですよね。正確な値よりも桁数の方が役に立ちそう。
あと、$${2n = 2000}$$と$${n = 1000}$$ってそんなに違う？って思いますよね。
思いますよね？

感想

バブルソートの勉強はもちろん、関数の定義の仕方(配列を引数にするには？など)、ポインタの初歩を学べました。面白かったです。