カクテルシェーカーの種類

カクテルシェーカーソート[ ^{1 ]は}、双方向バブルソート^{[ 2 ]} 、カクテルソート、シェーカーソート（選択ソートの変種を指す場合もある）、リップルソート、シャッフルソート[ ^{3 ] 、}またはシャトルソートとも呼ばれ、バブルソートの拡張です。このアルゴリズムは、双方向で動作することでバブルソートを拡張しています。リストの先頭にアイテムをより速く移動させることでバブルソートを改善していますが、パフォーマンスの向上はわずかです。

バブルソートのほとんどのバリエーションと同様に、カクテルシェーカーソートは主に教育ツールとして使用されます。クイックソート、マージソート、ティムソートなどのより効率的なアルゴリズムは、PythonやJavaなどの人気のあるプログラミング言語に組み込まれているソートライブラリで使用されています。^{[ 4 ] [ 5 ]}

最もシンプルな形式は、毎回リスト全体を順に処理します。

procedure cocktailShakerSort(A :ソート可能なアイテムのリスト) is do swapped := false 各iについて、 0からlength(A) − 2 まで、以下を実行する:もしA[i] > A[i + 1]ならば// 2 つの要素の順序が間違っているかどうかをテストする swap(A[i], A[i + 1]) // 2 つの要素の位置を交換する swapped := true end if end for if not swapped then // スワップが発生しなかった場合は、ここで外側のループを終了できます。break do-while ループend if swapped := false 長さ(A) − 2から0までの各iについて、 A[i] > A[i + 1]ならば、 swap(A[i], A[i + 1]) swapped := true end if end for while swapped // 要素が交換されていない場合、リストはソート済みですend procedure

最初の右方向へのパスでは、最大の要素が末尾の正しい位置に移動し、次の左方向へのパスでは、最小の要素が先頭の正しい位置に移動します。2回目の完全なパスでは、2番目に大きい要素と2番目に小さい要素が正しい位置に移動し、以下同様です。i 回パスした後、リストの最初のi 個と最後のi個の要素は正しい位置に配置され、チェックする必要はありません。ソートするリストの部分を毎回短くすることで、操作の数を半分にすることができます（バブルソートを参照）。

これは、最後のスワップインデックスを記憶し、境界を更新するという最適化を施した、MATLAB/OCTAVE におけるアルゴリズムの例です。

function A = cocktailShakerSort ( A ) % `beginIdx` と `endIdx` はチェックする最初のインデックスと最後のインデックスを示しますbeginIdx = 1 ; endIdx = length ( A ) - 1 ; while beginIdx <= endIdx newBeginIdx = endIdx ; newEndIdx = beginIdx ; for ii = beginIdx : endIdx if A ( ii ) > A ( ii + 1 ) [ A ( ii + 1 ), A ( ii )] = deal ( A ( ii ), A ( ii + 1 )); newEndIdx = ii ; end end% `newEndIdx` 以降の要素が正しい順序になっているため、`endIdx` が減少します。endIdx = newEndIdx - 1 ;for ii = endIdx : - 1 : beginIdx if A ( ii ) > A ( ii + 1 ) [ A ( ii + 1 ), A ( ii )] = deal ( A ( ii ), A ( ii + 1 )); newBeginIdx = ii ; end end % `newBeginIdx` より前の要素が正しい順序になっているため、`beginIdx` が増加しますbeginIdx = newBeginIdx + 1 ; end end

カクテルシェーカーソートはバブルソートのわずかなバリエーションです。^{[ 1 ]}バブルソートはリストを下から上に繰り返し通過するのに対し、カクテルシェーカーソートは下から上、そして上から下へと交互に通過します。標準的なバブルソートよりもわずかに優れたパフォーマンスを実現できます。その理由は、バブルソートはリストを一方向にしか通過しないため、各イテレーションでアイテムを1ステップずつしか後ろに移動できないためです。

この点を証明する例として、リスト（2,3,4,5,1）が挙げられます。このリストはカクテルソートを1回実行するだけでソートされますが、昇順バブルソートでは4回実行する必要があります。ただし、カクテルソート1回の実行はバブルソート2回の実行としてカウントされます。一般的に、カクテルソートはバブルソートよりも2倍以上高速です。

もう一つの最適化として、アルゴリズムが最後に実際にスワップが行われた場所を記憶するようにする方法があります。次のイテレーションでは、この制限を超えるスワップは行われず、アルゴリズムのパスが短くなります。カクテルシェーカーソートは双方向で実行されるため、テスト対象となるスワップの範囲がパスごとに縮小し、結果として全体の実行時間がわずかに短縮されます。

カクテルシェーカーソートの複雑さをビッグオー記法で表すと次のようになります。${\displaystyle O(n^{2})}$最悪の場合と平均的な場合の両方で、${\displaystyle O(n)}$リストがソートアルゴリズムを適用する前にほぼ順序付けられている場合。たとえば、すべての要素が最終的な位置から最大で k (k ≥ 1) だけ異なる位置にある場合、カクテルシェーカーソートの複雑さは次のようになります。${\displaystyle O(kn).}$

カクテルシェーカーソートは、 『コンピュータプログラミングの技法』という書籍でも簡単に説明されており、バブルソートの同様の改良版も紹介されている。結論として、クヌースはバブルソートとその改良について次のように述べている。

しかし、これらの改良のどれも、単純な挿入（つまり挿入ソート）よりも優れたアルゴリズムにはつながりません。また、単純な挿入はNが大きい場合には適していないことは既に分かっています。[...] 要するに、バブルソートには、キャッチーな名前といくつかの興味深い理論的問題につながるという事実以外に、推奨できる点は何もないようです。 

• デュアルカクテルシェーカーソートは、カクテルシェーカーソートの派生アルゴリズムであり、1回の反復処理で順方向パスと逆方向パスを同時に実行することで、元のアルゴリズムと比較してパフォーマンスを向上させています。

• Hartenstein, R. (2010年7月). 「コンピューティングの新しい世界モデル」(PDF) . The Grand Challenge to Reinvent Computing .ベロオリゾンテ、ブラジル: CSBC. 2013年8月7日にオリジナル(PDF)からアーカイブ済み。 2011年1月14日取得。

• カクテルの種類をインタラクティブにデモ
• Javaのソースコードと、カクテルソート（双方向バブルソートとも呼ばれる）およびその他のいくつかのアルゴリズムのアニメーションデモ
• 「.NETによるカクテルソートおよびその他のいくつかのアルゴリズムの実装」。 2012年2月12日にオリジナルからアーカイブされました。