苦しんで覚える C言語
苦しんで覚える C言語
バブルソート
整列(ソート)とは
整列(ソート)とは、でたらめに並べられたデータを順番通りに並び替えることです。
たとえば、次のように並び替えます。
この時、左に行くほど値が小さくなるソートを昇順と呼びます。
反対に、右に行くほど値が小さくなるソートは降順です。
また、ソートでは、安定性が必要なことがあります。
安定とは、ソート後に、同じ値のデータの並び順が変化しないことです。
たとえば、次はあるクラスの小テストの結果だとします。
これを安定な方法で並び替えると次のようになります。
同じ点数である剛田武と骨川スネ夫の前後関係はソートする前と同じです。
次は、非安定な方法で並び替えます。
同じ点数である剛田武と骨川スネ夫の前後関係が入れ替わっています。
場合によっては、同じ点数の人の並び順を保持する必要があり、
その場合には安定した方法を使わなければなりません。
たとえば、次のように並び替えます。
| ソート前 | 23 | 9 | 7 | 15 | 3 | 1 | 30 | 19 |
|---|---|---|---|---|---|---|---|---|
| ソート後 | 1 | 3 | 7 | 9 | 15 | 19 | 23 | 30 |
この時、左に行くほど値が小さくなるソートを昇順と呼びます。
反対に、右に行くほど値が小さくなるソートは降順です。
また、ソートでは、安定性が必要なことがあります。
安定とは、ソート後に、同じ値のデータの並び順が変化しないことです。
たとえば、次はあるクラスの小テストの結果だとします。
| 生徒名 | 点数 |
|---|---|
| 野比のび太 | 0 |
| 源静香 | 90 |
| 剛田武 | 50 |
| 骨川スネ夫 | 50 |
これを安定な方法で並び替えると次のようになります。
| 生徒名 | 点数 |
|---|---|
| 野比のび太 | 0 |
| 剛田武 | 50 |
| 骨川スネ夫 | 50 |
| 源静香 | 90 |
同じ点数である剛田武と骨川スネ夫の前後関係はソートする前と同じです。
次は、非安定な方法で並び替えます。
| 生徒名 | 点数 |
|---|---|
| 野比のび太 | 0 |
| 骨川スネ夫 | 50 |
| 剛田武 | 50 |
| 源静香 | 90 |
同じ点数である剛田武と骨川スネ夫の前後関係が入れ替わっています。
場合によっては、同じ点数の人の並び順を保持する必要があり、
その場合には安定した方法を使わなければなりません。
ソートの目的
もともとでたらめに並んでいたのならそのままにしておけばよいのに、
わざわざそれをソートする理由は、ズバリ検索の高速化のためです。
データがそろえられていると、目的の値がどこにあるか見当がつき、
データがでたらめに並んでいる場合よりも素早く検索できます。
わざわざそれをソートする理由は、ズバリ検索の高速化のためです。
データがそろえられていると、目的の値がどこにあるか見当がつき、
データがでたらめに並んでいる場合よりも素早く検索できます。
バブルソート
ソートには実にさまざまなアルゴリズムが考案されていますが、
その中でもバブルソートは、プログラムのわかりやすさからよく取り上げられます。
ただし、速度は遅いため、あまり優秀な方法とはいえません。
その考え方は簡単です。
まず、1つ目と2つ目のデータを比べ、2つ目が小さい場合はデータを交換します。
次は、2つ目と3つ目を比較して交換します。これをデータの最後まで繰り返します。
データの最後まできたら、また1つ目から比較と交換を繰り返します。
これをデータの個数回だけ繰り返せば、データが整列されます。
このようにして、並び替えが終わるまで、2個間での並び化を繰り返すのが、バブルソートです。
バブルソートをプログラムとして実装すると次の通りになります。
動作を確認する場合は、arrayの型をcharとして、文字配列を渡すのが簡単です。
バブルソートでは2重のループを使うため、計算回数は O(N^2) となります。
これは、計算量目安の中で、右から3番目の算量に相当してしまいます。
バブルソートはそれなりに計算量が多くなるアルゴリズムであり、あまり優秀とは言えません。
その中でもバブルソートは、プログラムのわかりやすさからよく取り上げられます。
ただし、速度は遅いため、あまり優秀な方法とはいえません。
その考え方は簡単です。
まず、1つ目と2つ目のデータを比べ、2つ目が小さい場合はデータを交換します。
次は、2つ目と3つ目を比較して交換します。これをデータの最後まで繰り返します。
データの最後まできたら、また1つ目から比較と交換を繰り返します。
これをデータの個数回だけ繰り返せば、データが整列されます。
| 1つ目と2つ目の比較 | (23) | ( 9) | 7 | 15 | 3 | 1 | 30 | 19 |
|---|---|---|---|---|---|---|---|---|
| 2つ目が小さいので交換 | ( 9) | (23) | 7 | 15 | 3 | 1 | 30 | 19 |
| 2つ目と3つ目の比較 | 9 | (23) | ( 7) | 15 | 3 | 1 | 30 | 19 |
| 3つ目が小さいので交換 | 9 | ( 7) | (23) | 15 | 3 | 1 | 30 | 19 |
このようにして、並び替えが終わるまで、2個間での並び化を繰り返すのが、バブルソートです。
バブルソートをプログラムとして実装すると次の通りになります。
ソースコード
/*
使用法
SortBubble(ソートする配列、ソートする個数);
*/
void SortBubble(int array[], int n)
{
int i, j, temp;
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - 1; j++)
{
if (array[j + 1] < array[j])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}動作を確認する場合は、arrayの型をcharとして、文字配列を渡すのが簡単です。
バブルソートでは2重のループを使うため、計算回数は O(N^2) となります。
これは、計算量目安の中で、右から3番目の算量に相当してしまいます。
計算量
1、log2n、n、nlog2n、n^2、2^n、n!
バブルソートはそれなりに計算量が多くなるアルゴリズムであり、あまり優秀とは言えません。
本サイトについて
苦しんで覚えるＣ言語(苦Ｃ)はＣ言語入門サイトの決定版です。
Ｃ言語の基本機能を体系立てて解説しており、
市販書籍と同等以上の完成度です。
