12,905
回編集
「C++の基礎 - ソート」の版間の差分
ナビゲーションに移動
検索に移動
→バブルソート
(→概要) |
(→バブルソート) |
||
| 4行目: | 4行目: | ||
== バブルソート == | == バブルソート == | ||
バブルソートは、隣接する要素を順次比較して、必要に応じて交換を行うソートアルゴリズムである。 | バブルソートは、隣接する要素を順次比較して、必要に応じて交換を行うソートアルゴリズムである。<br> | ||
大きな値が徐々に右側に移動していく様子が、泡が水面に浮かび上がっていく様子に似ていることから、この名前が付けられた。 | 大きな値が徐々に右側に移動していく様子が、泡が水面に浮かび上がっていく様子に似ていることから、この名前が付けられた。<br> | ||
<br> | |||
# 配列の先頭から順に隣接する要素を比較して、左の要素が右の要素より大きい場合に交換を行う。 | # 配列の先頭から順に隣接する要素を比較して、左の要素が右の要素より大きい場合に交換を行う。 | ||
# この操作を1回行うと、最も大きな要素が配列の最後尾に移動する。 | # この操作を1回行うと、最も大きな要素が配列の最後尾に移動する。 | ||
# 次の走査では、最後尾を除いた範囲で同様の操作を行い、これを繰り返す。 | # 次の走査では、最後尾を除いた範囲で同様の操作を行い、これを繰り返す。 | ||
<br> | <br> | ||
バブルソートの実装は簡単であるが、計算量は <math>O(n^2)</math> となる。 | バブルソートの実装は簡単であるが、計算量は <math>O(n^2)</math> となる。<br> | ||
安定なソートであるため、追加のメモリをほぼ必要としないというメリットがある。 | 安定なソートであるため、追加のメモリをほぼ必要としないというメリットがある。<br> | ||
<br> | <br> | ||
<syntaxhighlight lang="c++"> | <syntaxhighlight lang="c++"> | ||