バブルソート
ゲーム開発ではランキングや高速化などで値をソートする必要が必要になることが多々あります。
そんな時に使える一番原始的なソートアルゴリズムにバブルソートがあります。
アルゴリズム
バブルソートのアルゴリズムは至極単純です。
先頭から順にそれ以降のデータと値の比較を行っていきデータを入れ替えていくだけです。
※昇順、降順のどちらで比較するかによって符号の向きが逆になります。
実装方法
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
ソートのサンプル動画
バブルソートの流れを動画にしました。
今回の実装はこのような流れでソートがおこなわれています。
ソート処理はゲーム内でも多用する処理です。
バブルソートは速度的に多用はしませんが、
ソートの基本知識として必ず理解しておきましょう。