カクテルシェーカーソート
ソートアルゴリズム
カクテルシェーカーソート
シェーカーソートの可視化
クラスソートアルゴリズム
データ構造配列
最悪の パフォーマンス お （ n 2 ） {\displaystyle O(n^{2})\,}
最高の パフォーマンス お （ n ） {\displaystyle O(n)\,}
平均的な パフォーマンス お （ n 2 ） {\displaystyle O(n^{2})\,}
最悪の場合の 空間複雑度 お （ 1 ） {\displaystyle O(1)}
最適いいえ

カクテルシェーカーソート[ 1]は、双方向バブルソート[2] 、カクテルソート、シェーカーソート（選択ソートの派生形とも呼ばれる）、リップルソート、シャッフルソート[3]、シャトルソートとも呼ばれ、バブルソートの拡張アルゴリズムである。このアルゴリズムは、双方向に動作することでバブルソートを拡張する。アイテムをリストの先頭に素早く移動させることでバブルソートの性能を向上させているが、その性能向上はわずかである。

バブルソートの多くの変種と同様に、カクテルシェイカーソートは主に教育ツールとして用いられます。クイックソート、マージソート、ティムソートといったより効率的なアルゴリズムは、PythonやJavaなどの一般的なプログラミング言語に組み込まれているソートライブラリで使用されています。[4] [5]

擬似コード

最も単純な形式では、毎回リスト全体を処理します。 

手順cocktailShakerSort(A :ソート可能なアイテムのリスト)は
    
        交換済み := false
        0からlength(A) − 1までのiごとに、次のようにします。A [i] > A[i + 1]の場合、2 つの要素の順序が間違っているかどうかをテストします。swap 
                (A[i], A[i + 1]) の場合、2 つの要素の順序を入れ替えます。
             
                交換済み := true
            end if 
        end for 
        if not swapped then 
            // スワップが発生していない場合はここで外側のループを終了できます。
            break do-while loop 
        end if
        交換済み := false
        長さ(A) − 1から0までのiそれぞれについて、 A[i] > A[ i + 1]ならば
            
                スワップ(A[i], A[i + 1])
                交換済み := 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倍未満の速度で実行されます。

もう一つの最適化は、アルゴリズムが最後に実際に交換が行われた場所を記憶することです。次の反復では、この制限を超える交換は行われず、アルゴリズムのパスは短くなります。カクテルシェーカーソートは双方向に行われるため、交換の可能性のある範囲、つまりテスト対象となる範囲はパスごとに減少し、全体的な実行時間がわずかに短縮されます。

複雑

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

カクテルシェーカーソートについては、 『The Art of Computer Programming』という書籍でも簡単に触れられており、バブルソートの同様の改良点も紹介されています。結論として、クヌースはバブルソートとその改良点について次のように述べています。

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

— DEクヌース[1]

バリエーション

  • デュアル カクテル シェイカー ソートは、カクテル シェイカー ソートのバリエーションであり、反復ごとに前方パスと後方パスを同時に実行し、オリジナルと比較してパフォーマンスが向上します。

参考文献

  1. ^ abc Knuth, Donald E. (1973). 「Sorting by Exchanging」. Art of Computer Programming . 第3巻. Sorting and Searching (第1版). Addison-Wesley . pp.  110– 111. ISBN 0-201-03803-X。
  2. ^ Black, Paul E.; Bockholt, Bob (2009年8月24日). 「双方向バブルソート」. Black, Paul E. (編). 『アルゴリズムとデータ構造の辞書』.米国国立標準技術研究所. 2013年3月16日時点のオリジナルよりアーカイブ。 2010年2月5日閲覧。
  3. ^ マーティン・デュール (1986)。 「Die schrittweise Entwicklung und Beschreibung einer Shuffle-Sort-Array Schaltung」。HYPERKARL aus der Algorithmischen Darstellung des BUBBLE-SORT-ALGORITHMUS (ドイツ語)。カイザースラウテルン工科大学。 {{cite book}}:|journal=無視されました (ヘルプ)
  4. ^ "[JDK-6804124] (coll) java.util.Arrays.sort の "modified mergesort" を timsort に置き換える - Java Bug System". bugs.openjdk.java.net . 2020年1月11日閲覧。
  5. ^ Peters, Tim (2002-07-20). 「[Python-Dev] ソート」 . 2020年1月11日閲覧。

出典

  • Hartenstein, R. (2010年7月). 「コンピューティングの新たな世界モデル」(PDF) .コンピューティング改革への壮大な挑戦.ベロオリゾンテ, ブラジル: CSBC. オリジナル(PDF)から2013年8月7日にアーカイブ. 2011年1月14日閲覧.
Wikibookアルゴリズム実装には、カクテルソートに関するページがあります。
  • カクテルソートのインタラクティブデモ
  • Javaソースコードとカクテルソート（双方向バブルソートと呼ばれる）と他のいくつかのアルゴリズムのアニメーションデモ
  • 「カクテルソートとその他のアルゴリズムの.NET実装」。2012年2月12日時点のオリジナルよりアーカイブ。
「https://en.wikipedia.org/w/index.php?title=Cocktail_shaker_sort&oldid=1267360789」より取得