Sorting algorithms/Cocktail sort with shifting bounds

From Rosetta Code
Sorting algorithms/Cocktail sort with shifting bounds is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.

For other sorting algorithms, see Category:sorting algorithms, or:

O(n logn) sorts

Heapsort | Mergesort | Quicksort
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 | Bogosort | Counting sort | External sort | JortSort | Pancake sort | Permutation sort | Radix sort | Sleep sort | Stooge sort | Topological 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"   (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 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



360 Assembly[edit]

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.

*        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
Output:
 -31   0   1   2   2   4  45  58  65  69  74  82  82  83  88  89  99 104 112 782

ALGOL 60[edit]

Works with: A60
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
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


Go[edit]

If you run this a few times, the figures for 8K random numbers upwards are quite stable at around the levels shown.

package main
 
import (
"fmt"
"math/rand"
"time"
)
 
// translation of pseudo-code
func cocktailShakerSort(a []int) {
var begin = 0
var end = len(a) - 2
for begin <= end {
newBegin := end
newEnd := begin
for i := begin; i <= end; i++ {
if a[i] > a[i+1] {
a[i+1], a[i] = a[i], a[i+1]
newEnd = i
}
}
end = newEnd - 1
for i := end; i >= begin; i-- {
if a[i] > a[i+1] {
a[i+1], a[i] = a[i], a[i+1]
newBegin = i
}
}
begin = newBegin + 1
}
}
 
// from the RC Cocktail sort task (no optimizations)
func cocktailSort(a []int) {
last := len(a) - 1
for {
swapped := false
for i := 0; i < last; i++ {
if a[i] > a[i+1] {
a[i], a[i+1] = a[i+1], a[i]
swapped = true
}
}
if !swapped {
return
}
swapped = false
for i := last - 1; i >= 0; i-- {
if a[i] > a[i+1] {
a[i], a[i+1] = a[i+1], a[i]
swapped = true
}
}
if !swapped {
return
}
}
}
 
func main() {
// First make sure the routines are working correctly.
a := []int{21, 4, -9, 62, -7, 107, -62, 4, 0, -170}
fmt.Println("Original array:", a)
b := make([]int, len(a))
copy(b, a) // as sorts mutate array in place
cocktailSort(a)
fmt.Println("Cocktail sort :", a)
cocktailShakerSort(b)
fmt.Println("C/Shaker sort :", b)
 
// timing comparison code
rand.Seed(time.Now().UnixNano())
fmt.Println("\nRelative speed of the two sorts")
fmt.Println(" N x faster (CSS v CS)")
fmt.Println("----- -------------------")
const runs = 10 // average over 10 runs say
for _, n := range []int{1000, 2000, 4000, 8000, 10000, 20000} {
sum := 0.0
for i := 1; i <= runs; i++ {
// get 'n' random numbers in range [0, 100,000]
// with every other number being negated
nums := make([]int, n)
for i := 0; i < n; i++ {
rn := rand.Intn(100000)
if i%2 == 1 {
rn = -rn
}
nums[i] = rn
}
// copy the array
nums2 := make([]int, n)
copy(nums2, nums)
 
start := time.Now()
cocktailSort(nums)
elapsed := time.Since(start)
start2 := time.Now()
cocktailShakerSort(nums2)
elapsed2 := time.Since(start2)
sum += float64(elapsed) / float64(elapsed2)
}
fmt.Printf(" %2dk  %0.3f\n", n/1000, sum/runs)
}
}
Output:

Sample run:

Original array: [21 4 -9 62 -7 107 -62 4 0 -170]
Cocktail sort : [-170 -62 -9 -7 0 4 4 21 62 107]
C/Shaker sort : [-170 -62 -9 -7 0 4 4 21 62 107]

Relative speed of the two sorts
  N    x faster (CSS v CS)
-----  -------------------
  1k      1.439
  2k      1.480
  4k      1.415
  8k      1.330
 10k      1.326
 20k      1.302


Julia[edit]

The implementation chosen is to extend the native Julia base sort! function, which by default in base Julia supports insertion sort, quick sort, partial quick sort, and merge sort.

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])
 
Output:
[5, 8, 2, 0, 6, 1, 9, 3, 4] => [0, 1, 2, 3, 4, 5, 6, 8, 9] => [9, 8, 6, 5, 4, 3, 2, 1, 0]

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[edit]

