【Unity/C#】バブルソートとは(コード付き)

10371 ワード
C# ソート BubbleSort Unity C# テキストリンク

バブルソート(BubbleSort)とは？

バブルソートとは、与えられたデータを大小などの順序通りになるよう並べ替えるソーアルゴリズムの最も基本的な手法の一つです、端から順番に隣接する要素同士を比較・交換していくもの。

どんな動きをするの？

サンプルコード

    int[] BubbleSort(int[] _array)
    {
        //配列の回数分回す
        for (int i = 0; i < _array.Length; i++)
        {
            //配列の回数分回す
            for (int j = 0; j < _array.Length; j++)
            {
                //比較元より大きければ入れ替え
                if (_array[i] < _array[j])
                {
                    int x = _array[j];
                    _array[j] = _array[i];
                    _array[i] = x;
                }
            }
        }

        //Sortした結果を返す
        return _array;
    }

豆知識

実はこのバブルソートですがある一文字を変えるだけで劇的に入れかえ回数が変化します。

バブルソート改

for (int j = 0; j < _array.Length; j++)

この部分を

for (int j = i; j < _array.Length; j++)

とするだけですごく変わります！

実行結果

サンプルコード

    int[] BubbleSort(int[] _array)
    {
        //配列の回数分回す
        for (int i = 0; i < _array.Length; i++)
        {
            //配列の回数分回す
            for (int j = i; j < _array.Length; j++)
            {
                //比較元より大きければ入れ替え
                if (_array[i] < _array[j])
                {
                    int x = _array[j];
                    _array[j] = _array[i];
                    _array[i] = x;
                }
            }
        }

        //Sortした結果を返す
        return _array;
    }

まとめ

たった一か所変更しただけで半分近くに比較する回数を減らすことができました。
みなさんがバブルソートを使う場合このあたりを気を付けましょう。

追記

コメントにてもっと早くなる方法を記載してくださった方がいらっしゃいましたのでそちらの実行結果とソースをのせます！

 int[] BubbleSort(int[] _array)
    {
        //配列の回数分回す
        for (int i = 0; i < _array.Length; i++)
        {
            //配列の回数分回す
            for (int j = i+1; j < _array.Length; j++)
            {
                //比較元より大きければ入れ替え
                if (_array[i] < _array[j])
                {
                    int x = _array[j];
                    _array[j] = _array[i];
                    _array[i] = x;
                }
            }
        }

        //Sortした結果を返す
        return _array;
    }

まとめ2

少し早くなっていますね！
ソートってこういう少しの変更でも工程数が変化するのがいいですよね。