バブルソート

ソートアルゴリズムの一つ。単純交換ソート、単純交換法。

データの頭から順にスライドしながら、隣合う二者を比較して、小さい方に移動するソート方法。数値がまるで泡のように数列の中を上がっていくのでこの名がついている。

最悪計算量はO(n^2)であるが、すでに大部分がソート済である場合は計算量はO(n)に近づく。しかし、ランダムに生成したデータでソートを行なわせると他のどのソートよりも処理が遅い。これはデータを交換するためのオーバーヘッドが大きいからである。

バブルソート
３  ２  １  ４
  ×                (交換)
２  ３  １  ４
      ×            (交換)
２  １  ３  ４
          ・        (交換しない)
２  １  ３  ４
  ×                (交換)
１  ２  ３  ４

通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)