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<Integer> 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<Integer> 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
トラックバック URL:
https://perltips.twinkle.cc/trackback/297