Sorting algorithms/Cocktail sort with shifting bounds
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) |
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" 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.
See the discussion page for some timing comparisons.
- Related task
360 Assembly
For maximum compatibility, this program uses only the basic instruction set. The program uses also HLASM structured macros (DO,ENDDO,IF,ELSE,ENDIF) for readability and two ASSIST/360 macros (XDECO,XPRNT) to keep the code as short as possible. <lang 360asm>* Cocktail sort with shifting bounds 10/05/2020 COCKSHIS CSECT
USING COCKSHIS,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
- Sort
LA R0,1 1
ST R0,BEGIDX begIdx=LBound(A)
L R0,N n
BCTR R0,0 n-1
ST R0,ENDIDX endIdx=UBound(A)-1
L R1,BEGIDX begIdx
DO WHILE=(C,R1,LE,ENDIDX) while begIdx<=endIdx
MVC NWBEGIDX,ENDIDX nwbegIdx=endIdx
MVC NWENDIDX,BEGIDX nwendIdx=begIdx
L RI,BEGIDX i=begIdx
DO WHILE=(C,RI,LE,ENDIDX) do i=1 to endIdx
LR R1,RI i
SLA R1,2 .
LA R2,A-4(R1) @a(i)
LA R3,A(R1) @a(i+1)
L R4,0(R2) r4=a(i)
L R5,0(R3) r5=a(i+1)
IF CR,R4,GT,R5 THEN if a(i)>a(i+1) then
ST R5,0(R2) a(i)=r5
ST R4,0(R3) a(i+1)=r4
ST RI,NWENDIDX nwendIdx=i
ENDIF , end if
LA RI,1(RI) i=i+1
ENDDO , end do
L R1,NWENDIDX nwendIdx
BCTR R1,0 -1
ST R1,ENDIDX endIdx=nwendIdx-1
LR RI,R1 endIdx
DO WHILE=(C,RI,GE,BEGIDX) do i=endIdx to begIdx by -1
LR R1,RI i
SLA R1,2 .
LA R2,A-4(R1) @a(i)
LA R3,A(R1) @a(i+1)
L R4,0(R2) r4=a(i)
L R5,0(R3) r5=a(i+1)
IF CR,R4,GT,R5 THEN if a(i)>a(i+1) then
ST R5,0(R2) a(i)=r5
ST R4,0(R3) a(i+1)=r4
ST RI,NWBEGIDX nwbegIdx=i
ENDIF , end if
BCTR RI,0 i=i-1
ENDDO , end do
L R1,NWBEGIDX nwbegIdx
LA R1,1(R1) +1
ST R1,BEGIDX begIdx=nwbegIdx+1
ENDDO , endwhile
- Display sorted list
LA R3,PG pgi=0
LA RI,1 i=1
DO WHILE=(C,RI,LE,N) do i=1 to n
LR R1,RI i
SLA R1,2 .
L R2,A-4(R1) a(i)
XDECO R2,XDEC edit a(i)
MVC 0(4,R3),XDEC+8 output a(i)
LA R3,4(R3) pgi=pgi+4
LA RI,1(RI) i=i+1
ENDDO , end do
XPRNT PG,L'PG print buffer
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling save
A DC F'4',F'65',F'2',F'-31',F'0',F'99',F'2',F'83'
DC F'782',F'1',F'45',F'82',F'69',F'82',F'104',F'58'
DC F'88',F'112',F'89',F'74'
N DC A((N-A)/L'A) number of items of a PG DC CL80' ' buffer XDEC DS CL12 temp for xdeco BEGIDX DS F begIdx ENDIDX DS F endIdx NWBEGIDX DS F nwbegIdx NWENDIDX DS F nwendIdx
REGEQU
RI EQU 6 i
END COCKSHIS </lang>
- Output:
-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782
ALGOL 60
<lang algol60>begin
comment Sorting algorithms/Cocktail sort - Algol 60;
integer array A[1:20]; integer nA;
procedure cocktailsort(lb,ub);
value lb,ub; integer lb,ub;
begin
integer i,lbx,ubx;
boolean swapped;
lbx:=lb; ubx:=ub-1; swapped :=true;
for i:=1 while swapped do begin
procedure swap(i); value i; integer i;
begin
integer temp;
temp :=A[i];
A[i] :=A[i+1];
A[i+1]:=temp;
swapped:=true
end swap;
swapped:=false;
for i:=lbx step 1 until ubx do if A[i]>A[i+1] then swap(i);
if swapped
then begin
for i:=ubx step -1 until lbx do if A[i]>A[i+1] then swap(i);
ubx:=ubx-1; lbx:=lbx+1
end
end
end cocktailsort;
procedure inittable(lb,ub);
value lb,ub; integer lb,ub;
begin
integer i;
for i:=lb step 1 until ub do A[i]:=entier(rand*100)
end inittable;
procedure writetable(lb,ub);
value lb,ub; integer lb,ub;
begin
integer i;
for i:=lb step 1 until ub do outinteger(1,A[i]);
outstring(1,"\n")
end writetable;
nA=20;
inittable(1,nA);
writetable(1,nA);
cocktailsort(1,nA);
writetable(1,nA)
end </lang>
- Output:
6 92 61 64 73 3 81 28 62 67 83 33 77 14 16 23 47 19 33 78 3 6 14 16 19 23 28 33 33 47 61 62 64 67 73 77 78 81 83 92
Julia
The imp[lementation chosen is to extend the native Julia sort! function, which by default supports insertion sort, quick sort, partial quick sort, and merge sort. <lang julia>module CocktailShakerSorts
using Base.Order, Base.Sort import Base.Sort: sort! export CocktailShakerSort
struct CocktailSortAlg <: Algorithm end const CocktailShakerSort = CocktailSortAlg()
function sort!(A::AbstractVector, lo::Int, hi::Int, a::CocktailSortAlg, ord::Ordering)
if lo > 1 || hi < length(A)
return sort!(view(A, lo:hi), 1, length(A), a, ord)
end
forward, beginindex, endindex = ord isa ForwardOrdering, 1, length(A) - 1
while beginindex <= endindex
newbegin, newend = endindex, beginindex
for idx in beginindex:endindex
if (forward && A[idx] > A[idx + 1]) || (!forward && A[idx] < A[idx + 1])
A[idx + 1], A[idx] = A[idx], A[idx + 1]
newend = idx
end
end
# end has another in correct place, so narrow end by 1
endindex = newend - 1
for idx in endindex:-1:beginindex
if (forward && A[idx] > A[idx + 1]) || (!forward && A[idx] < A[idx + 1])
A[idx + 1], A[idx] = A[idx], A[idx + 1]
newbegin = idx
end
end
# beginning has another in correct place, so narrow beginning by 1
beginindex = newbegin + 1
end
A
end
end # module
using .CocktailShakerSorts using BenchmarkTools
cocktailshakersort!(v) = sort!(v; alg=CocktailShakerSort)
arr = [5, 8, 2, 0, 6, 1, 9, 3, 4] println(arr, " => ", sort(arr, alg=CocktailShakerSort), " => ",
sort(arr, alg=CocktailShakerSort, rev=true))
println("\nUsing default sort, which is Quicksort with integers:") @btime sort!([5, 8, 2, 0, 6, 1, 9, 3, 4]) println("\nUsing CocktailShakerSort:") @btime cocktailshakersort!([5, 8, 2, 0, 6, 1, 9, 3, 4])
</lang>
- Output:
[5, 8, 2, 0, 6, 1, 9, 3, 4] => [0, 1, 2, 3, 4, 5, 6, 8, 9] Using default sort, which is Quicksort with integers: 56.765 ns (1 allocation: 160 bytes) Using CocktailShakerSort: 94.443 ns (1 allocation: 160 bytes)
Phix
Averages 7 or 8% better than Sorting_algorithms/Cocktail_sort#Phix which already shifted the bounds, however this shifts >1 (sometimes). <lang Phix>function cocktailShakerSort(sequence s)
integer beginIdx = 1,
endIdx = length(s)-1
while beginIdx <= endIdx do
integer newBeginIdx = endIdx,
newEndIdx = beginIdx
for ii=beginIdx to endIdx do
if s[ii]>s[ii+1] then
{s[ii+1],s[ii]} = {s[ii], s[ii+1]}
newEndIdx = ii
end if
end for
-- elements after `newEndIdx` are now in correct order
endIdx = newEndIdx - 1
for ii=endIdx to beginIdx by -1 do
if s[ii]>s[ii+1] then
{s[ii+1],s[ii]} = {s[ii],s[ii+1]}
newBeginIdx = ii
end if
end for
-- elements before `newBeginIdx` are now in correct order.
beginIdx = newBeginIdx + 1
end while
return s
end function sequence s = shuffle(tagset(12)) ?{s,cocktailShakerSort(s)} s = {"one","two","three","four"} ?{s,cocktailShakerSort(s)}</lang>
- Output:
{{12,2,1,9,4,10,8,5,3,11,6,7},{1,2,3,4,5,6,7,8,9,10,11,12}}
{{"one","two","three","four"},{"four","one","three","two"}}
Raku
<lang perl6>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';</lang>
REXX
This REXX version can handle array elements that may contain blanks or spaces. <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$; end$$= 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
VBA
<lang vb>' Sorting algorithms/Cocktail sort with shifting bounds - VBA
Function cocktailShakerSort(ByVal A As Variant) As Variant
beginIdx = LBound(A)
endIdx = UBound(A) - 1
Do While beginIdx <= endIdx
newBeginIdx = endIdx
newEndIdx = beginIdx
For ii = beginIdx To endIdx
If A(ii) > A(ii + 1) Then
tmp = A(ii): A(ii) = A(ii + 1): A(ii + 1) = tmp
newEndIdx = ii
End If
Next ii
endIdx = newEndIdx - 1
For ii = endIdx To beginIdx Step -1
If A(ii) > A(ii + 1) Then
tmp = A(ii): A(ii) = A(ii + 1): A(ii + 1) = tmp
newBeginIdx = ii
End If
Next ii
beginIdx = newBeginIdx + 1
Loop
cocktailShakerSort = A
End Function 'cocktailShakerSort
Public Sub main()
Dim B(20) As Variant
For i = LBound(B) To UBound(B)
B(i) = Int(Rnd() * 100)
Next i
Debug.Print Join(B, ", ")
Debug.Print Join(cocktailShakerSort(B), ", ")
End Sub</lang>
- Output:
52, 76, 5, 59, 46, 29, 62, 64, 26, 27, 82, 82, 58, 98, 91, 22, 69, 98, 24, 53, 10 5, 10, 22, 24, 26, 27, 29, 46, 52, 53, 58, 59, 62, 64, 69, 76, 82, 82, 91, 98, 98
VBScript
<lang vb>' Sorting algorithms/Cocktail sort with shifting bounds - VBScript
Function cocktailShakerSort(ByVal A)
beginIdx = Lbound(A)
endIdx = Ubound(A)-1
Do While beginIdx <= endIdx
newBeginIdx = endIdx
newEndIdx = beginIdx
For ii = beginIdx To endIdx
If A(ii) > A(ii+1) Then
tmp=A(ii) : A(ii)=A(ii+1) : A(ii+1)=tmp
newEndIdx = ii
End If
Next
endIdx = newEndIdx - 1
For ii = endIdx To beginIdx Step -1
If A(ii) > A(ii+1) Then
tmp=A(ii) : A(ii)=A(ii+1) : A(ii+1)=tmp
newBeginIdx = ii
End If
Next
beginIdx = newBeginIdx+1
Loop
cocktailShakerSort=A
End Function 'cocktailShakerSort
Dim B(20) For i=Lbound(B) To Ubound(B)
B(i)=Int(Rnd()*100)
Next Wscript.Echo Join(cocktailShakerSort(B)," ")
</lang>
- Output:
1 4 5 28 30 36 37 41 53 57 70 70 76 77 79 81 86 87 94 96
Visual Basic .NET
<lang vbnet>' Sorting algorithms/Cocktail sort with shifting bounds - VB.Net
Private Sub Cocktail_Shaker_Sort()
Dim A(20), tmp As Long 'or Integer Long Single Double String
Dim i, beginIdx, endIdx, newBeginIdx, newEndIdx As Integer
'Generate the list
For i = LBound(A) To UBound(A)
A(i) = Int(Rnd() * 100)
Next i
'Sort the list
beginIdx = LBound(A)
endIdx = UBound(A) - 1
Do While beginIdx <= endIdx
newBeginIdx = endIdx
newEndIdx = beginIdx
For ii = beginIdx To endIdx
If A(ii) > A(ii + 1) Then
tmp = A(ii) : A(ii) = A(ii + 1) : A(ii + 1) = tmp
newEndIdx = ii
End If
Next ii
endIdx = newEndIdx - 1
For ii = endIdx To beginIdx Step -1
If A(ii) > A(ii + 1) Then
tmp = A(ii) : A(ii) = A(ii + 1) : A(ii + 1) = tmp
newBeginIdx = ii
End If
Next ii
beginIdx = newBeginIdx + 1
Loop
'Display the sorted list
Debug.Print(String.Join(", ", A))
End Sub 'Cocktail_Shaker_Sort </lang>
- Output:
1, 4, 5, 28, 30, 36, 37, 41, 52, 53, 57, 70, 70, 76, 77, 79, 81, 86, 87, 94, 96