Cocktail Sortとは
Cocktail Sort（カクテルソート）とは、バブルソートの改良版である。シェーカーソートとも呼ばれる。安定なソートの一種。
アルゴリズム
- 先頭から2つずつ隣り合う要素を比較し、先頭側が小さくなるように入れ替える
- 数値を入れ替えたらフラグを立てる
- 末尾まで行き、フラグが立っていない場合は終了。フラグが立っている場合はフラグをリセットし、見る範囲の終端を1つ先頭側へずらす1
- 末尾から2つずつ隣り合う要素を比較し、先頭側が小さくなるように入れ替える
- 数値を入れ替えたらフラグを立てる
- 先頭まで行き、フラグが立っていない場合は終了。フラグが立っている場合はフラグをリセットし、見る範囲の始端を1つ末尾側へずらす2
- これをフラグが立たなくなるまで続ける
実装例
def swap_forward(numbers: list[int], idx_start: int, idx_end: int) -> bool:
is_swapped = False
for i in range(idx_start, idx_end):
if numbers[i] > numbers[i + 1]:
numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]
is_swapped = True
return is_swapped
def swap_backward(numbers: list[int], idx_start: int, idx_end: int) -> bool:
is_swapped = False
for i in range(idx_end, idx_start, -1):
if numbers[i - 1] > numbers[i]:
numbers[i - 1], numbers[i] = numbers[i], numbers[i - 1]
is_swapped = True
return is_swapped
def cocktail_sort(numbers: list[int]) -> list[int]:
idx_start = 0
idx_end = len(numbers) - 1
while True:
if not swap_forward(numbers, idx_start, idx_end):
break
idx_end -= 1
if not swap_backward(numbers, idx_start, idx_end):
break
idx_start += 1
return numbers計算量
要素数を$n$とする。
| 計算量 | |
|---|---|
| Average | $\mathrm{O}(n^2)$ |
| Best | $\mathrm{O}(n)$ |
| Worst | $\mathrm{O}(n^2)$ |
Pros
- バブルソートに比べて、特定の状況下で効率的
- e.g. 末尾に小さい要素がある場合、先頭に大きい要素がある場合
- 双方向捜査のため、両方向に対して局所的な順序を改善できる
- 安定なソート
Cons
- 効率が悪い
- 計算量が大きいため速度は遅い
- ほとんどの場合、他のソートアルゴリズムの方が良い
- バブルソートに比べて実装が少し複雑
利用場面
- 要素数が少ない場合 : シンプルさと容易さが有利になることがある
- 教育目的 : アルゴリズムの理解を深めるために用いられることがある