カクテルシェーカーの並べ替え

カクテル シェーカー ソート –双方向バブルソーティングの一種であるシェーカーソーティング。
アルゴリズムは次のように機能します。

<オル>

  • ループ内での最初の検索方向が選択されます (通常は左から右)
  • ループの次に、数値がペアでチェックされます
  • 次の要素の方が大きい場合、それらは交換されます
  • 終了すると、検索プロセスが方向を逆にして再び開始されます
  • 検索は順列がなくなるまで繰り返されます
  • アルゴリズムの時間計算量はバブル – に似ています。 O(n2)

    PHP での実装例:

    <?php
    
    function cocktailShakeSort($numbers)
    {
        echo implode(",", $numbers),"\n";
        $direction = false;
        $sorted = false;
        do {
            $direction = !$direction;        
            $firstIndex = $direction == true ? 0 : count($numbers) - 1;
            $lastIndex = $direction == true ? count($numbers) - 1 : 0;
            
            $sorted = true;
            for (
                $i = $firstIndex;
                $direction == true ? $i < $lastIndex : $i > $lastIndex;
                $direction == true ? $i++ : $i--
            ) {
                $lhsIndex = $direction ? $i : $i - 1;
                $rhsIndex = $direction ? $i + 1 : $i;
    
                $lhs = $numbers[$lhsIndex];
                $rhs = $numbers[$rhsIndex];
    
                if ($lhs > $rhs) {
                    $numbers[$lhsIndex] = $rhs;
                    $numbers[$rhsIndex] = $lhs;
                    $sorted = false;
                }
            }
        } while ($sorted == false);
    
        echo implode(",", $numbers);
    }
    
    $numbers = [2, 1, 4, 3, 69, 35, 55, 7, 7, 2, 6, 203, 9];
    cocktailShakeSort($numbers);
    
    ?>

    Ссылки

    https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/cocktailShakerSort/cocktailShakerSort.php

    Источники

    https://www.youtube.com/watch?v=njClLBoEbfI
    https://www.geeksforgeeks.org/cocktail-sort/
    https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort

    Leave a Comment

    Your email address will not be published. Required fields are marked *