シェーカーソートを使用する

シェーカーソート (shaker sort) は、カクテルシェイカーを振るようにデータが両端へ動いていく様子から カクテルソート (cocktail sort) とも呼ばれる比較ソートである。バブルソートと同様に隣り合う要素だけを入れ替えるが、左から右への走査と右から左への走査を交互に繰り返す点が異なる。

  1. 右方向の走査: 左端から右端手前まで進み、a[i] > a[i+1] なら交換する。これでそのラウンドでは最大の要素が右端側へ寄る。
  2. 左方向の走査: 右端から左端手前まで戻り、同様に逆順なら交換する。最小の要素が左端側へ寄る。
  3. 範囲の縮小: 右方向のあと右端は確定した最大として比較範囲から外し、左方向のあと左端は確定した最小として外す。
  4. 終了条件: ある走査で一度も交換が起きなければ全体がソート済みとして終了する。

「タートル問題」と呼ばれる現象で、バブルソートでは小さな値が左端へ届くのに多くのパスを要することがあるが、シェーカーソートでは逆向きの走査があるため、極端に左にしか進めない値も早めに動かしやすくなる。

時間計算量は最悪でも O(n²) で、空間計算量は O(1)。隣接交換のみなので 安定 なソートである。

procedure shaker_sort(A)
  begin = 0
  end = length(A) - 1
  while begin < end
    swapped = false
    for i from begin to end - 1
      if A[i] > A[i + 1] then
        swap(A[i], A[i + 1])
        swapped = true
    end = end - 1
    if not swapped then
      break
    swapped = false
    for i from end down to begin + 1
      if A[i - 1] > A[i] then
        swap(A[i - 1], A[i])
        swapped = true
    begin = begin + 1
    if not swapped then
      break

実運用ではマージソートやクイックソートなどが選ばれることが多いが、実装が単純で挙動を視覚化しやすい教育的なアルゴリズムとして有用である。

バブルソートと同じく O(n²) だが、データによっては逆向き走査によりステップ数が抑えられる場合がある。それでも大規模データ向けの第一選択にはならないことが多い。