単純な比較ソートであるバブルソートを使用する

バブルソート (bubble sort) は、隣り合う要素を比較し、順序が逆なら入れ替える操作を繰り返すことで、配列全体を昇順（または降順）に整列させる単純な比較ソートである。小さい（または大きい）値が「泡のように」一端へ浮き上がっていく様子からこの名前が付いている。

  1. 走査開始: 配列の先頭から、隣り合う2要素 (a[i], a[i+1]) を順に見ていく。
  2. 交換: a[i] > a[i+1] のときだけ2つを入れ替える。そうでなければ何もしない。
  3. 走査終了: 1回の始端から終端への走査が終わると、常に大きい方が終端へ押し出されるため最大の要素は必ず終端に移動する。
  4. 繰り返し: 配列がソートされるまで上記の走査を繰り返す。最適化として、すでに終端に固定された最大要素は次の走査から比較対象から外してよい。
procedure bubble_sort(A)
  n = length(A)
  for i from 0 to n - 1
    swapped = false
    for j from 0 to n - 2 - i
      if A[j] > A[j + 1] then
        swap(A[j], A[j + 1])
        swapped = true
    if not swapped then
      break

最悪時間計算量は O(n²) で、すでにソートされている場合は O(n) となる。空間計算量は O(1) で、安定なソートである（等しいキーの相対順序を保つ）。

説明は簡単で教育的な例としてよく用いられるが、実際の用途ではクイックソートやマージソートなどのより効率的なアルゴリズムが一般的に使用される。