アルゴリズム初心者向けの基礎と入門(C#, Pythonとか)

バブルソートとは

数あるソートアルゴリズムで真っ先に紹介されるアルゴリズムが、おそらくこのバブルソートです。隣り合う要素を比較しながら整列させていくことで、最終的にソートされたデータが得られます。アルゴリズムが単純で実装も容易ですが、要素の比較・交換の回数が多く、処理速度は低速になります。

ソートの特性としては、安定 な 内部 ソートです。処理速度は低速ですが、このアルゴリズムをベースに様々なアルゴリズムが派生しています。

バブルは泡の意味で、ソートの過程での値の動きが泡のように見えることが、名前の由来です。

バブルソートのシミュレーション

背景色が黄色のタイミングで比較が実行されています。ソート済のデータは水色になります。 動かしてみると、小さな値から順に配列の前のほうに降りてくるのが分かります。

アルゴリズムの解説

「n番目の要素をn-1番目の要素と比較し交換する」これを配列の末尾から先頭要素まで繰り返します。すると全データの最小値が配列の先頭要素まで降りてきます。さらにこれらを配列の要素数分繰り返すと、小さな値から順にソート済の位置に移動し、最終的には昇順(降順)に整列します。

サンプルコード

C#

public static void BubbleSort<T>(T[] array) where T : IComparable<T>
{
    int n = array.Length;
    // 最終要素を除いて全て比較する
    for (int i = 0; i < n - 1; i++)
    {
        // 最終要素から、現在比較中の要素までループ
        // このループが終われば array[i] にはソート済のデータが入っている
        for (int j = n - 1; i < j; j--)
        {
            // j番目の要素が一つ前の要素より小さければスワップ
            if (array[j].CompareTo(array[j - 1]) < 0)
            {
                Swap(ref array[j], ref array[j - 1]);
            }
        }
    }
}

public static void Swap<T>(ref T a, ref T b)
{
    var tmp = a;
    a = b;
    b = tmp;
}

Python

def bubble_sort(array):
    n = len(array)
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if array[j] < array[j-1]:
                tmp = array[j]
                array[j] = array[j-1]
                array[j-1] = tmp