Algorithms/Sorting/Bubble Sort

Bubble Sort

バブルソート, 単純交換ソート, バカソート

Outline

バブルソートは隣り合う要素の順序が狂っていればそれを直しながらソートしていく方法である.このソートはバカソートと呼ばれるが、それはある要素を正しい位置に置くまでに
多くの要素交換を行わなければならないからである.また、バカソートというくせに、挿入ソートや選択ソートに比べると直感的に分かりづらいので、まったく使い道のないアルゴリズムである.

Program

サイズnの配列dataに対してバブルソートを行う関数.

void bubble_sort(int data[], int n) {
  for(int i = n - 1 ; i >= 1 ; i--) {
    for(int j = 0 ; j < i ; j++) {
      if(data[j] > data[j + 1]) {
        swap(data[j], data[j + 1]);
      }
    }
  }
}

Consideration

#mimetex( \Theta(n^2) )