zukaこんにちは。zuka（@beginaid）です。
本記事では，バブルソートの簡単な解説と実装例をお伝えしていきます。使用言語はJavaです。
本記事の概要
まずは，バブルソートのお気持ちをお伝えしていきます。続いて，実装方法を確認していきます。
バブルソートのお気持ち
実装方法
お気持ち
バブルソートは隣り合う要素同士をしらみつぶしに比較していくアルゴリズムです。配列の一番左側の要素から比較を始めて，配列の右側にソート済みの要素が溜まっていくイメージです。
さて，バブルソートの解説はWeb上に資料がたくさんあるため，以下では時間計算量を考えてみましょう。
配列の一番左の要素にとって，比較するべき要素は自分以外の$n-1$回です。この$n-1$回の比較が終わった後は，同様に配列の一番左の要素に注目して比較を繰り返していきます。一番右側の要素がソート済みであることに注意すると，比較回数は$n-2$回であることが分かります。
以上の操作を繰り返していくと，バブルソートの最悪時間計算量は$O(n^2)$であることが分かります。
\left\{(n-1) + (n-2) + \ldots + 1 \right\}&= \left\{\frac{n(n-1)}{2}\right\} \\
&= O(n^2)
\end{align}
バブルソートの最良時間計算量は$O(n)$です。なぜなら，整列済みの配列に対して「一度も要素の交換が行われなかったらループを抜ける」という処理を施すことで比較は最初の$n-1$回だけで済むからです。
バブルソートの空間計算量は$O(n)$です。なぜなら，$n$個の要素を格納する領域さえ確保してしまえばソートのアルゴリズムを適用できてしまうからです。英語Wikipediaにはtotalの空間計算量が$O(n)$と記載されています。
なお，配列内の要素をスワップする際に一時的に高々1個変数を用意しなくてはいけないことから，日本語Wikipediaには追加で要素数$n$以外に必要となるメモリ領域（auxiliary）として空間計算量が$O(1)$と記載されています。
- 最悪計算量：$O(n^2)$
- 最良計算量：$O(n)$
- 空間計算量：$O(n)$
※ただし空間計算量はtotalでありauxiliaryではない
実装
public class Main {
public static void main(String[] args) {
int[] arg = { 46, 3, 20, 39, 72, 79 };
int[] newArg = bubbleSort(arg);
// 以下は確認用コード
System.out.println("整列前の配列:");
for (int x : arg) {
System.out.print(String.format("%d ", x));
}
System.out.println("\n整列後の配列:");
for (int x : newArg) {
System.out.print(String.format("%d ", x));
}
}
static int[] bubbleSort(int[] arg) {
// argは配列の参照型でありデータを書き換えてしまうためディープコピーを行って新しいメモリ領域を確保する
int[] newArg = arg.clone();
// iはどこまで探索するかのインデックス。未整列部分の右端と考えてもよい。
for (int i = newArg.length - 1; i > 0; i--) {
// jは探索対象のインデックス。一番左端から右端のiに到達するまで繰り返す。
for (int j = 0; j < i; j++) {
// バブルソートの比較部分
if (newArg[j] > newArg[j + 1]) {
// スワップ用に一時的に保存しておく用の変数
int tmp = newArg[j];
// 以下でスワップを実行
newArg[j] = newArg[j + 1];
newArg[j + 1] = tmp;
}
}
}
return newArg;
}
}
コメント