バブルソートとは : JavaA2Z

バブルソート

日本語	泡並び替え
英語	bubble sort、bubblesort
ふりがな	ばぶるそーと
フリガナ	バブルソート

泡が浮かび上がるように比較していくソート。
ソートのアルゴリズムのひとつ。
ソートのアルゴリズムの中でも、最も簡単なアルゴリズム。その分処理時間は長い。
　
バブルソートのアルゴリズムは、配列の末端から「隣との比較」を先頭方向へ行っていく、というものである。
配列の「右端」と「右端のひとつ左」を比較し「右端のひとつ左」の方が大きければ「右端」と入れ替える。こうすると「右端のひとつ左」<「右端」と、並んだ要素の左側が小さい値となる。
これを右端から順に行うと、左端に「一番小さな値」が来る。
ここまでを1セットとし、「配列のサイズ-1」まで行う。ただし、2セット目以降は左端までは行わず、前回のセットで「最小の値」がセットされた位置のひとつ右まで入れ替えていく。前回のセットで「最小の値」がセットされている位置にはもうすでに「最小の値」があるためである。
　
1セットごとの「一番小さな値が昇ってくる」姿が「泡が上へと上がっていく」ように見えるため「バブルソート」と呼ばれる。
　
比較方法が普通のため、処理に時間が掛かる。
安定ソートである、仕組みが簡単、というメリットはあるが、バブルソートに限らず、自分でソートのアルゴリズムを作製するのはバグの元となりなやすい。
特別な場合を除き、Arrays クラスのsort()メソッドでソートする方がいいだろう。

参考サイト

J2SE Array#sort()

(KAB-studioからのおしらせです)

// Sample.java
public class Sample
{
    public static void main( String[] args )
    {
        // 出力する配列を用意します。
        int[] ints = new int[]{ 4, 9, 3, 5, 8 };

        for( int iF1 = 0; iF1 < ints.length; ++iF1 )
        {
            System.out.print( ints[iF1] + ", " );
        }
        System.out.println();
        // 4, 9, 3, 5, 8,

        // バブルソートします。
        bubbleSort( ints );

        for( int iF1 = 0; iF1 < ints.length; ++iF1 )
        {
            System.out.print( ints[iF1] + ", " );
        }
        System.out.println();
        // 3, 4, 5, 8, 9,
    }

    /**
    *   バブルソートします。
    */
    private static void bubbleSort( int[] array )
    {
        // 「入れ替え先」のループです。
        // 左端から1ずつ増えて、右端のひとつ前まで進みます。
        for( int iOut = 0; iOut < array.length - 1; iOut++ )
        {
            // 右端から左端方向へのループです。
            // ただし「入れ替え先」までです。
            for( int iIn = array.length - 1; iOut < iIn; iIn-- )
            {
                // ある要素と、その要素の「ひとつ左」を比較します。
                if( array[iIn] < array[iIn - 1] )
                {
                    // 「ひとつ左」の方が大きいので入れ替えます。
                    int iTemp = array[iIn];
                    array[iIn] = array[iIn - 1];
                    array[iIn - 1] = iTemp;
                }
            }
        }
    }
}

/*
この例でのソートの流れ。

■1セット目
      _ _
4 9 3 5 8
↓
4 9 3 5 8
    _ _
4 9 3 5 8
↓
4 9 3 5 8
  _ _
4 9 3 5 8
↓
4 3 9 5 8
_ _
4 3 9 5 8
↓
3 4 9 5 8

■2セット目
      _ _
3 4 9 5 8
↓
3 4 9 5 8
    _ _
3 4 9 5 8
↓
3 4 5 9 8
  _ _
3 4 5 9 8
↓
3 4 5 9 8

■3セット目
      _ _
3 4 5 9 8
↓
3 4 5 8 9
    _ _
3 4 5 8 9
↓
3 4 5 8 9

■4セット目
      _ _
3 4 5 8 9
↓
3 4 5 8 9

※5セット目はありません。
　右端と右端から2番目を入れ替えた段階で、右端には
「一番大きな値」がセットされていることになるからです。
*/

// Sample.java
public class Sample
{
    public static void main( String[] args )
    {
        // 出力する配列を用意します。
        int[] ints = new int[]{ 4, 9, 3, 5, 8 };

        for( int iF1 = 0; iF1 < ints.length; ++iF1 )
        {
            System.out.print( ints[iF1] + ", " );
        }
        System.out.println();
        // 4, 9, 3, 5, 8, 

        // バブルソートします。
        bubbleSort( ints );

        for( int iF1 = 0; iF1 < ints.length; ++iF1 )
        {
            System.out.print( ints[iF1] + ", " );
        }
        System.out.println();
        // 3, 4, 5, 8, 9, 
    }

    /**
    *   バブルソートします。
    */
    private static void bubbleSort( int[] array )
    {
        // 「入れ替え先」のループです。
        // 左端から1ずつ増えて、右端のひとつ前まで進みます。
        for( int iOut = 0; iOut < array.length - 1; iOut++ )
        {
            // 右端から左端方向へのループです。
            // ただし「入れ替え先」までです。
            for( int iIn = array.length - 1; iOut < iIn; iIn-- )
            {
                // ある要素と、その要素の「ひとつ左」を比較します。
                if( array[iIn] < array[iIn - 1] )
                {
                    // 「ひとつ左」の方が大きいので入れ替えます。
                    int iTemp = array[iIn];
                    array[iIn] = array[iIn - 1];
                    array[iIn - 1] = iTemp;
                }
            }
        }
    }
}

/*
この例でのソートの流れ。

■1セット目
      _ _
4 9 3 5 8 
↓
4 9 3 5 8 
    _ _
4 9 3 5 8 
↓
4 9 3 5 8 
  _ _
4 9 3 5 8 
↓
4 3 9 5 8 
_ _
4 3 9 5 8 
↓
3 4 9 5 8 

■2セット目
      _ _
3 4 9 5 8
↓
3 4 9 5 8
    _ _
3 4 9 5 8
↓
3 4 5 9 8
  _ _
3 4 5 9 8
↓
3 4 5 9 8

■3セット目
      _ _
3 4 5 9 8
↓
3 4 5 8 9
    _ _
3 4 5 8 9
↓
3 4 5 8 9

■4セット目
      _ _
3 4 5 8 9
↓
3 4 5 8 9

※5セット目はありません。
　右端と右端から2番目を入れ替えた段階で、右端には
「一番大きな値」がセットされていることになるからです。
*/