user
|  |
| --- |
| This page uses content from **Wikipedia**. The original article was at Cocktail sort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

The   cocktail sort   is an improvement on the   Bubble Sort.

A cocktail sort is also known as:

:   :   :   :   * cocktail shaker sort
                * happy hour sort
                * bidirectional bubble sort
                * a bubble sort variation
                * a selection sort variation
                * ripple sort
                * shuffle sort
                * shuttle sort

The improvement is basically that values "bubble"   (migrate)   both directions through the
array,   because on each iteration the cocktail sort   *bubble sorts*   once
forwards and once backwards.

After   *ii*   passes,   the first   *ii*   and the
last   *ii*   elements in the array are in their correct
positions,   and don't have to be checked (again).

By shortening the part of the array that is sorted each time,   the number of
comparisons can be halved.

Pseudocode for the    2nd    algorithm   (from
Wikipedia)   with an added comment and changed indentations:

```
function A = cocktailShakerSort(A)
% `beginIdx` and `endIdx` marks the first and last index to check.
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

    % decreases `endIdx` because the elements after `newEndIdx` are in correct order
    endIdx = newEndIdx - 1;

    % (FOR  (below)  decrements the  II  index by -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

    % increases `beginIdx` because the elements before `newBeginIdx` are in correct order.
    beginIdx = newBeginIdx + 1;
    end
end

```

**%**   indicates a comment,   and   **deal**   indicates a   *swap*.

Task

Implement a   *cocktail sort*   and optionally show the sorted output here on this page.

See the   *discussion*   page for some timing comparisons.

Related task
:   * cocktail sort
assistant
**Works with**: Rakudo version 2020.05

```
sub cocktail_sort ( @a ) {
    my ($min, $max) = 0, +@a - 2;
    loop {
        my $swapped_forward = 0;
        for $min .. $max -> $i {
            given @a[$i] cmp @a[$i+1] {
                when More {
                    @a[ $i, $i+1 ] .= reverse;
                    $swapped_forward = 1
                }
                default {}
            }
        }
        last if not $swapped_forward;
        $max -= 1;

        my $swapped_backward = 0;
        for ($min .. $max).reverse -> $i {
            given @a[$i] cmp @a[$i+1] {
                when More {
                    @a[ $i, $i+1 ] .= reverse;
                    $swapped_backward = 1
                }
                default {}
            }
        }
        last if not $swapped_backward;
        $min += 1;
    }
    @a
}

my @weights = (flat 0..9, 'A'..'F').roll(2 + ^4 .roll).join xx 100;
say @weights.sort.Str eq @weights.&cocktail_sort.Str ?? 'ok' !! 'not ok';

```