Javaのようなプログラムでは、ソート処理と呼ばれるデータの並び替えは頻出処理の1つです。
ソート用アルゴリズムの1つバブルソートについて、名前は聞いたことがあってもイマイチ内容を理解出来ていない方も多いのではないでしょうか。
本記事では、Javaプログラムをサンプルとして、バブルソートの実装方法について初心者向けに解説していきたいと思います。
目次
バブルソートって何？
まずはそもそもバブルソートとは何かといった基本的な知識からご紹介してきます。
ソートアルゴリズムの1つ
バブルソートはソートアルゴリズムの1種で、並び替えの過程で泡が浮かび上がるように処理が行われることからバブルソートと呼ばれています。
他にも日本語名では、「単純交換法」とも呼ばれ、名前の通りシンプルなアルゴリズムにより処理が行われます。
バブルソートの仕組み
バブルソートでは、隣り合った要素同士の大小を順番に比較していき整列させることで、昇順・降順の並び替えを行います。
配列の右端の値から隣の値と比較していき、値が大きい方を右側へ配置していくことで、最終的に一番小さな値が左端に配備される結果となります。
この作業を繰り返すことで、小さい値から大きい値へと整列させることが可能です。(降順の場合は処理を反対にするだけ)
バブルソートのメリット・デメリット
バブルソートはシンプルな分、メリット・デメリットがはっきりと分かれます。
バブルソートの仕組みでご紹介したように、シンプルである分、実装も簡単に行える点がメリットとなります。
デメリットとしては、1つずつ順番に比較を行っていく単純比較であるため、処理に時間が掛かる点です。
バブルソートのJavaサンプルコード
ではバブルソートの処理について、実際のJavaコードで確認してみましょう。
昇順サンプル
今回はシンプルに1~5の値を配列に格納して、バブルソートにより昇順に並べるサンプルです。
public class Main {
public static void main(String[] args) {
int[] data = {1, 4, 2, 5, 3};
for(int i=0; i < data.length-1; i++) {
for(int ii=0; ii data[ii+1]) {
int tmp = data[ii];
data[ii] = data[ii+1];
data[ii+1] = tmp;
}
}
}
for(int i = 0; i < data.length; i++) {
System.out.println(data[i]);
}
}
}
実行した結果が下記です。
1 2 3 4 5
昇順コード解説
int[] data = {1, 4, 2, 5, 3};
まず5行目で今回並び替えを行うデータを配列として格納しています。
for(int i=0; i < data.length-1; i++) {
for(int ii=0; ii data[ii+1]) {
int tmp = data[ii];
data[ii] = data[ii+1];
data[ii+1] = tmp;
}
}
}
7行目から14行目が、今回のメインとなるバブルソートを実施している部分で、2重ループの中でデータの大小比較を行いながら並び替えを行っています。
for(int i = 0; i < data.length; i++) {
System.out.println(data[i]);
}
18~20行目は、バブルソートで並び替えを行ったデータをコンソールに順番に出力しています。
降順サンプル
public class Main {
public static void main(String[] args) {
int[] data = {1, 4, 2, 5, 3};
for(int i=0; i < data.length-1; i++) {
for(int ii=0; ii < data.length-i-1; ii++) {
if(data[ii] < data[ii+1]) {
int tmp = data[ii];
data[ii] = data[ii+1];
data[ii+1] = tmp;
}
}
}
for(int i = 0; i < data.length; i++) {
System.out.println(data[i]);
}
}
}
実行した結果が下記です。
5 4 3 2 1
降順コード解説
if(data[ii] < data[ii+1])
降順への並び替えは9行目の条件比較で、大小を入れ替えるだけです。
この条件式で並び替える昇順と降順を切り替えて、データを整列させることが出来ます。
バブルソートに限らず基本はJavaの標準メソッドを利用する
Javaでバブルソートを実装する方法についてご紹介してきましたが、基本的にはJava標準で提供されているソート用のメソッドを利用して並び替えは行います。
簡単にJavaのArraysクラスから提供されているsortメソッドについてもご紹介しておきます。
昇順サンプル
バブルソートで使用したサンプルコードをArraysクラスのsortメソッドで書き換えてみましょう。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] data = {1, 4, 2, 5, 3};
Arrays.sort(data);
for(int i = 0; i < data.length; i++) {
System.out.println(data[i]);
}
}
}
9行目の「Arrays.sort」で昇順への並び替えが実施されます。
降順サンプル
同じく降順サンプルもsortメソッドを使用して書き換えてみます。
import java.util.Arrays;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
Integer[] data = {1, 4, 2, 5, 3};
Arrays.sort(data, Collections.reverseOrder());
for(int i = 0; i < data.length; i++) {
System.out.println(data[i]);
}
}
}
10行目でsortメソッドの第２引数に、CollectionsクラスのreverseOrderメソッドを指定することで降順への並び替えが行えます。
8行目で配列データを定義する際、int型ではなくInteger型のクラスを利用する必要がある点に注意してください。
さいごに: ソートアルゴリズムの基本バブルソートをJavaプログラムで試してみよう
本記事では、ソートアルゴリズムの基本ともいえるバブルソートについて、Javaのサンプルプログラムを掲載しながら実装方法についてご紹介してきました。
バブルソートは単純な並び替え処理のため、アルゴリズムに苦手意識を持っている方にも学習しやすい内容となっています。
まずは1つずつの処理の役割を理解して、どのようにバブルソートによる並び替えが行われているのかしっかりと把握出来るように学習していきましょう。
