教科書で学ぶ探索と整列のアルゴリズム
定義バブルソートは、隣り合う 2 つの値を比べて順序が逆なら入れ替えることを、端から端まで繰り返す整列法である。
解説昇順に並べる場合、1 巡すると最も大きい値が末尾まで運ばれて確定する。次の巡は確定した末尾を除いた範囲で同じことを行い、1 巡の間に入れ替えが起きなければ並び終わっている。比較回数は選択ソートと同じく、およそ件数の 2 乗に比例する。
たとえ一列に並んだ人が隣の人とだけ背比べをして、背の高い方が右へ 1 つずれることを列の端まで続けるようなもの。
記憶フックbubble は泡。大きな値が泡のように 1 つずつ端へ浮かび上がっていく。