アルゴリズムの勉強 #3 cocktail sort

概要

bubble sortの改良版

・bubble sortではスキャンを一方向でのみ行うが、cocktail sortは交互に行ったり来たりする。

特徴など

・安定ソート
・bubble sortより若干効率が良い。

計算量

Best (最良計算時間)

O(n)

・1巡目のソートで整列した場合

Average (平均計算時間）

O(n^2)

Worst (最悪計算時間)

O(n^2)

実装例

あとでかく

その他メモ

・別名、「シェイカーソート」「双方向バブルソート」「改良交換法」
　・「改良交換法」ではわかりずらいし、「cocktail sort」もわかりずらい。これは「双方向バブルソート」の方が言いたいことは伝わる。