{{Sorting Algorithm}}
[[Category:Sorting]]
{{Wikipedia|Cocktail sort}}

<!-- 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

      Because the Rosetta Code task      Cocktail sort      had so many entries in it,
      adding an optional algorithm  (or a stretch goal)  wasn't feasible at this time,
      I decided to create   another   Rosetta Code task   to perform a cocktail sort
      with the improved bounds checking  (shifting bounds).

                    -------------- Gerard Schildberger ---------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
!-->

The &nbsp; cocktail sort &nbsp; is an improvement on the &nbsp; [[Bubble Sort]]. 


A cocktail sort is also known as:
::::* &nbsp; cocktail shaker sort
::::* &nbsp; happy hour sort
::::* &nbsp; bidirectional bubble sort
::::* &nbsp; a bubble sort variation
::::* &nbsp; a selection sort variation
::::* &nbsp; ripple sort
::::* &nbsp; shuffle sort
::::* &nbsp; shuttle sort


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

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

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


Pseudocode for the &nbsp; <big> 2<sup>nd</sup> </big> &nbsp; algorithm &nbsp; (from
[[wp:Cocktail sort|Wikipedia]]) &nbsp; with an added comment and changed indentations:
<syntaxhighlight lang="matlab">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</syntaxhighlight>
<big>'''%'''</big> &nbsp; indicates a comment, &nbsp; and &nbsp; '''deal''' &nbsp; indicates a &nbsp; ''swap''. 


;Task:
Implement a &nbsp; ''cocktail sort'' &nbsp; and optionally show the sorted output here on this page.
  
See the &nbsp; ''discussion'' &nbsp; page for some timing comparisons.


;Related task:
:* &nbsp; [https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort cocktail sort]
<br><br>