asaのブログ

プログラミングの勉強まとめ

ソートアルゴリズム(バブルソート)

 今日は、タイトルにあるソートを勉強しました。単純選択ソートとシェルソートまで進みましたが、ずらずら書くと冗長なので今回はバブルソートをまとめました。参考書は『明解javaによるアルゴリズムとデータ構造』です。

 

明解Javaによるアルゴリズムとデータ構造

明解Javaによるアルゴリズムとデータ構造

 

  

 バブルソート

 配列を昇順に並び替えます。走査は末尾からスタートします。隣り合う要素を比較して先頭側が大きければ(昇順なので)後ろの要素と交換します。

 参考書では配列の要素を入力させていましたが、やや面倒だと感じたのでmakeArrayメソッドを使って配列を作成しています。配列の確認は頻繁に行うのでcheckArrayメソッドを使いまわしています。swapとbublesortメソッドが今回の本体になります。

 

 最初 i = 0からスタートします。j は末尾からのスタートです。末尾とその前の要素を比較して、前の要素が大きければ交換します。j はデクリメントされて、次に末尾の一個前の要素とその前の要素を比較します。これは今、i = 0 なので、配列の先頭まで繰り返されて、最小の要素が先頭に来ます。

 j のループが回って、i がインクリメントされると i = 1となります。j の方の for 文は j > iとなっているので、末尾から2番目の要素までを比較して、2番目に小さい要素が先頭の次にやってきます。

 i は配列の末尾の1個手前までやって来て、ネストされているfor文で末尾とその手前の要素が比較されると j = n - 2、i = n - 2となり、ネストされたfor文を抜け、i も n - 1となりfor文を抜けます。

 終わってみると、配列は無事に昇順に並んでいます。