Averages 7 or 8% better than Sorting_algorithms/Cocktail_sort#Phix which already shifted the bounds, however this shifts >1 (sometimes).

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)}
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[edit]

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';

REXX[edit]

This REXX version can handle array elements that may contain blanks or spaces.

/*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; [email protected].j; @.[email protected].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; [email protected].k; @.[email protected].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.*/
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[edit]

' 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
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[edit]

' 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)," ")
 
Output:
 1 4 5 28 30 36 37 41 53 57 70 70 76 77 79 81 86 87 94 96

Visual Basic .NET[edit]

Works with: Visual Basic .NET version 9.0
' 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
Output:
1, 4, 5, 28, 30, 36, 37, 41, 52, 53, 57, 70, 70, 76, 77, 79, 81, 86, 87, 94, 96

Wren[edit]

Translation of: Go
Library: Wren-fmt

Limited to 5 runs for each sample size as takes a few minutes to process.

Ratios are noticeably less than the Go example (more in keeping with the REXX results in the talk page) and vary more if the script is run a few times. Frankly, I don't know why this is.

import "/fmt" for Fmt
import "random" for Random
 
// translation of pseudo-code
var cocktailShakerSort = Fn.new { |a|
var begin = 0
var end = a.count - 2
while (begin <= end) {
var newBegin = end
var newEnd = begin
for (i in begin..end) {
if (a[i] > a[i+1]) {
var t = a[i+1]
a[i+1] = a[i]
a[i] = t
newEnd = i
}
}
end = newEnd - 1
if (end >= begin) {
for (i in end..begin) {
if (a[i] > a[i+1]) {
var t = a[i+1]
a[i+1] = a[i]
a[i] = t
newBegin = i
}
}
}
begin = newBegin + 1
}
}
 
// from the RC Cocktail sort task (no optimizations)
var cocktailSort = Fn.new { |a|
var last = a.count - 1
while (true) {
var swapped = false
for (i in 0...last) {
if (a[i] > a[i+1]) {
var t = a[i]
a[i] = a[i+1]
a[i+1] = t
swapped = true
}
}
if (!swapped) return
swapped = false
if (last >= 1) {
for (i in last-1..0) {
if (a[i] > a[i+1]) {
var t = a[i]
a[i] = a[i+1]
a[i+1] = t
swapped = true
}
}
}
if (!swapped) return
}
}
 
// First make sure the routines are working correctly.
var a = [21, 4, -9, 62, -7, 107, -62, 4, 0, -170]
System.print("Original array: %(a)")
var b = a.toList // make copy as sorts mutate array in place
cocktailSort.call(a)
System.print("Cocktail sort : %(a)")
cocktailShakerSort.call(b)
System.print("C/Shaker sort : %(b)")
 
// timing comparison code
var rand = Random.new()
System.print("\nRelative speed of the two sorts")
System.print(" N x faster (CSS v CS)")
System.print("----- -------------------")
var runs = 5 // average over 5 runs say
for (n in [1000, 2000, 4000, 8000, 10000, 20000]) {
var sum = 0
for (i in 1..runs) {
// get 'n' random numbers in range [0, 100,000]
// with every other number being negated
var nums = List.filled(n, 0)
for (i in 0...n) {
var rn = rand.int(100000)
if (i%2 == 1) rn = -rn
nums[i] = rn
}
// copy the array
var nums2 = nums.toList
 
var start = System.clock
cocktailSort.call(nums)
var elapsed = System.clock - start
var start2 = System.clock
cocktailShakerSort.call(nums2)
var elapsed2 = System.clock - start2
sum = sum + elapsed/elapsed2
}
System.print(" %(Fmt.d(2, (n/1000).floor))k  %(Fmt.f(0, sum/runs, 3))")
}
Output:

Sample run:

Original array: [21, 4, -9, 62, -7, 107, -62, 4, 0, -170]
Cocktail sort : [-170, -62, -9, -7, 0, 4, 4, 21, 62, 107]
C/Shaker sort : [-170, -62, -9, -7, 0, 4, 4, 21, 62, 107]

Relative speed of the two sorts
  N    x faster (CSS v CS)
-----  -------------------
  1k      1.257
  2k      1.223
  4k      1.212
  8k      1.216
 10k      1.239
 20k      1.228