バブルソート

バブルソート

ゲーム開発ではランキングや高速化などで値をソートする必要が必要になることが多々あります。
そんな時に使える一番原始的なソートアルゴリズムにバブルソートがあります。

アルゴリズム

バブルソートのアルゴリズムは至極単純です。

先頭から順にそれ以降のデータと値の比較を行っていきデータを入れ替えていくだけです。
※昇順、降順のどちらで比較するかによって符号の向きが逆になります。

実装方法

int型のデータをソートする場合には下記のようになります。

// バブルソートを使ったソート
void BubbleSort(int* pData, int count)
{
	for (int i = 0; i < count; i++)
	{
		for (int j = count-1; i < j; j--)
		{
			if (pData[i] <= pData[j]) continue;
			int temp = pData[i];
			pData[i] = pData[j];
			pData[j] = temp;
		}
	}
}

これでcount個のint型データが入ったpDataがソートされます。

使い方

実際に使う時は下記のようになります。

// ソートするデータリスト
int data[] = { 5, 15, 3, 6, 7, 8, 20, 31 };
// ソートテスト
void SortTest()
{
	int count = sizeof(data) / sizeof(*data);
	// バブルソート
	BubbleSort(data, count);
	for( int i=0; i < count; i++ )
	{
		printf("%d:%d\n", i, data[i]);
	}
}

これでdataの配列をソートして結果を表示します。

今回の場合は下記のような結果になります。

0:3
1:5
2:6
3:7
4:8
5:15
6:20
7:31

ソートのサンプル動画

バブルソートの流れを動画にしました。
今回の実装はこのような流れでソートがおこなわれています。

 

ソート処理はゲーム内でも多用する処理です。
バブルソートは速度的に多用はしませんが、
ソートの基本知識として必ず理解しておきましょう。