12,950
回編集
「C++の基礎 - ソート」の版間の差分
ナビゲーションに移動
検索に移動
→概要
(→概要) |
|||
| 1行目: | 1行目: | ||
== 概要 == | == 概要 == | ||
<br><br> | |||
== バブルソート == | |||
バブルソートは、隣接する要素を順次比較して、必要に応じて交換を行うソートアルゴリズムである。 | |||
大きな値が徐々に右側に移動していく様子が、泡が水面に浮かび上がっていく様子に似ていることから、この名前が付けられた。 | |||
# 配列の先頭から順に隣接する要素を比較して、左の要素が右の要素より大きい場合に交換を行う。 | |||
# この操作を1回行うと、最も大きな要素が配列の最後尾に移動する。 | |||
# 次の走査では、最後尾を除いた範囲で同様の操作を行い、これを繰り返す。 | |||
<br> | |||
バブルソートの実装は簡単であるが、計算量は <math>O(n^2)</math> となる。 | |||
安定なソートであるため、追加のメモリをほぼ必要としないというメリットがある。 | |||
<br> | |||
<syntaxhighlight lang="c++"> | |||
#include <iostream> | |||
using namespace std; | |||
int main() | |||
{ | |||
int arr[8] = {64, 34, 25, 12, 22, 11, 90, 50}; | |||
int n = 8; // 配列のサイズ | |||
cout << "ソート前の配列: "; | |||
for (int i = 0; i < n; i++) { | |||
cout << arr[i] << " "; | |||
} | |||
cout << endl; | |||
// バブルソートのアルゴリズム | |||
for (int i = 0; i < n - 1; i++) { | |||
bool swapped = false; // 交換が発生したかを記録 | |||
for (int j = 0; j < n - 1 - i; j++) { | |||
// 隣接要素を比較し、必要に応じて交換 | |||
if (arr[j] > arr[j + 1]) { | |||
int temp = arr[j]; | |||
arr[j] = arr[j + 1]; | |||
arr[j + 1] = temp; | |||
swapped = true; | |||
} | |||
} | |||
// 各ステップでの配列の状態を表示 | |||
cout << "ステップ " << i + 1 << ": "; | |||
for (int k = 0; k < n; k++) { | |||
cout << arr[k] << " "; | |||
} | |||
cout << endl; | |||
// 交換が発生しなければソート完了 | |||
if (!swapped) { | |||
break; | |||
} | |||
} | |||
cout << "ソート後の配列: "; | |||
for (int i = 0; i < n; i++) { | |||
cout << arr[i] << " "; | |||
} | |||
cout << endl; | |||
return 0; | |||
} | |||
</syntaxhighlight> | |||
<br> | |||
# 出力例: | |||
ソート前の配列: 64 34 25 12 22 11 90 50 | |||
ステップ 1: 34 25 12 22 11 64 50 90 | |||
ステップ 2: 25 12 22 11 34 50 64 90 | |||
ステップ 3: 12 22 11 25 34 50 64 90 | |||
ステップ 4: 12 11 22 25 34 50 64 90 | |||
ステップ 5: 11 12 22 25 34 50 64 90 | |||
ソート後の配列: 11 12 22 25 34 50 64 90 | |||
<br><br> | <br><br> | ||