035-アルゴリズム-バブルソート【新人エンジニアが最初に覚えたい100のJava文法】 シミュレータあり
山崎講師ユーチューブ動画
アルゴリズム-バブルソートについて解説します。
ソースコード
public class ArgoSortBubble {
public static void main(String[] args) {
int[] data = { 30, 60, 70, 90, 20 };
sort(data);
for(int element : data){
System.out.print(element + " ");
}
}
public static void sort(int[] data) {
for(int i = data.length - 1; i > 0; i--){
for(int j = 0; j < i; j++){
if(data[j] > data[j + 1]){
int tmp = data[j + 1];
data[j + 1] = data[j];
data[j] = tmp;
}
}
}
}
}解説
バブルソートについて解説します。
プログラムを組み立てるときには、プログラムの解法が必要です。
プログラムの解法をアルゴリズムといいます。
代表的なアルゴリズムを覚えておくと、将来いろいろなプログラムを組むときのヒントになります。
ここでは、バブルソートを紹介します。
ソートは並び替えです。
サンプルコードでは、配列dataを並び替えるため、sortメソッドを呼び出し、for文で並び替えた後の要素を出力しています。
なお、for文では拡張for文が利用されているので、配列dataの要素を１つ取り出し、変数elementに入れることで繰り返し出力しています。
バブルソートは別名では隣接交換法とか基本交換法といいます。
隣り合う者同士を比較し、交換し、並び替えるという点がポイントです。
１回目の繰り返しでは、初期値がdata.length-1になっています。
これは範囲の右端が、要素数-1になるからです。
今回は配列の要素数が５ですから、変数iは４になります。
増減値がデクリメントになっていることにも注目してください。
変数iの値は、１ずつ減っていきます。比較する範囲を小さくしていく形になっています。
変数iが4の状態で、内側のfor文に突入します。初期値は変数j=0です。
終了条件は、ｊ<iになっていますから、１回目の繰り返しでは、j<4となり、ｊは3まで繰り返すことになります。
その中の条件分岐がバブルソートのポイントです。
Data[0]>data[0+1]となり、隣り合うものを比較して、インデックスの小さい方の値が大きければ、という分岐になりますifの中では、値を入れ替えています。
値を入れ替えるときには、一時的な変数、ここではtmpという変数を宣言しておき、入れ替える対象を一度待避させてから、変数の値を上書きしています。
１回目の繰り返しでは、30と60を比較して、入れ替えせず、次に60と70を比較して、入れ替えせず、70と90を比較して、入れ替えせず、90と20を比較して、入れ替えることになり、30 60 70 20 90という結果になり、変数jの繰り返しが終わります。
ここでは大事なことは90は決定ということです。
２回目の繰り返しでは、iの値が１減り、3になります。
変数jの範囲は、j<3となります。Jは2まで繰り返すことになります。
すると、30 60 70 20 までが交換する範囲という形になります。
そうすると、30と60、60と70、70と20を比較したときに交換が発生します。
そうすると、30 60 20 70 90という結果になります。
これを続けるとご覧のような結果になります。
このように、隣り合うものを比較し、比較する範囲を狭くしていくアルゴリズムがバブルソートです。
いかがでしょうか？
頭の中だけで考えずにぜひ書き出して考えてみてください。
以上、バブルソートについて解説しました。
このサンプルコードをJavaタッチタイプゲームとして遊ぶことができます。
投稿者プロフィール
- 代表取締役
-
セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します！
この記事に間違い等ありましたらぜひお知らせください。
最新の投稿
新入社員2024年11月23日「ゲシュタルト崩壊」とシステム開発- 新入社員2024年11月23日データベースでテーブル名やフィールド名にスペースを使うことは、一般的には推奨されていません
- 新入社員2024年11月23日「データにはなぜ型が必要なのか？」を2進数の観点から解説
- 新入社員2024年11月23日ディスプレイの解像度の意味と変更方法
