Javaでバブルソートアルゴリズムを実装する方法–昇順と降順の例

公開: 2019-01-19
Javaでバブルソートアルゴリズムを実装する方法-昇順と降順の例

Bubble sort （誤ってsinking sortと呼ばれることもあります）は、ソートするリストを繰り返しステップ実行し、隣接するアイテムの各ペアを比較し、順序が間違っている場合はそれらを交換することで機能する単純なソートアルゴリズムです。

リストのパススルーは、スワップが不要になるまで繰り返されます。これは、リストがソートされていることを示します。 アルゴリズムの名前は、小さい要素がリストの一番上にbubbleする方法から付けられています。

要素を操作するために比較のみを使用するため、比較ソートです。 アルゴリズムは単純ですが、他のほとんどの並べ替えアルゴリズムは、大きなリストに対してより効率的です。

ロジックは単純です：

バブルソートでは、基本的に配列リストを最初の位置から（サイズ– 1）の位置までトラバースし、要素を次の位置と比較します。 次の要素が大きい場合にのみ、要素を次の要素と交換します。

Javaコードは次のとおりです。

  • ファイルCrunchifyBubbleSort.javaを作成します。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package crunchify . com . tutorials ;
 
import java . util . Arrays ;
 
/**
* @author Crunchify.com
* How to Implement Bubble sort algorithm in Java? Ascending and Descending Order Tutorial
*/
 
public class CrunchifyBubbleSort {
 
     public static void main ( String [ ] args ) {
         int [ ] crunchifyArray = { 15 , 3 , 9 , 7 , 19 , 8 , 1 , 5 } ;
         int [ ] crunchifyArrayDesc = { 20 , 13 , 19 , 37 , 69 , 18 , 21 , 5 , 99 } ;
         crunchifyPrint ( "Let's get started on Bubble Sort implementation in Java - by Crunchify \n" ) ;
         crunchifyPrint ( "============ Ascending Order result: " + Arrays . toString ( CrunchifyBubbleSortAscMethod ( crunchifyArray ) ) + "\n" ) ;
         crunchifyPrint ( "============ Descending Order result: " + Arrays . toString ( CrunchifyBubbleSortDescMethod ( crunchifyArrayDesc ) ) + "\n" ) ;
     }
 
     // Bubble Sort Algorithm in Ascending Order
     public static int [ ] CrunchifyBubbleSortAscMethod ( int [ ] crunchifyArr ) {
         for ( int i = 0 ; i < crunchifyArr . length - 1 ; i ++ ) {
 
             for ( int j = 1 ; j < crunchifyArr . length - i ; j ++ ) {
                 if ( crunchifyArr [ j - 1 ] > crunchifyArr [ j ] ) {
                     int temp = crunchifyArr [ j - 1 ] ;
                     crunchifyArr [ j - 1 ] = crunchifyArr [ j ] ;
                     crunchifyArr [ j ] = temp ;
                 }
             }
             crunchifyPrint ( "Iteration " + ( i + 1 ) + ": " + Arrays . toString ( crunchifyArr ) ) ;
         }
         return crunchifyArr ;
     }
 
     // Bubble Sort Algorithm in Descending Order
     public static int [ ] CrunchifyBubbleSortDescMethod ( int [ ] crunchifyArr ) {
         for ( int i = 0 ; i < crunchifyArr . length - 1 ; i ++ ) {
             for ( int j = 1 ; j < crunchifyArr . length - i ; j ++ ) {
                 if ( crunchifyArr [ j - 1 ] < crunchifyArr [ j ] ) {
                     int temp = crunchifyArr [ j - 1 ] ;
                     crunchifyArr [ j - 1 ] = crunchifyArr [ j ] ;
                     crunchifyArr [ j ] = temp ;
                 }
             }
             crunchifyPrint ( "Iteration " + ( i + 1 ) + ": " + Arrays . toString ( crunchifyArr ) ) ;
         }
         return crunchifyArr ;
     }
 
     // Simple log util
     private static void crunchifyPrint ( String result ) {
         System . out . println ( result ) ;
 
     }
}
 

Eclipseコンソールの結果：

EclipseコンソールまたはIntelliJIDEでバブルソートJavaプログラムの上を実行するだけで、次のような結果が表示されます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Let ' s get started on Bubble Sort implementation in Java - by Crunchify
 
Iteration 1 : [ 3 , 9 , 7 , 15 , 8 , 1 , 5 , 19 ]
Iteration 2 : [ 3 , 7 , 9 , 8 , 1 , 5 , 15 , 19 ]
Iteration 3 : [ 3 , 7 , 8 , 1 , 5 , 9 , 15 , 19 ]
Iteration 4 : [ 3 , 7 , 1 , 5 , 8 , 9 , 15 , 19 ]
Iteration 5 : [ 3 , 1 , 5 , 7 , 8 , 9 , 15 , 19 ]
Iteration 6 : [ 1 , 3 , 5 , 7 , 8 , 9 , 15 , 19 ]
Iteration 7 : [ 1 , 3 , 5 , 7 , 8 , 9 , 15 , 19 ]
============ Ascending Order result : [ 1 , 3 , 5 , 7 , 8 , 9 , 15 , 19 ]
 
Iteration 1 : [ 20 , 19 , 37 , 69 , 18 , 21 , 13 , 99 , 5 ]
Iteration 2 : [ 20 , 37 , 69 , 19 , 21 , 18 , 99 , 13 , 5 ]
Iteration 3 : [ 37 , 69 , 20 , 21 , 19 , 99 , 18 , 13 , 5 ]
Iteration 4 : [ 69 , 37 , 21 , 20 , 99 , 19 , 18 , 13 , 5 ]
Iteration 5 : [ 69 , 37 , 21 , 99 , 20 , 19 , 18 , 13 , 5 ]
Iteration 6 : [ 69 , 37 , 99 , 21 , 20 , 19 , 18 , 13 , 5 ]
Iteration 7 : [ 69 , 99 , 37 , 21 , 20 , 19 , 18 , 13 , 5 ]
Iteration 8 : [ 99 , 69 , 37 , 21 , 20 , 19 , 18 , 13 , 5 ]
============ Descending Order result : [ 99 , 69 , 37 , 21 , 20 , 19 , 18 , 13 , 5 ]
 
 
Process finished with exit code 0
 

バブルソートアルゴリズムの時間計算量とは何ですか？

  • Best caseシナリオを検討すると、 O(n)になります。
  • Worst caseシナリオを考えると、 O(n 2 )になります。

上記のプログラムで問題や例外が発生した場合はお知らせください。