バブルソート
全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行う。なおこの繰り返しは、入れ替えが起こらなくなった時点で(それ以降は何度繰り返しても変化が起こらなくなるので)中断することができる。
この「全ての要素に関して」において、全ての要素に関して比較交換が行なわれるならば順序を問わない特徴を持つ(安定ソート)。この特徴により、比較交換順序を調整することで効率化されたアルゴリズムが多数派生している。そのため他の様々なソートアルゴリズムの基礎として一度は学ばされるアルゴリズムとなっている。
例えば前記の特徴によりバブルソートは並列処理と親和性が高く、比較交換器を潤沢に用いることで比較交換順序を調整したハードウェア実装では時間計算量はO(n)になる。この並列処理向けに比較交換順序を調整したアルゴリズムとして奇偶転置ソートがある。
初期データ: 8 4 3 7 6 5 2 1 結果が確定した部を太字でしめすと、
交換回数の合計:7+5+3+2+2+2+1=22