Java で、バブルソートを実現する。

Java でバブルソートのアルゴリズムを考える。

今さらバブルソート・・・でもバブルソートっていったい何なんだ？と思いつつプログラマ業を営んでいる輩も多いかもしれない。バブルソートのアルゴリズムを知らなくても業務プログラムは組めるからね。

しかしバブルソートがソートの基本なのだ。まずは最も遅いアルゴリズムでソートを体感するのだ。計算量は O(n^2) となる。これはデータ量が n 個あったら、ソートするのに最大 n x n 回分の時間がかかるということだ。10個のデータなら 100回で済むために、今どきの Core 2 Duo マシンであればちょちょいのちょいなのだが、1,000,000個のデータを並べ替えるときの演算回数は 1,000,000 x 1,000,000 となるのであり、考えただけでもおそろしい。

import java.util.*; public class Sort { private Sort() { } public static void output(List data) { 
for(int i = 0, n = data.size(); i < n; i++)
System.out.print(data.get(i) + ", "); System.out.println(); } public static void bubble(List data) { 
for(int i = 0, n = data.size(); i < n; i++) {
  for(int j = 0, m = data.size() - 1; j < m; j++) {
    if(data.get(j) > data.get(j + 1)) {
      int tmp = data.get(j);
      data.set(j, data.get(j + 1));
      data.set(j + 1, tmp);
    }
  }
}
} public static void main( String[] args ) { 
List<Integer> data = new ArrayList<Integer>();

data.add(9); // 0
data.add(4); // 1
data.add(5); // 2
data.add(2); // 3
data.add(3); // 4
data.add(5); // 5
data.add(3); // 6
data.add(3); // 7
data.add(8); // 8
data.add(1); // 9

Sort.output(Sort.bubble(data));
} }

コンパイルは

javac Sort.java

実行は

java Sort

admin

Tags