バブルソートとは
数あるソートアルゴリズムで真っ先に紹介されるアルゴリズムが、おそらくこのバブルソートです。隣り合う要素を比較しながら整列させていくことで、最終的にソートされたデータが得られます。アルゴリズムが単純で実装も容易ですが、要素の比較・交換の回数が多く、処理速度は低速になります。
ソートの特性としては、安定 な 内部 ソートです。処理速度は低速ですが、このアルゴリズムをベースに様々なアルゴリズムが派生しています。
バブルは泡の意味で、ソートの過程での値の動きが泡のように見えることが、名前の由来です。
バブルソートのシミュレーション
背景色が黄色のタイミングで比較が実行されています。ソート済のデータは水色になります。 動かしてみると、小さな値から順に配列の前のほうに降りてくるのが分かります。
アルゴリズムの解説
「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