Sorting algorithms/Cocktail sort with shifting bounds
The cocktail sort is an improvement on the Bubble Sort.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
| 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) |
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" 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 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:
<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</lang> % indicates a comment, and deal indicates a swap.
- Task
Implement a cocktail sort and optionally show the sorted output here on this page.
- Related task
REXX
This REXX version can handle array elements that may contain blanks or spaces,
and uses an improved algorithm that uses shifting bounds.
<lang rexx>/*REXX program sorts an array using the cocktail─sort method with shifting bounds. */
call gen /*generate some array elements. */
call show 'before sort' /*show unsorted array elements. */
say copies('█', 101) /*show a separator line (a fence). */
call cocktailSort # /*invoke the cocktail sort subroutine. */ call show ' after sort' /*show sorted array elements. */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ cocktailSort: procedure expose @.; parse arg N /*N: is number of items. */
end$= N - 1; beg$= 1
do while beg$ <= end$
beg$$= end$; new$$= beg$
do j=beg$ to end$; jp= j + 1
if @.j>@.jp then do; _=@.j; @.j=@.jp; @.jp=_; end$$=j; end
end /*j*/
end$= end$$ - 1
do k=end$ to beg$ by -1; kp= k + 1
if @.k>@.kp then do; _=@.k; @.k=@.kp; @.kp=_; beg$$=k; end
end /*k*/
beg$= beg$$ + 1
end /*while*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/ gen: @.= /*assign a default value for the stem. */
@.1 = '---the 22 card tarot deck (larger deck has 56 additional cards in 4 suits)---'
@.2 = '==========symbol====================pip======================================'
@.3 = 'the juggler ◄─── I'
@.4 = 'the high priestess [Popess] ◄─── II'
@.5 = 'the empress ◄─── III'
@.6 = 'the emperor ◄─── IV'
@.7 = 'the hierophant [Pope] ◄─── V'
@.8 = 'the lovers ◄─── VI'
@.9 = 'the chariot ◄─── VII'
@.10= 'justice ◄─── VIII'
@.11= 'the hermit ◄─── IX'
@.12= 'fortune [the wheel of] ◄─── X'
@.13= 'strength ◄─── XI'
@.14= 'the hanging man ◄─── XII'
@.15= 'death [often unlabeled] ◄─── XIII'
@.16= 'temperance ◄─── XIV'
@.17= 'the devil ◄─── XV'
@.18= 'lightning [the tower] ◄─── XVI'
@.18= 'the stars ◄─── XVII'
@.20= 'the moon ◄─── XVIII'
@.21= 'the sun ◄─── XIX'
@.22= 'judgment ◄─── XX'
@.23= 'the world ◄─── XXI'
@.24= 'the fool [often unnumbered] ◄─── XXII'
do #= 1 until @.#==; end; #= #-1 /*find how many entries in the array. */
return /* [↑] adjust for DO loop advancement.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ show: w= length(#); do j=1 for # /*#: is the number of items in @. */
say 'element' right(j, w) arg(1)":" @.j
end /*j*/ /* ↑ */
return /* └─────max width of any line.*/</lang>
- output when using the internal default inputs:
(Shown at three-quarter size.)
element 1 before sort: ---the 22 card tarot deck (larger deck has 56 additional cards in 4 suits)--- element 2 before sort: ==========symbol====================pip====================================== element 3 before sort: the juggler ◄─── I element 4 before sort: the high priestess [Popess] ◄─── II element 5 before sort: the empress ◄─── III element 6 before sort: the emperor ◄─── IV element 7 before sort: the hierophant [Pope] ◄─── V element 8 before sort: the lovers ◄─── VI element 9 before sort: the chariot ◄─── VII element 10 before sort: justice ◄─── VIII element 11 before sort: the hermit ◄─── IX element 12 before sort: fortune [the wheel of] ◄─── X element 13 before sort: strength ◄─── XI element 14 before sort: the hanging man ◄─── XII element 15 before sort: death [often unlabeled] ◄─── XIII element 16 before sort: temperance ◄─── XIV element 17 before sort: the devil ◄─── XV element 18 before sort: the stars ◄─── XVII █████████████████████████████████████████████████████████████████████████████████████████████████████ element 1 after sort: ---the 22 card tarot deck (larger deck has 56 additional cards in 4 suits)--- element 2 after sort: ==========symbol====================pip====================================== element 3 after sort: death [often unlabeled] ◄─── XIII element 4 after sort: fortune [the wheel of] ◄─── X element 5 after sort: justice ◄─── VIII element 6 after sort: strength ◄─── XI element 7 after sort: temperance ◄─── XIV element 8 after sort: the chariot ◄─── VII element 9 after sort: the devil ◄─── XV element 10 after sort: the emperor ◄─── IV element 11 after sort: the empress ◄─── III element 12 after sort: the hanging man ◄─── XII element 13 after sort: the hermit ◄─── IX element 14 after sort: the hierophant [Pope] ◄─── V element 15 after sort: the high priestess [Popess] ◄─── II element 16 after sort: the juggler ◄─── I element 17 after sort: the lovers ◄─── VI element 18 after sort: the stars ◄─── XVII