Sorting algorithms/Cocktail sort with shifting bounds: Difference between revisions
Thundergnat (talk | contribs) (→{{header|Raku}}: Add a Raku example) |
m (→{{header|Wren}}: Minor tidy) |
||
(46 intermediate revisions by 21 users not shown) | |||
Line 1: | Line 1: | ||
{{ |
{{task|Sorting Algorithms}} |
||
{{Sorting Algorithm}} |
{{Sorting Algorithm}} |
||
[[Category:Sorting]] |
|||
{{Wikipedia|Cocktail sort}} |
{{Wikipedia|Cocktail sort}} |
||
<!-- |
<!-- |
||
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|||
Because the Rosetta Code task Cocktail sort had so many entries in it, |
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, |
adding an optional algorithm (or a stretch goal) wasn't feasible at this time, |
||
Line 10: | Line 13: | ||
-------------- Gerard Schildberger --------------------- |
-------------- Gerard Schildberger --------------------- |
||
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|||
!--> |
!--> |
||
Line 26: | Line 31: | ||
The improvement is basically that values "bubble" both directions through the |
The improvement is basically that values "bubble" (migrate) both directions through the |
||
array, because on each iteration the cocktail sort ''bubble sorts'' once |
array, because on each iteration the cocktail sort ''bubble sorts'' once |
||
forwards and once backwards. |
forwards and once backwards. |
||
Line 32: | Line 37: | ||
After ''ii'' passes, the first ''ii'' and the |
After ''ii'' passes, the first ''ii'' and the |
||
last ''ii'' elements in the array are in their correct |
last ''ii'' elements in the array are in their correct |
||
positions, and don't to be checked (again). |
positions, and don't have to be checked (again). |
||
By shortening the part of the array that is sorted each time, the number of |
By shortening the part of the array that is sorted each time, the number of |
||
Line 40: | Line 45: | ||
Pseudocode for the <big> 2<sup>nd</sup> </big> algorithm (from |
Pseudocode for the <big> 2<sup>nd</sup> </big> algorithm (from |
||
[[wp:Cocktail sort|Wikipedia]]) with an added comment and changed indentations: |
[[wp:Cocktail sort|Wikipedia]]) 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` and `endIdx` marks the first and last index to check. |
||
beginIdx = 1; |
beginIdx = 1; |
||
Line 70: | Line 75: | ||
beginIdx = newBeginIdx + 1; |
beginIdx = newBeginIdx + 1; |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
<big>'''%'''</big> indicates a comment, and '''deal''' indicates a ''swap''. |
<big>'''%'''</big> indicates a comment, and '''deal''' indicates a ''swap''. |
||
Line 83: | Line 88: | ||
:* [https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort cocktail sort] |
:* [https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort cocktail sort] |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="11l">F cocktailshiftingbounds(&A) |
|||
V beginIdx = 0 |
|||
V endIdx = A.len - 1 |
|||
L beginIdx <= endIdx |
|||
V newBeginIdx = endIdx |
|||
V newEndIdx = beginIdx |
|||
L(ii) beginIdx .< endIdx |
|||
I A[ii] > A[ii + 1] |
|||
swap(&A[ii + 1], &A[ii]) |
|||
newEndIdx = ii |
|||
endIdx = newEndIdx |
|||
L(ii) (endIdx .< beginIdx - 1).step(-1) |
|||
I A[ii] > A[ii + 1] |
|||
swap(&A[ii + 1], &A[ii]) |
|||
newBeginIdx = ii |
|||
beginIdx = newBeginIdx + 1 |
|||
V test1 = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0] |
|||
cocktailshiftingbounds(&test1) |
|||
print(test1)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] |
|||
</pre> |
|||
=={{header|360 Assembly}}== |
=={{header|360 Assembly}}== |
||
For maximum compatibility, this program uses only the basic instruction set. |
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. |
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. |
||
< |
<syntaxhighlight lang="360asm">* Cocktail sort with shifting bounds 10/05/2020 |
||
COCKSHIS CSECT |
COCKSHIS CSECT |
||
USING COCKSHIS,R13 base register |
USING COCKSHIS,R13 base register |
||
Line 170: | Line 206: | ||
REGEQU |
REGEQU |
||
RI EQU 6 i |
RI EQU 6 i |
||
END COCKSHIS </ |
END COCKSHIS </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782 |
-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782 |
||
</pre> |
|||
=={{header|AArch64 Assembly}}== |
|||
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
|||
<syntaxhighlight lang="aarch64 assembly"> |
|||
/* ARM assembly AARCH64 Raspberry PI 3B */ |
|||
/* program cocktailSortbound64.s */ |
|||
/*******************************************/ |
|||
/* Constantes file */ |
|||
/*******************************************/ |
|||
/* for this file see task include a file in language AArch64 assembly */ |
|||
.include "../includeConstantesARM64.inc" |
|||
/*********************************/ |
|||
/* Initialized data */ |
|||
/*********************************/ |
|||
.data |
|||
szMessSortOk: .asciz "Table sorted.\n" |
|||
szMessSortNok: .asciz "Table not sorted !!!!!.\n" |
|||
sMessResult: .asciz "Value : @ \n" |
|||
szCarriageReturn: .asciz "\n" |
|||
.align 4 |
|||
//TableNumber: .quad 1,3,6,2,5,9,10,8,4,7 |
|||
TableNumber: .quad 10,9,8,7,6,-5,4,3,2,1 |
|||
.equ NBELEMENTS, (. - TableNumber) / 8 |
|||
/*********************************/ |
|||
/* UnInitialized data */ |
|||
/*********************************/ |
|||
.bss |
|||
sZoneConv: .skip 24 |
|||
/*********************************/ |
|||
/* code section */ |
|||
/*********************************/ |
|||
.text |
|||
.global main |
|||
main: // entry of program |
|||
ldr x0,qAdrTableNumber // address number table |
|||
mov x1,0 |
|||
mov x2,NBELEMENTS // number of élements |
|||
bl cocktailSortBound |
|||
ldr x0,qAdrTableNumber // address number table |
|||
bl displayTable |
|||
ldr x0,qAdrTableNumber // address number table |
|||
mov x1,NBELEMENTS // number of élements |
|||
bl isSorted // control sort |
|||
cmp x0,1 // sorted ? |
|||
beq 1f |
|||
ldr x0,qAdrszMessSortNok // no !! error sort |
|||
bl affichageMess |
|||
b 100f |
|||
1: // yes |
|||
ldr x0,qAdrszMessSortOk |
|||
bl affichageMess |
|||
100: // standard end of the program |
|||
mov x0,0 // return code |
|||
mov x8,EXIT // request to exit program |
|||
svc 0 // perform the system call |
|||
qAdrsZoneConv: .quad sZoneConv |
|||
qAdrszCarriageReturn: .quad szCarriageReturn |
|||
qAdrsMessResult: .quad sMessResult |
|||
qAdrTableNumber: .quad TableNumber |
|||
qAdrszMessSortOk: .quad szMessSortOk |
|||
qAdrszMessSortNok: .quad szMessSortNok |
|||
/******************************************************************/ |
|||
/* control sorted table */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of table */ |
|||
/* x1 contains the number of elements > 0 */ |
|||
/* x0 return 0 if not sorted 1 if sorted */ |
|||
isSorted: |
|||
stp x2,lr,[sp,-16]! // save registers |
|||
stp x3,x4,[sp,-16]! // save registers |
|||
mov x2,0 |
|||
ldr x4,[x0,x2,lsl 3] |
|||
1: |
|||
add x2,x2,1 |
|||
cmp x2,x1 |
|||
bge 99f |
|||
ldr x3,[x0,x2, lsl 3] |
|||
cmp x3,x4 |
|||
blt 98f |
|||
mov x4,x3 |
|||
b 1b |
|||
98: |
|||
mov x0,0 // not sorted |
|||
b 100f |
|||
99: |
|||
mov x0,1 // sorted |
|||
100: |
|||
ldp x3,x4,[sp],16 // restaur 2 registers |
|||
ldp x2,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
/******************************************************************/ |
|||
/* cocktail sort Bound */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of table */ |
|||
/* x1 contains the first element */ |
|||
/* x2 contains the number of element */ |
|||
cocktailSortBound: |
|||
stp x1,lr,[sp,-16]! // save registers |
|||
stp x2,x3,[sp,-16]! // save registers |
|||
stp x4,x5,[sp,-16]! // save registers |
|||
stp x6,x7,[sp,-16]! // save registers |
|||
stp x8,x9,[sp,-16]! // save registers |
|||
sub x2,x2,2 // compute endidx = n - 2 |
|||
// and r1 = beginidx |
|||
1: // start loop 1 |
|||
cmp x1,x2 |
|||
bgt 100f |
|||
mov x8,x1 // newbeginidx |
|||
mov x7,x2 // newendidx |
|||
mov x3,x1 // start index |
|||
2: // start loop 2 |
|||
add x4,x3,1 |
|||
ldr x5,[x0,x3,lsl 3] // load value A[j] |
|||
ldr x6,[x0,x4,lsl 3] // load value A[j+1] |
|||
cmp x6,x5 // compare value |
|||
bge 3f |
|||
str x6,[x0,x3,lsl 3] // if smaller inversion |
|||
str x5,[x0,x4,lsl 3] |
|||
mov x7,x3 // and mov indice to newendidx |
|||
3: |
|||
add x3,x3,1 // increment index j |
|||
cmp x3,x2 // end ? |
|||
ble 2b // no -> loop 2 |
|||
sub x2,x7,1 // endidx = newendidx - 1 |
|||
bl displayTable |
|||
mov x3,x2 // indice |
|||
4: |
|||
add x4,x3,1 |
|||
ldr x5,[x0,x3,lsl 3] // load value A[j] |
|||
ldr x6,[x0,x4,lsl 3] // load value A[j+1] |
|||
cmp x6,x5 // compare value |
|||
bge 5f |
|||
str x6,[x0,x3,lsl 3] // if smaller inversion |
|||
str x5,[x0,x4,lsl 3] |
|||
mov x8,x3 // newbeginidx = indice |
|||
5: |
|||
sub x3,x3,1 // decrement index j |
|||
cmp x3,x1 // end ? |
|||
bge 4b // no -> loop 2 |
|||
add x1,x8,1 // beginidx = newbeginidx |
|||
b 1b // loop 1 |
|||
100: |
|||
ldp x8,x9,[sp],16 // restaur 2 registers |
|||
ldp x6,x7,[sp],16 // restaur 2 registers |
|||
ldp x4,x5,[sp],16 // restaur 2 registers |
|||
ldp x2,x3,[sp],16 // restaur 2 registers |
|||
ldp x1,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
/******************************************************************/ |
|||
/* Display table elements */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of table */ |
|||
displayTable: |
|||
stp x1,lr,[sp,-16]! // save registers |
|||
stp x2,x3,[sp,-16]! // save registers |
|||
mov x2,x0 // table address |
|||
mov x3,0 |
|||
1: // loop display table |
|||
ldr x0,[x2,x3,lsl 3] |
|||
ldr x1,qAdrsZoneConv |
|||
bl conversion10S // décimal conversion |
|||
ldr x0,qAdrsMessResult |
|||
ldr x1,qAdrsZoneConv |
|||
bl strInsertAtCharInc // insert result at @ character |
|||
bl affichageMess // display message |
|||
add x3,x3,1 |
|||
cmp x3,NBELEMENTS - 1 |
|||
ble 1b |
|||
ldr x0,qAdrszCarriageReturn |
|||
bl affichageMess |
|||
mov x0,x2 // table address |
|||
100: |
|||
ldp x2,x3,[sp],16 // restaur 2 registers |
|||
ldp x1,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
/********************************************************/ |
|||
/* File Include fonctions */ |
|||
/********************************************************/ |
|||
/* for this file see task include a file in language AArch64 assembly */ |
|||
.include "../includeARM64.inc" |
|||
</syntaxhighlight> |
|||
=={{header|Action!}}== |
|||
<syntaxhighlight lang="action!">PROC PrintArray(INT ARRAY a INT size) |
|||
INT i |
|||
Put('[) |
|||
FOR i=0 TO size-1 |
|||
DO |
|||
IF i>0 THEN Put(' ) FI |
|||
PrintI(a(i)) |
|||
OD |
|||
Put(']) PutE() |
|||
RETURN |
|||
PROC CoctailShakerSort(INT ARRAY a INT size) |
|||
INT begIdx,endIdx,newBegIdx,newEndIdx,i,tmp |
|||
begIdx=0 endIdx=size-2 |
|||
WHILE begIdx<=endIdx |
|||
DO |
|||
newBegIdx=endIdx |
|||
newEndIdx=begIdx |
|||
i=begIdx |
|||
WHILE i<=endIdx |
|||
DO |
|||
IF a(i)>a(i+1) THEN |
|||
tmp=a(i) a(i)=a(i+1) a(i+1)=tmp |
|||
newEndIdx=i |
|||
FI |
|||
i==+1 |
|||
OD |
|||
endIdx=newEndIdx-1 |
|||
i=endIdx |
|||
WHILE i>=begIdx |
|||
DO |
|||
IF a(i)>a(i+1) THEN |
|||
tmp=a(i) a(i)=a(i+1) a(i+1)=tmp |
|||
newBegIdx=i |
|||
FI |
|||
i==-1 |
|||
OD |
|||
begIdx=newBegIdx+1 |
|||
OD |
|||
RETURN |
|||
PROC Test(INT ARRAY a INT size) |
|||
PrintE("Array before sort:") |
|||
PrintArray(a,size) |
|||
CoctailShakerSort(a,size) |
|||
PrintE("Array after sort:") |
|||
PrintArray(a,size) |
|||
PutE() |
|||
RETURN |
|||
PROC Main() |
|||
INT ARRAY |
|||
a(10)=[1 4 65535 0 3 7 4 8 20 65530], |
|||
b(21)=[10 9 8 7 6 5 4 3 2 1 0 |
|||
65535 65534 65533 65532 65531 |
|||
65530 65529 65528 65527 65526], |
|||
c(8)=[101 102 103 104 105 106 107 108], |
|||
d(12)=[1 65535 1 65535 1 65535 1 |
|||
65535 1 65535 1 65535] |
|||
Test(a,10) |
|||
Test(b,21) |
|||
Test(c,8) |
|||
Test(d,12) |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Cocktail_sort_with_shifting_bounds.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
Array before sort: |
|||
[1 4 -1 0 3 7 4 8 20 -6] |
|||
Array after sort: |
|||
[-6 -1 0 1 3 4 4 7 8 20] |
|||
Array before sort: |
|||
[10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10] |
|||
Array after sort: |
|||
[-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10] |
|||
Array before sort: |
|||
[101 102 103 104 105 106 107 108] |
|||
Array after sort: |
|||
[101 102 103 104 105 106 107 108] |
|||
Array before sort: |
|||
[1 -1 1 -1 1 -1 1 -1 1 -1 1 -1] |
|||
Array after sort: |
|||
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1] |
|||
</pre> |
</pre> |
||
=={{header|ALGOL 60}}== |
=={{header|ALGOL 60}}== |
||
{{works with|A60}} |
{{works with|A60}} |
||
< |
<syntaxhighlight lang="algol60">begin |
||
comment Sorting algorithms/Cocktail sort - Algol 60; |
comment Sorting algorithms/Cocktail sort with shifting bounds - Algol 60; |
||
integer nA; |
|||
nA:=20; |
|||
procedure cocktailsort(lb,ub); |
|||
value lb,ub; integer lb,ub; |
|||
begin |
begin |
||
integer |
integer array A[1:nA]; |
||
boolean swapped; |
|||
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 |
|||
A[i] :=A[i+1]; |
|||
A[i+1]:=temp; |
|||
swapped:=true |
|||
end swap; |
|||
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); |
for i:=lbx step 1 until ubx do if A[i]>A[i+1] then swap(i); |
||
if swapped |
if swapped |
||
then begin |
then begin |
||
for i:=ubx step -1 until lbx do if A[i]>A[i+1] then swap(i); |
for i:=ubx step -1 until lbx do if A[i]>A[i+1] then swap(i); |
||
ubx:=ubx-1; lbx:=lbx+1 |
ubx:=ubx-1; lbx:=lbx+1 |
||
end |
|||
end |
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 |
|||
end </syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
|||
Based on the pseudo-code with test cases from the Action! sample. |
|||
<syntaxhighlight lang="algol68"> |
|||
BEGIN # cocktail sort with shifting bounds # |
|||
# sorts data, using a cocktail sort with shifting bounds # |
|||
# a reference to the sorted data is returned # |
|||
# - defined as an operator as Algol 68 has operator overloading but not # |
|||
# procedure overloading # |
|||
# (similar operators with the same name could be defined for other types # |
|||
# of array) # |
|||
OP COCKTAILSORTSB = ( []INT data )REF[]INT: |
|||
BEGIN |
|||
# make a copy of the data # |
|||
REF[]INT a := HEAP[ LWB data : UPB data ]INT := data; |
|||
# `beginIdx` and `endIdx` marks the first and last index to check. # |
|||
INT begin idx := LWB a; |
|||
INT end idx := UPB a - 1; |
|||
WHILE begin idx <= end idx DO |
|||
INT new begin idx := end idx; |
|||
INT new end idx := begin idx; |
|||
FOR ii FROM begin idx TO end idx DO |
|||
IF a[ ii ] > a[ ii + 1 ] THEN |
|||
INT aii = a[ ii ]; |
|||
a[ ii ] := a[ ii + 1 ]; |
|||
a[ ii + 1 ] := aii; |
|||
new end idx := ii |
|||
FI |
|||
OD; |
|||
# decreases `endIdx` because the elements after `newEndIdx` are in correct order # |
|||
end idx := new end idx - 1; |
|||
FOR ii FROM end idx BY -1 TO begin idx DO |
|||
IF a[ ii ] > a[ ii + 1 ] THEN |
|||
INT aii = a[ ii ]; |
|||
a[ ii ] := a[ ii + 1 ]; |
|||
a[ ii + 1 ] := aii; |
|||
new begin idx := ii |
|||
FI |
|||
OD; |
|||
# increases `beginIdx` because the elements before `newBeginIdx` are in correct order. # |
|||
begin idx := new begin idx + 1 |
|||
OD; |
|||
a |
|||
END # COCKTAILSORTSB # ; |
|||
# test the COCKTAILSORTSB operator # |
|||
PROC test cocktail sort with shifting bounds = ( []INT data )VOID: |
|||
BEGIN |
|||
REF[]INT sorted := COCKTAILSORTSB data; |
|||
print( ( "[" ) ); |
|||
FOR i FROM LWB data TO UPB data DO print( ( " ", whole( data[ i ], 0 ) ) ) OD; |
|||
print( ( " ]", newline, " -> [" ) ); |
|||
FOR i FROM LWB sorted TO UPB sorted DO print( ( " ", whole( sorted[ i ], 0 ) ) ) OD; |
|||
print( ( " ]", newline ) ) |
|||
END # test cocktail sort with shifting bounds # ; |
|||
# test cases from the Action! sample # |
|||
test cocktail sort with shifting bounds( ( 1, 4, -1, 0, 3, 7, 4, 8, 20, -6 ) ); |
|||
test cocktail sort with shifting bounds( ( 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
|||
, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10 |
|||
) |
|||
); |
|||
test cocktail sort with shifting bounds( ( 101, 102, 103, 104, 105, 106, 107, 108 ) ); |
|||
test cocktail sort with shifting bounds( ( 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1 ) ); |
|||
# additional test cases # |
|||
test cocktail sort with shifting bounds( ( 1, 1, 1, 1, 1, 1 ) ); |
|||
test cocktail sort with shifting bounds( ( 0 ) ); |
|||
test cocktail sort with shifting bounds( () ) |
|||
END |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[ 1 4 -1 0 3 7 4 8 20 -6 ] |
|||
-> [ -6 -1 0 1 3 4 4 7 8 20 ] |
|||
[ 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ] |
|||
-> [ -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 ] |
|||
[ 101 102 103 104 105 106 107 108 ] |
|||
-> [ 101 102 103 104 105 106 107 108 ] |
|||
[ 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ] |
|||
-> [ -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 ] |
|||
[ 1 1 1 1 1 1 ] |
|||
-> [ 1 1 1 1 1 1 ] |
|||
[ 0 ] |
|||
-> [ 0 ] |
|||
[ ] |
|||
-> [ ] |
|||
</pre> |
|||
=={{header|ALGOL W}}== |
|||
Based on the pseudo-code - test code based on the Algol 68 test code. |
|||
<syntaxhighlight lang="algolw"> |
|||
begin % cocktail sort with shifting bounds % |
|||
% sorts in-place a using a cocktail sort with shifting bounds % |
|||
% the bounds of a must be specified in lb and ub % |
|||
procedure cocktailSortWithShiftingBounds ( integer array a ( * ) |
|||
; integer value lb, ub |
|||
); |
|||
begin |
begin |
||
% `beginIdx` and `endIdx` marks the first and last index to check. % |
|||
integer i; |
|||
integer beginIdx, endIdx; |
|||
for i:=lb step 1 until ub do A[i]:=entier(rand*100) |
|||
beginIdx := lb; |
|||
endIdx := ub - 1; |
|||
procedure writetable(lb,ub); |
|||
while beginIdx <= endIdx do begin |
|||
value lb,ub; integer lb,ub; |
|||
integer newBeginIdx, newEndIdx; |
|||
newBeginIdx := endIdx; |
|||
newEndIdx := beginIdx; |
|||
for ii := beginIdx until endIdx do begin |
|||
integer aii; |
|||
if a( ii ) > a( ii + 1 ) then begin |
|||
integer aii; |
|||
aii := a( ii ); |
|||
a( ii ) := a( ii + 1 ); |
|||
a( ii + 1 ) := aii; |
|||
newEndIdx := ii |
|||
end |
|||
end for_ii ; |
|||
% decreases `endIdx` because the elements after `newEndIdx` are in correct order % |
|||
endIdx := newEndIdx - 1; |
|||
for ii := endIdx step -1 until beginIdx do begin |
|||
if a( ii ) > a( ii + 1 ) then begin |
|||
integer aii; |
|||
aii := a( ii ); |
|||
a( ii ) := a( ii + 1 ); |
|||
a( ii + 1 ) := aii; |
|||
newBeginIdx := ii |
|||
end |
|||
end for_ii ; |
|||
% increases `beginIdx` because the elements before `newBeginIdx` are in correct order. % |
|||
beginIdx := newBeginIdx + 1 |
|||
end while_beginIdx_le_endIdx |
|||
end coctailSortWithShiftingBounds ; |
|||
% test the cocktailSortWithShiftingBounds procedure % |
|||
begin |
begin |
||
integer i; |
|||
integer procedure inc ( integer value result i ) ; |
|||
begin |
|||
i := i + 1; |
|||
i |
|||
end inc ; |
|||
procedure testCocktailSortWithShiftingBounds( integer array data ( * ) |
|||
; integer value lb, ub |
|||
); |
|||
begin |
|||
i_w := 1; s_w := 0; % set formatting % |
|||
write( "[" ); |
|||
for i := lb until ub do writeon( " ", data( i ) ); |
|||
writeon( " ]" ); |
|||
cocktailSortWithShiftingBounds( data, lb, ub ); |
|||
write( " -> [" ); |
|||
for i := lb until ub do writeon( " ", data( i ) ); |
|||
writeon( " ]" ) |
|||
end testCocktailSortWithShiftingBounds ; |
|||
integer array t ( 1 :: 32 ); |
|||
integer tPos; |
|||
% test cases from the Action! sample % |
|||
tPos := 0; |
|||
for d := 1, 4, -1, 0, 3, 7, 4, 8, 20, -6 do t( inc( tPos ) ) := d; |
|||
testCocktailSortWithShiftingBounds( t, 1, tPos ); |
|||
tPos := 0; |
|||
for d := 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
|||
, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10 |
|||
do t( inc( tPos ) ) := d; |
|||
testCocktailSortWithShiftingBounds( t, 1, tPos ); |
|||
tPos := 0; |
|||
for d := 101, 102, 103, 104, 105, 106, 107, 108 do t( inc( tPos ) ) := d; |
|||
testCocktailSortWithShiftingBounds( t, 1, tPos ); |
|||
tPos := 0; |
|||
for d := 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1 do t( inc( tPos ) ) := d; |
|||
testCocktailSortWithShiftingBounds( t, 1, tPos ); |
|||
% additional test cases % |
|||
tPos := 0; |
|||
for d := 1, 1, 1, 1, 1, 1 do t( inc( tPos ) ) := d; |
|||
testCocktailSortWithShiftingBounds( t, 1, tPos ); |
|||
tPos := 0; |
|||
for d := 0 do t( inc( tPos ) ) := d; |
|||
testCocktailSortWithShiftingBounds( t, 1, tPos ); |
|||
tPos := 0; |
|||
testCocktailSortWithShiftingBounds( t, 1, tPos ); |
|||
end |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[ 1 4 -1 0 3 7 4 8 20 -6 ] |
|||
-> [ -6 -1 0 1 3 4 4 7 8 20 ] |
|||
[ 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ] |
|||
-> [ -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 ] |
|||
[ 101 102 103 104 105 106 107 108 ] |
|||
-> [ 101 102 103 104 105 106 107 108 ] |
|||
[ 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ] |
|||
-> [ -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 ] |
|||
[ 1 1 1 1 1 1 ] |
|||
-> [ 1 1 1 1 1 1 ] |
|||
[ 0 ] |
|||
-> [ 0 ] |
|||
[ ] |
|||
-> [ ] |
|||
</pre> |
|||
=={{header|ARM Assembly}}== |
|||
{{works with|as|Raspberry Pi}} |
|||
<syntaxhighlight lang="arm assembly"> |
|||
/* ARM assembly Raspberry PI */ |
|||
/* program cocktailSortBound.s */ |
|||
/* REMARK 1 : this program use routines in a include file |
|||
see task Include a file language arm assembly |
|||
for the routine affichageMess conversion10 |
|||
see at end of this program the instruction include */ |
|||
/* for constantes see task include a file in arm assembly */ |
|||
/************************************/ |
|||
/* Constantes */ |
|||
/************************************/ |
|||
.include "../constantes.inc" |
|||
/*********************************/ |
|||
/* Initialized data */ |
|||
/*********************************/ |
|||
.data |
|||
szMessSortOk: .asciz "Table sorted.\n" |
|||
szMessSortNok: .asciz "Table not sorted !!!!!.\n" |
|||
sMessResult: .asciz "Value : @ \n" |
|||
szCarriageReturn: .asciz "\n" |
|||
.align 4 |
|||
TableNumber: .int 1,3,6,2,5,9,10,8,4,7 |
|||
#TableNumber: .int 10,9,8,7,6,-5,4,3,2,1 |
|||
.equ NBELEMENTS, (. - TableNumber) / 4 |
|||
/*********************************/ |
|||
/* UnInitialized data */ |
|||
/*********************************/ |
|||
.bss |
|||
sZoneConv: .skip 24 |
|||
/*********************************/ |
|||
/* code section */ |
|||
/*********************************/ |
|||
.text |
|||
.global main |
|||
main: @ entry of program |
|||
1: |
|||
ldr r0,iAdrTableNumber @ address number table |
|||
mov r1,#0 |
|||
mov r2,#NBELEMENTS @ number of élements |
|||
bl cocktailSortBound |
|||
ldr r0,iAdrTableNumber @ address number table |
|||
bl displayTable |
|||
ldr r0,iAdrTableNumber @ address number table |
|||
mov r1,#NBELEMENTS @ number of élements |
|||
bl isSorted @ control sort |
|||
cmp r0,#1 @ sorted ? |
|||
beq 2f |
|||
ldr r0,iAdrszMessSortNok @ no !! error sort |
|||
bl affichageMess |
|||
b 100f |
|||
2: @ yes |
|||
ldr r0,iAdrszMessSortOk |
|||
bl affichageMess |
|||
100: @ standard end of the program |
|||
mov r0, #0 @ return code |
|||
mov r7, #EXIT @ request to exit program |
|||
svc #0 @ perform the system call |
|||
iAdrszCarriageReturn: .int szCarriageReturn |
|||
iAdrsMessResult: .int sMessResult |
|||
iAdrTableNumber: .int TableNumber |
|||
iAdrszMessSortOk: .int szMessSortOk |
|||
iAdrszMessSortNok: .int szMessSortNok |
|||
/******************************************************************/ |
|||
/* control sorted table */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of table */ |
|||
/* r1 contains the number of elements > 0 */ |
|||
/* r0 return 0 if not sorted 1 if sorted */ |
|||
isSorted: |
|||
push {r2-r4,lr} @ save registers |
|||
mov r2,#0 |
|||
ldr r4,[r0,r2,lsl #2] |
|||
1: |
|||
add r2,#1 |
|||
cmp r2,r1 |
|||
movge r0,#1 |
|||
bge 100f |
|||
ldr r3,[r0,r2, lsl #2] |
|||
cmp r3,r4 |
|||
movlt r0,#0 |
|||
blt 100f |
|||
mov r4,r3 |
|||
b 1b |
|||
100: |
|||
pop {r2-r4,lr} |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* cocktail Sort */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of table */ |
|||
/* r1 contains the first element */ |
|||
/* r2 contains the number of element */ |
|||
cocktailSortBound: |
|||
push {r1-r9,lr} @ save registers |
|||
sub r2,r2,#2 @ compute endidx = n - 2 |
|||
@ and r1= beginidx |
|||
1: @ start loop 1 |
|||
cmp r1,r2 @ compare endidx beginidx |
|||
bgt 100f |
|||
mov r8,r1 @ newbeginidx |
|||
mov r7,r2 @ newendidx |
|||
mov r3,r1 @ indice |
|||
2: @ start loop 2 |
|||
add r4,r3,#1 |
|||
ldr r5,[r0,r3,lsl #2] @ load value A[j] |
|||
ldr r6,[r0,r4,lsl #2] @ load value A[j+1] |
|||
cmp r6,r5 @ compare value |
|||
strlt r6,[r0,r3,lsl #2] @ if smaller inversion |
|||
strlt r5,[r0,r4,lsl #2] |
|||
movlt r7,r3 @ and mov indice to newendidx |
|||
add r3,#1 @ increment indice |
|||
cmp r3,r2 @ end ? |
|||
ble 2b @ no -> loop 2 |
|||
sub r2,r7,#1 @ endidx = newendidx |
|||
//bl displayTable |
|||
mov r3,r2 @ indice |
|||
3: |
|||
add r4,r3,#1 |
|||
ldr r5,[r0,r3,lsl #2] @ load value A[j] |
|||
ldr r6,[r0,r4,lsl #2] @ load value A[j+1] |
|||
cmp r6,r5 @ compare value |
|||
strlt r6,[r0,r3,lsl #2] @ if smaller inversion |
|||
strlt r5,[r0,r4,lsl #2] |
|||
movlt r8,r3 @ newbeginidx = indice |
|||
sub r3,#1 @ decrement indice |
|||
cmp r3,r1 @ end ? |
|||
bge 3b @ no -> loop 3 |
|||
//bl displayTable |
|||
nA=20; |
|||
add r1,r8,#1 @ beginidx = newbeginidx + 1 |
|||
inittable(1,nA); |
|||
b 1b @ loop 1 |
|||
writetable(1,nA); |
|||
cocktailsort(1,nA); |
|||
100: |
|||
writetable(1,nA) |
|||
pop {r1-r9,lr} |
|||
end </lang> |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* Display table elements */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of table */ |
|||
displayTable: |
|||
push {r0-r3,lr} @ save registers |
|||
mov r2,r0 @ table address |
|||
mov r3,#0 |
|||
1: @ loop display table |
|||
ldr r0,[r2,r3,lsl #2] |
|||
ldr r1,iAdrsZoneConv @ |
|||
bl conversion10S @ décimal conversion |
|||
ldr r0,iAdrsMessResult |
|||
ldr r1,iAdrsZoneConv @ insert conversion |
|||
bl strInsertAtCharInc |
|||
bl affichageMess @ display message |
|||
add r3,#1 |
|||
cmp r3,#NBELEMENTS - 1 |
|||
ble 1b |
|||
ldr r0,iAdrszCarriageReturn |
|||
bl affichageMess |
|||
100: |
|||
pop {r0-r3,lr} |
|||
bx lr |
|||
iAdrsZoneConv: .int sZoneConv |
|||
/***************************************************/ |
|||
/* ROUTINES INCLUDE */ |
|||
/***************************************************/ |
|||
.include "../affichage.inc" |
|||
</syntaxhighlight> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">cocktailShiftSort: function [items][ |
|||
a: new items |
|||
beginIdx: 0 |
|||
endIdx: (size a)-2 |
|||
while [beginIdx =< endIdx][ |
|||
newBeginIdx: endIdx |
|||
newEndIdx: beginIdx |
|||
loop beginIdx..endIdx 'i [ |
|||
if a\[i] > a\[i+1] [ |
|||
tmp: a\[i] |
|||
a\[i]: a\[i+1] |
|||
a\[i+1]: tmp |
|||
newEndIdx: i |
|||
] |
|||
] |
|||
endIdx: newEndIdx - 1 |
|||
loop endIdx..beginIdx 'i [ |
|||
if a\[i] > a\[i+1] [ |
|||
tmp: a\[i] |
|||
a\[i]: a\[i+1] |
|||
a\[i+1]: tmp |
|||
newBeginIdx: i |
|||
] |
|||
] |
|||
beginIdx: newBeginIdx - 1 |
|||
] |
|||
return a |
|||
] |
|||
print cocktailShiftSort [3 1 2 8 5 7 9 4 6]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>1 2 3 4 5 6 7 8 9</pre> |
|||
=={{header|AutoHotkey}}== |
|||
<syntaxhighlight lang="autohotkey">cocktailShakerSort(A){ |
|||
beginIdx := 1 |
|||
endIdx := A.Count() - 1 |
|||
while (beginIdx <= endIdx) { |
|||
newBeginIdx := endIdx |
|||
newEndIdx := beginIdx |
|||
ii := beginIdx |
|||
while (ii <= endIdx) { |
|||
if (A[ii] > A[ii + 1]) { |
|||
tempVal := A[ii], A[ii] := A[ii+1], A[ii+1] := tempVal |
|||
newEndIdx := ii |
|||
} |
|||
ii++ |
|||
} |
|||
endIdx := newEndIdx - 1 |
|||
ii := endIdx |
|||
while (ii >= beginIdx) { |
|||
if (A[ii] > A[ii + 1]) { |
|||
tempVal := A[ii], A[ii] := A[ii+1], A[ii+1] := tempVal |
|||
newBeginIdx := ii |
|||
} |
|||
ii-- |
|||
} |
|||
beginIdx := newBeginIdx + 1 |
|||
} |
|||
}</syntaxhighlight> |
|||
Examples:<syntaxhighlight lang="autohotkey">A := [8,6,4,3,5,2,7,1] |
|||
cocktailShakerSort(A) |
|||
for k, v in A |
|||
output .= v ", " |
|||
MsgBox % "[" Trim(output, ", ") "]" ; show output</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
=={{header|C}}== |
|||
<syntaxhighlight lang="c">#include <stdio.h> |
|||
#include <string.h> |
|||
void swap(char* p1, char* p2, size_t size) { |
|||
for (; size-- > 0; ++p1, ++p2) { |
|||
char tmp = *p1; |
|||
*p1 = *p2; |
|||
*p2 = tmp; |
|||
} |
|||
} |
|||
void cocktail_shaker_sort(void* base, size_t count, size_t size, |
|||
int (*cmp)(const void*, const void*)) { |
|||
char* begin = base; |
|||
char* end = base + size * count; |
|||
if (end == begin) |
|||
return; |
|||
for (end -= size; begin < end; ) { |
|||
char* new_begin = end; |
|||
char* new_end = begin; |
|||
for (char* p = begin; p < end; p += size) { |
|||
char* q = p + size; |
|||
if (cmp(p, q) > 0) { |
|||
swap(p, q, size); |
|||
new_end = p; |
|||
} |
|||
} |
|||
end = new_end; |
|||
for (char* p = end; p > begin; p -= size) { |
|||
char* q = p - size; |
|||
if (cmp(q, p) > 0) { |
|||
swap(p, q, size); |
|||
new_begin = p; |
|||
} |
|||
} |
|||
begin = new_begin; |
|||
} |
|||
} |
|||
int string_compare(const void* p1, const void* p2) { |
|||
const char* const* s1 = p1; |
|||
const char* const* s2 = p2; |
|||
return strcmp(*s1, *s2); |
|||
} |
|||
void print(const char** a, size_t len) { |
|||
for (size_t i = 0; i < len; ++i) |
|||
printf("%s ", a[i]); |
|||
printf("\n"); |
|||
} |
|||
int main() { |
|||
const char* a[] = { "one", "two", "three", "four", "five", |
|||
"six", "seven", "eight" }; |
|||
const size_t len = sizeof(a)/sizeof(a[0]); |
|||
printf("before: "); |
|||
print(a, len); |
|||
cocktail_shaker_sort(a, len, sizeof(char*), string_compare); |
|||
printf("after: "); |
|||
print(a, len); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
before: one two three four five six seven eight |
|||
6 92 61 64 73 3 81 28 62 67 83 33 77 14 16 23 47 19 33 78 |
|||
after: eight five four one seven six three two |
|||
3 6 14 16 19 23 28 33 33 47 61 62 64 67 73 77 78 81 83 92 |
|||
</pre> |
</pre> |
||
=={{header|C++}}== |
|||
<syntaxhighlight lang="cpp">#include <algorithm> |
|||
#include <cassert> |
|||
#include <iostream> |
|||
#include <iterator> |
|||
#include <vector> |
|||
// This only works for random access iterators |
|||
template <typename iterator> |
|||
void cocktail_shaker_sort(iterator begin, iterator end) { |
|||
if (begin == end) |
|||
return; |
|||
for (--end; begin < end; ) { |
|||
iterator new_begin = end; |
|||
iterator new_end = begin; |
|||
for (iterator i = begin; i < end; ++i) { |
|||
iterator j = i + 1; |
|||
if (*j < *i) { |
|||
std::iter_swap(i, j); |
|||
new_end = i; |
|||
} |
|||
} |
|||
end = new_end; |
|||
for (iterator i = end; i > begin; --i) { |
|||
iterator j = i - 1; |
|||
if (*i < *j) { |
|||
std::iter_swap(i, j); |
|||
new_begin = i; |
|||
} |
|||
} |
|||
begin = new_begin; |
|||
} |
|||
} |
|||
template <typename iterator> |
|||
void print(iterator begin, iterator end) { |
|||
if (begin == end) |
|||
return; |
|||
std::cout << *begin++; |
|||
while (begin != end) |
|||
std::cout << ' ' << *begin++; |
|||
std::cout << '\n'; |
|||
} |
|||
int main() { |
|||
std::vector<int> v{5, 1, -6, 12, 3, 13, 2, 4, 0, 15}; |
|||
std::cout << "before: "; |
|||
print(v.begin(), v.end()); |
|||
cocktail_shaker_sort(v.begin(), v.end()); |
|||
assert(std::is_sorted(v.begin(), v.end())); |
|||
std::cout << "after: "; |
|||
print(v.begin(), v.end()); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
before: 5 1 -6 12 3 13 2 4 0 15 |
|||
after: -6 0 1 2 3 4 5 12 13 15 |
|||
</pre> |
|||
=={{header|FreeBASIC}}== |
|||
{{trans|VBA}} |
|||
<syntaxhighlight lang="freebasic"> |
|||
Sub cocktailShakerSort(bs() As Long) |
|||
Dim As Long i, lb = Lbound(bs), ub = Ubound(bs) -1 |
|||
Dim As Long newlb, newub, tmp |
|||
Do While lb <= ub |
|||
newlb = ub |
|||
newub = lb |
|||
For i = lb To ub |
|||
If bs(i) > bs(i + 1) Then |
|||
tmp = bs(i): bs(i) = bs(i + 1): bs(i + 1) = tmp |
|||
newub = i |
|||
End If |
|||
Next i |
|||
ub = newub - 1 |
|||
For i = ub To lb Step -1 |
|||
If bs(i) > bs(i + 1) Then |
|||
tmp = bs(i): bs(i) = bs(i + 1): bs(i + 1) = tmp |
|||
newlb = i |
|||
End If |
|||
Next i |
|||
lb = newlb + 1 |
|||
Loop |
|||
End Sub |
|||
'--- Programa Principal --- |
|||
Dim As Long i, array(-7 To 7) |
|||
Dim As Long a = Lbound(array), b = Ubound(array) |
|||
Randomize Timer |
|||
For i = a To b : array(i) = i : Next i |
|||
For i = a To b |
|||
Swap array(i), array(Int(Rnd * (b - a + 1)) + a) |
|||
Next i |
|||
Print "unsort "; |
|||
For i = a To b : Print Using "####"; array(i); : Next i |
|||
cocktailShakerSort(array()) ' ordenar el array |
|||
Print !"\n sort "; |
|||
For i = a To b : Print Using "####"; array(i); : Next i |
|||
Print !"\n--- terminado, pulsa RETURN---" |
|||
Sleep |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
unsort -4 0 5 -7 -2 4 3 -5 -1 7 2 1 6 -3 -6 |
|||
sort -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 |
|||
</pre> |
|||
=={{header|Go}}== |
|||
If you run this a few times, the figures for 8K random numbers upwards are quite stable at around the levels shown. |
|||
<syntaxhighlight lang="go">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) |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
Sample run: |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Groovy}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="groovy">class CocktailSort { |
|||
static void main(String[] args) { |
|||
Integer[] array = [ 5, 1, -6, 12, 3, 13, 2, 4, 0, 15 ] |
|||
println("before: " + Arrays.toString(array)) |
|||
cocktailSort(array) |
|||
println("after: " + Arrays.toString(array)) |
|||
} |
|||
// Sorts an array of elements that implement the Comparable interface |
|||
static void cocktailSort(Object[] array) { |
|||
int begin = 0 |
|||
int end = array.length |
|||
if (end == 0) { |
|||
return |
|||
} |
|||
for (--end; begin < end; ) { |
|||
int new_begin = end |
|||
int new_end = begin |
|||
for (int i = begin; i < end; ++i) { |
|||
Comparable c1 = (Comparable)array[i] |
|||
Comparable c2 = (Comparable)array[i + 1] |
|||
if (c1 > c2) { |
|||
swap(array, i, i + 1) |
|||
new_end = i |
|||
} |
|||
} |
|||
end = new_end |
|||
for (int i = end; i > begin; --i) { |
|||
Comparable c1 = (Comparable)array[i - 1] |
|||
Comparable c2 = (Comparable)array[i] |
|||
if (c1 > c2) { |
|||
swap(array, i, i - 1) |
|||
new_begin = i |
|||
} |
|||
} |
|||
begin = new_begin |
|||
} |
|||
} |
|||
private static void swap(Object[] array, int i, int j) { |
|||
Object tmp = array[i] |
|||
array[i] = array[j] |
|||
array[j] = tmp |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>before: [5, 1, -6, 12, 3, 13, 2, 4, 0, 15] |
|||
after: [-6, 0, 1, 2, 3, 4, 5, 12, 13, 15]</pre> |
|||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java">import java.util.*; |
|||
public class CocktailSort { |
|||
public static void main(String[] args) { |
|||
Integer[] array = new Integer[]{ 5, 1, -6, 12, 3, 13, 2, 4, 0, 15 }; |
|||
System.out.println("before: " + Arrays.toString(array)); |
|||
cocktailSort(array); |
|||
System.out.println("after: " + Arrays.toString(array)); |
|||
} |
|||
// Sorts an array of elements that implement the Comparable interface |
|||
public static void cocktailSort(Object[] array) { |
|||
int begin = 0; |
|||
int end = array.length; |
|||
if (end == 0) |
|||
return; |
|||
for (--end; begin < end; ) { |
|||
int new_begin = end; |
|||
int new_end = begin; |
|||
for (int i = begin; i < end; ++i) { |
|||
Comparable c1 = (Comparable)array[i]; |
|||
Comparable c2 = (Comparable)array[i + 1]; |
|||
if (c1.compareTo(c2) > 0) { |
|||
swap(array, i, i + 1); |
|||
new_end = i; |
|||
} |
|||
} |
|||
end = new_end; |
|||
for (int i = end; i > begin; --i) { |
|||
Comparable c1 = (Comparable)array[i - 1]; |
|||
Comparable c2 = (Comparable)array[i]; |
|||
if (c1.compareTo(c2) > 0) { |
|||
swap(array, i, i - 1); |
|||
new_begin = i; |
|||
} |
|||
} |
|||
begin = new_begin; |
|||
} |
|||
} |
|||
private static void swap(Object[] array, int i, int j) { |
|||
Object tmp = array[i]; |
|||
array[i] = array[j]; |
|||
array[j] = tmp; |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
before: [5, 1, -6, 12, 3, 13, 2, 4, 0, 15] |
|||
after: [-6, 0, 1, 2, 3, 4, 5, 12, 13, 15] |
|||
</pre> |
|||
=={{header|Julia}}== |
|||
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. |
|||
<syntaxhighlight 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]) |
|||
</syntaxhighlight>{{out}} |
|||
<pre> |
|||
[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) |
|||
</pre> |
|||
=={{header|Kotlin}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="scala">fun <T> swap(array: Array<T>, i: Int, j: Int) { |
|||
val temp = array[i] |
|||
array[i] = array[j] |
|||
array[j] = temp |
|||
} |
|||
fun <T> cocktailSort(array: Array<T>) where T : Comparable<T> { |
|||
var begin = 0 |
|||
var end = array.size |
|||
if (end == 0) { |
|||
return |
|||
} |
|||
--end |
|||
while (begin < end) { |
|||
var newBegin = end |
|||
var newEnd = begin |
|||
for (i in begin until end) { |
|||
val c1 = array[i] |
|||
val c2 = array[i + 1] |
|||
if (c1 > c2) { |
|||
swap(array, i, i + 1) |
|||
newEnd = i |
|||
} |
|||
} |
|||
end = newEnd |
|||
for (i in end downTo begin + 1) { |
|||
val c1 = array[i - 1] |
|||
val c2 = array[i] |
|||
if (c1 > c2) { |
|||
swap(array, i, i - 1) |
|||
newBegin = i |
|||
} |
|||
} |
|||
begin = newBegin |
|||
} |
|||
} |
|||
fun main() { |
|||
val array: Array<Int> = intArrayOf(5, 1, -6, 12, 3, 13, 2, 4, 0, 15).toList().toTypedArray() |
|||
println("before: ${array.contentToString()}") |
|||
cocktailSort(array) |
|||
println("after: ${array.contentToString()}") |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>before: [5, 1, -6, 12, 3, 13, 2, 4, 0, 15] |
|||
after: [-6, 0, 1, 2, 3, 4, 5, 12, 13, 15]</pre> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">ClearAll[CocktailShakerSort] |
|||
CocktailShakerSort[in_List] := |
|||
Module[{x = in, swapped, begin = 1, end = Length[in] - 1}, |
|||
swapped = True; |
|||
While[swapped, |
|||
swapped = False; |
|||
Do[ |
|||
If[x[[i]] > x[[i + 1]], |
|||
x[[{i, i + 1}]] //= Reverse; |
|||
swapped = True; |
|||
] |
|||
, |
|||
{i, begin, end} |
|||
]; |
|||
end--; |
|||
Do[ |
|||
If[x[[i]] > x[[i + 1]], |
|||
x[[{i, i + 1}]] //= Reverse; |
|||
swapped = True; |
|||
] |
|||
, |
|||
{i, end, begin, -1} |
|||
]; |
|||
begin++; |
|||
]; |
|||
x |
|||
] |
|||
CocktailShakerSort[{44, 21, 5, 88, 52, 44, 36, 93, 66, 18, 88, 61, 45, 47, 47, 68, 19, 60}]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>{5, 18, 19, 21, 36, 44, 44, 45, 47, 47, 52, 60, 61, 66, 68, 88, 88, 93}</pre> |
|||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="nim">proc cocktailShakerSort[T](a: var openarray[T]) = |
|||
var beginIdx = 0 |
|||
var endIdx = a.len - 2 |
|||
while beginIdx <= endIdx: |
|||
var newBeginIdx = endIdx |
|||
var newEndIdx = beginIdx |
|||
for i in beginIdx..endIdx: |
|||
if a[i] > a[i + 1]: |
|||
swap a[i], a[i + 1] |
|||
newEndIdx = i |
|||
endIdx = newEndIdx - 1 |
|||
for i in countdown(endIdx, beginIdx): |
|||
if a[i] > a[i + 1]: |
|||
swap a[i], a[i + 1] |
|||
newBeginIdx = i |
|||
beginIdx = newBeginIdx + 1 |
|||
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782] |
|||
cocktailShakerSort a |
|||
echo a</syntaxhighlight> |
|||
{{out}} |
|||
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre> |
|||
=={{header|Perl}}== |
|||
<syntaxhighlight lang="perl">use strict; |
|||
use warnings; |
|||
use feature 'say'; |
|||
sub cocktail_sort { |
|||
my @a = @_; |
|||
my ($min, $max) = (0, $#a-1); |
|||
while (1) { |
|||
my $swapped_forward = 0; |
|||
for my $i ($min .. $max) { |
|||
if ($a[$i] gt $a[$i+1]) { |
|||
@a[$i, $i+1] = @a[$i+1, $i]; |
|||
$swapped_forward = 1 |
|||
} |
|||
} |
|||
last if not $swapped_forward; |
|||
$max -= 1; |
|||
my $swapped_backward = 0; |
|||
for my $i (reverse $min .. $max) { |
|||
if ($a[$i] gt $a[$i+1]) { |
|||
@a[$i, $i+1] = @a[$i+1, $i]; |
|||
$swapped_backward = 1; |
|||
} |
|||
} |
|||
last if not $swapped_backward; |
|||
$min += 1; |
|||
} |
|||
@a |
|||
} |
|||
say join ' ', cocktail_sort( <t h e q u i c k b r o w n f o x j u m p s o v e r t h e l a z y d o g> );</syntaxhighlight> |
|||
{{out}} |
|||
<pre>a b c d e e e f g h h i j k l m n o o o o p q r r s t t u u v w x y z</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Averages 7 or 8% better than [[Sorting_algorithms/Cocktail_sort#Phix]] which already shifted the bounds, however this shifts >1 (sometimes). |
Averages 7 or 8% better than [[Sorting_algorithms/Cocktail_sort#Phix]] which already shifted the bounds, however this shifts >1 (sometimes). |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>function cocktailShakerSort(sequence s) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
integer beginIdx = 1, |
|||
endIdx = length(s)-1 |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">cocktailShakerSort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
while beginIdx <= endIdx do |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
integer newBeginIdx = endIdx, |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">beginIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> |
|||
newEndIdx = beginIdx |
|||
<span style="color: #000000;">endIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> |
|||
for ii=beginIdx to endIdx do |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">beginIdx</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">endIdx</span> <span style="color: #008080;">do</span> |
|||
if s[ii]>s[ii+1] then |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">newBeginIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">endIdx</span><span style="color: #0000FF;">,</span> |
|||
{s[ii+1],s[ii]} = {s[ii], s[ii+1]} |
|||
<span style="color: #000000;">newEndIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">beginIdx</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">ii</span><span style="color: #0000FF;">=</span><span style="color: #000000;">beginIdx</span> <span style="color: #008080;">to</span> <span style="color: #000000;">endIdx</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">object</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">],</span> |
|||
<span style="color: #000000;">sn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">></span><span style="color: #000000;">sn</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sn</span> |
|||
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span> |
|||
<span style="color: #000000;">newEndIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ii</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000080;font-style:italic;">-- elements after `newEndIdx` are now in correct order</span> |
|||
<span style="color: #000000;">endIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newEndIdx</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">ii</span><span style="color: #0000FF;">=</span><span style="color: #000000;">endIdx</span> <span style="color: #008080;">to</span> <span style="color: #000000;">beginIdx</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">object</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">],</span> |
|||
<span style="color: #000000;">sn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">></span><span style="color: #000000;">sn</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sn</span> |
|||
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span> |
|||
<span style="color: #000000;">newBeginIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ii</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000080;font-style:italic;">-- elements before `newBeginIdx` are now in correct order.</span> |
|||
<span style="color: #000000;">beginIdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newBeginIdx</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">12</span><span style="color: #0000FF;">))</span> <span style="color: #0000FF;">?{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cocktailShakerSort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)}</span> |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"one"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"two"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"three"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"four"</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">?{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cocktailShakerSort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)}</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
{{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"}} |
|||
</pre> |
|||
=={{header|Python}}== |
|||
<syntaxhighlight lang="python"> |
|||
""" |
|||
Python example of |
|||
http://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort_with_shifting_bounds |
|||
based on |
|||
http://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort#Python |
|||
""" |
|||
def cocktailshiftingbounds(A): |
|||
beginIdx = 0 |
|||
endIdx = len(A) - 1 |
|||
while beginIdx <= endIdx: |
|||
newBeginIdx = endIdx |
|||
newEndIdx = beginIdx |
|||
for ii in range(beginIdx,endIdx): |
|||
if A[ii] > A[ii + 1]: |
|||
A[ii+1], A[ii] = A[ii], A[ii+1] |
|||
newEndIdx = ii |
newEndIdx = ii |
||
endIdx = newEndIdx |
|||
-- elements after `newEndIdx` are now in correct order |
|||
for ii in range(endIdx,beginIdx-1,-1): |
|||
if A[ii] > A[ii + 1]: |
|||
A[ii+1], A[ii] = A[ii], A[ii+1] |
|||
{s[ii+1],s[ii]} = {s[ii],s[ii+1]} |
|||
newBeginIdx = ii |
newBeginIdx = ii |
||
end for |
|||
-- elements before `newBeginIdx` are now in correct order. |
|||
beginIdx = newBeginIdx + 1 |
beginIdx = newBeginIdx + 1 |
||
test1 = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0] |
|||
return s |
|||
cocktailshiftingbounds(test1) |
|||
end function |
|||
print(test1) |
|||
sequence s = shuffle(tagset(12)) ?{s,cocktailShakerSort(s)} |
|||
s = {"one","two","three","four"} ?{s,cocktailShakerSort(s)}</lang> |
|||
test2=list('big fjords vex quick waltz nymph') |
|||
cocktailshiftingbounds(test2) |
|||
print(''.join(test2)) |
|||
</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] |
|||
abcdefghiijklmnopqrstuvwxyz |
|||
{{"one","two","three","four"},{"four","one","three","two"}} |
|||
</pre> |
</pre> |
||
=={{header|Quackery}}== |
|||
<syntaxhighlight lang="Quackery"> |
|||
[ stack ] is limit ( --> s ) |
|||
[ stack ] is offset ( --> s ) |
|||
[ offset share + |
|||
2dup 1+ peek dip peek > ] is compare ( [ n --> b ) |
|||
[ offset share + |
|||
dup 1+ unrot |
|||
2dup peek |
|||
dip |
|||
[ 2dup 1+ peek |
|||
unrot poke |
|||
swap ] |
|||
unrot poke ] is exchange ( [ n --> [ ) |
|||
[ dup size 1 - limit put |
|||
0 offset put |
|||
[ 0 swap |
|||
limit share times |
|||
[ dup i^ compare if |
|||
[ i^ exchange |
|||
dip 1+ ] ] |
|||
over while |
|||
limit share times |
|||
[ dup i compare if |
|||
[ i exchange |
|||
dip 1+ ] ] |
|||
over while |
|||
-2 limit tally |
|||
1 offset tally |
|||
nip again ] |
|||
nip |
|||
limit release |
|||
offset release ] is cocktail ( [ --> [ ) |
|||
randomise |
|||
[] 20 times [ 89 random 10 + join ] |
|||
dup echo cr |
|||
cocktail echo</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[ 88 46 64 82 35 34 92 15 48 78 94 19 50 79 62 19 42 79 43 50 ] |
|||
[ 15 19 19 34 35 42 43 46 48 50 50 62 64 78 79 79 82 88 92 94 ]</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
{{works with|Rakudo|2020.05}} |
{{works with|Rakudo|2020.05}} |
||
<lang |
<syntaxhighlight lang="raku" line>sub cocktail_sort ( @a ) { |
||
my ($min, $max) = 0, +@a - 2; |
my ($min, $max) = 0, +@a - 2; |
||
loop { |
loop { |
||
Line 307: | Line 1,842: | ||
my @weights = (flat 0..9, 'A'..'F').roll(2 + ^4 .roll).join xx 100; |
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';</ |
say @weights.sort.Str eq @weights.&cocktail_sort.Str ?? 'ok' !! 'not ok';</syntaxhighlight> |
||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
This REXX version can handle array elements that may contain blanks or spaces |
This REXX version can handle array elements that may contain blanks or spaces. |
||
<syntaxhighlight lang="rexx">/*REXX program sorts an array using the cocktail─sort method with shifting bounds. */ |
|||
<br>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 gen /*generate some array elements. */ |
||
call show 'before sort' /*show unsorted array elements. */ |
call show 'before sort' /*show unsorted array elements. */ |
||
Line 367: | Line 1,901: | ||
say 'element' right(j, w) arg(1)":" @.j |
say 'element' right(j, w) arg(1)":" @.j |
||
end /*j*/ /* ↑ */ |
end /*j*/ /* ↑ */ |
||
return /* └─────max width of any line.*/</ |
return /* └─────max width of any line.*/</syntaxhighlight> |
||
{{out|output|text= when using the internal default inputs:}} |
{{out|output|text= when using the internal default inputs:}} |
||
Line 410: | Line 1,944: | ||
element 17 after sort: the lovers ◄─── VI |
element 17 after sort: the lovers ◄─── VI |
||
element 18 after sort: the stars ◄─── XVII |
element 18 after sort: the stars ◄─── XVII |
||
</pre> |
|||
=={{header|Rust}}== |
|||
<syntaxhighlight lang="rust">fn cocktail_shaker_sort<T: PartialOrd>(a: &mut [T]) { |
|||
let mut begin = 0; |
|||
let mut end = a.len(); |
|||
if end == 0 { |
|||
return; |
|||
} |
|||
end -= 1; |
|||
while begin < end { |
|||
let mut new_begin = end; |
|||
let mut new_end = begin; |
|||
for i in begin..end { |
|||
if a[i + 1] < a[i] { |
|||
a.swap(i, i + 1); |
|||
new_end = i; |
|||
} |
|||
} |
|||
end = new_end; |
|||
let mut i = end; |
|||
while i > begin { |
|||
if a[i] < a[i - 1] { |
|||
a.swap(i, i - 1); |
|||
new_begin = i; |
|||
} |
|||
i -= 1; |
|||
} |
|||
begin = new_begin; |
|||
} |
|||
} |
|||
fn main() { |
|||
let mut v = vec![5, 1, -6, 12, 3, 13, 2, 4, 0, 15]; |
|||
println!("before: {:?}", v); |
|||
cocktail_shaker_sort(&mut v); |
|||
println!("after: {:?}", v); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
before: [5, 1, -6, 12, 3, 13, 2, 4, 0, 15] |
|||
after: [-6, 0, 1, 2, 3, 4, 5, 12, 13, 15] |
|||
</pre> |
|||
=={{header|Swift}}== |
|||
{{trans|Rust}} |
|||
<syntaxhighlight lang="swift">func cocktailShakerSort<T: Comparable>(_ a: inout [T]) { |
|||
var begin = 0 |
|||
var end = a.count |
|||
if end == 0 { |
|||
return |
|||
} |
|||
end -= 1 |
|||
while begin < end { |
|||
var new_begin = end |
|||
var new_end = begin |
|||
var i = begin |
|||
while i < end { |
|||
if a[i + 1] < a[i] { |
|||
a.swapAt(i, i + 1) |
|||
new_end = i |
|||
} |
|||
i += 1 |
|||
} |
|||
end = new_end |
|||
i = end |
|||
while i > begin { |
|||
if a[i] < a[i - 1] { |
|||
a.swapAt(i, i - 1) |
|||
new_begin = i |
|||
} |
|||
i -= 1 |
|||
} |
|||
begin = new_begin |
|||
} |
|||
} |
|||
var array = [5, 1, -6, 12, 3, 13, 2, 4, 0, 15] |
|||
print("before: \(array)") |
|||
cocktailShakerSort(&array) |
|||
print(" after: \(array)") |
|||
var array2 = ["one", "two", "three", "four", "five", "six", "seven", "eight"] |
|||
print("before: \(array2)") |
|||
cocktailShakerSort(&array2) |
|||
print(" after: \(array2)")</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
before: [5, 1, -6, 12, 3, 13, 2, 4, 0, 15] |
|||
after: [-6, 0, 1, 2, 3, 4, 5, 12, 13, 15] |
|||
before: ["one", "two", "three", "four", "five", "six", "seven", "eight"] |
|||
after: ["eight", "five", "four", "one", "seven", "six", "three", "two"] |
|||
</pre> |
</pre> |
||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
< |
<syntaxhighlight lang="vb">' Sorting algorithms/Cocktail sort with shifting bounds - VBA |
||
Function cocktailShakerSort(ByVal A As Variant) As Variant |
Function cocktailShakerSort(ByVal A As Variant) As Variant |
||
Line 446: | Line 2,074: | ||
Debug.Print Join(B, ", ") |
Debug.Print Join(B, ", ") |
||
Debug.Print Join(cocktailShakerSort(B), ", ") |
Debug.Print Join(cocktailShakerSort(B), ", ") |
||
End Sub</ |
End Sub</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 455: | Line 2,083: | ||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
< |
<syntaxhighlight lang="vb">' Sorting algorithms/Cocktail sort with shifting bounds - VBScript |
||
Function cocktailShakerSort(ByVal A) |
Function cocktailShakerSort(ByVal A) |
||
Line 486: | Line 2,114: | ||
Next |
Next |
||
Wscript.Echo Join(cocktailShakerSort(B)," ") |
Wscript.Echo Join(cocktailShakerSort(B)," ") |
||
</ |
</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 494: | Line 2,122: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{works with|Visual Basic .NET|9.0}} |
{{works with|Visual Basic .NET|9.0}} |
||
< |
<syntaxhighlight lang="vbnet">' Sorting algorithms/Cocktail sort with shifting bounds - VB.Net |
||
Private Sub Cocktail_Shaker_Sort() |
Private Sub Cocktail_Shaker_Sort() |
||
Dim A(20), tmp As Long 'or Integer Long Single Double String |
Dim A(20), tmp As Long 'or Integer Long Single Double String |
||
Line 525: | Line 2,153: | ||
'Display the sorted list |
'Display the sorted list |
||
Debug.Print(String.Join(", ", A)) |
Debug.Print(String.Join(", ", A)) |
||
End Sub 'Cocktail_Shaker_Sort </ |
End Sub 'Cocktail_Shaker_Sort </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
1, 4, 5, 28, 30, 36, 37, 41, 52, 53, 57, 70, 70, 76, 77, 79, 81, 86, 87, 94, 96 |
1, 4, 5, 28, 30, 36, 37, 41, 52, 53, 57, 70, 70, 76, 77, 79, 81, 86, 87, 94, 96 |
||
</pre> |
</pre> |
||
=={{header|Wren}}== |
|||
{{trans|Go}} |
|||
{{libheader|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. |
|||
<syntaxhighlight lang="wren">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))") |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
Sample run: |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
Translation of the pseudo code from Wikipedia. |
|||
<syntaxhighlight lang "XPL0">procedure CocktailShakerSort(A, Length); |
|||
integer A, Length; |
|||
integer BeginIdx, EndIdx; \mark the first and last index to check |
|||
integer NewBeginIdx, NewEndIdx, II, T; |
|||
begin |
|||
BeginIdx:= 0; |
|||
EndIdx:= Length - 1; |
|||
while BeginIdx <= EndIdx do |
|||
begin |
|||
NewBeginIdx:= EndIdx; |
|||
NewEndIdx:= BeginIdx; |
|||
for II:= BeginIdx to EndIdx - 1 do |
|||
begin |
|||
if A(II) > A(II + 1) then |
|||
begin |
|||
T:= A(II+1); A(II+1):= A(II); A(II):= T; |
|||
NewEndIdx:= II; |
|||
end; |
|||
end; |
|||
\Decreases EndIdx because the elements after NewEndIdx are in correct order |
|||
EndIdx:= NewEndIdx; |
|||
for II:= EndIdx downto BeginIdx - 1 do |
|||
begin |
|||
if A(II) > A(II + 1) then |
|||
begin |
|||
T:= A(II+1); A(II+1):= A(II); A(II):= T; |
|||
NewBeginIdx:= II; |
|||
end; |
|||
end; |
|||
\Increases BeginIdx because elements before NewBeginIdx are in correct order |
|||
BeginIdx:= NewBeginIdx + 1; |
|||
end; |
|||
end; |
|||
int Test, Len, I; |
|||
begin |
|||
Test:= [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]; |
|||
Len:= 10; |
|||
CocktailShakerSort(Test, Len); |
|||
for I:= 0 to Len-1 do |
|||
begin |
|||
IntOut(0, Test(I)); |
|||
ChOut(0, ^ ); |
|||
end; |
|||
end</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
0 1 2 3 4 5 6 7 8 9 </pre> |
Latest revision as of 11:33, 8 February 2024
You are encouraged to solve this task according to the task description, using any language you may know.
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" (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
11l
F cocktailshiftingbounds(&A)
V beginIdx = 0
V endIdx = A.len - 1
L beginIdx <= endIdx
V newBeginIdx = endIdx
V newEndIdx = beginIdx
L(ii) beginIdx .< endIdx
I A[ii] > A[ii + 1]
swap(&A[ii + 1], &A[ii])
newEndIdx = ii
endIdx = newEndIdx
L(ii) (endIdx .< beginIdx - 1).step(-1)
I A[ii] > A[ii + 1]
swap(&A[ii + 1], &A[ii])
newBeginIdx = ii
beginIdx = newBeginIdx + 1
V test1 = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
cocktailshiftingbounds(&test1)
print(test1)
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
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.
* 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
AArch64 Assembly
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program cocktailSortbound64.s */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessSortOk: .asciz "Table sorted.\n"
szMessSortNok: .asciz "Table not sorted !!!!!.\n"
sMessResult: .asciz "Value : @ \n"
szCarriageReturn: .asciz "\n"
.align 4
//TableNumber: .quad 1,3,6,2,5,9,10,8,4,7
TableNumber: .quad 10,9,8,7,6,-5,4,3,2,1
.equ NBELEMENTS, (. - TableNumber) / 8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
ldr x0,qAdrTableNumber // address number table
mov x1,0
mov x2,NBELEMENTS // number of élements
bl cocktailSortBound
ldr x0,qAdrTableNumber // address number table
bl displayTable
ldr x0,qAdrTableNumber // address number table
mov x1,NBELEMENTS // number of élements
bl isSorted // control sort
cmp x0,1 // sorted ?
beq 1f
ldr x0,qAdrszMessSortNok // no !! error sort
bl affichageMess
b 100f
1: // yes
ldr x0,qAdrszMessSortOk
bl affichageMess
100: // standard end of the program
mov x0,0 // return code
mov x8,EXIT // request to exit program
svc 0 // perform the system call
qAdrsZoneConv: .quad sZoneConv
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsMessResult: .quad sMessResult
qAdrTableNumber: .quad TableNumber
qAdrszMessSortOk: .quad szMessSortOk
qAdrszMessSortNok: .quad szMessSortNok
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the number of elements > 0 */
/* x0 return 0 if not sorted 1 if sorted */
isSorted:
stp x2,lr,[sp,-16]! // save registers
stp x3,x4,[sp,-16]! // save registers
mov x2,0
ldr x4,[x0,x2,lsl 3]
1:
add x2,x2,1
cmp x2,x1
bge 99f
ldr x3,[x0,x2, lsl 3]
cmp x3,x4
blt 98f
mov x4,x3
b 1b
98:
mov x0,0 // not sorted
b 100f
99:
mov x0,1 // sorted
100:
ldp x3,x4,[sp],16 // restaur 2 registers
ldp x2,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* cocktail sort Bound */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the first element */
/* x2 contains the number of element */
cocktailSortBound:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
stp x8,x9,[sp,-16]! // save registers
sub x2,x2,2 // compute endidx = n - 2
// and r1 = beginidx
1: // start loop 1
cmp x1,x2
bgt 100f
mov x8,x1 // newbeginidx
mov x7,x2 // newendidx
mov x3,x1 // start index
2: // start loop 2
add x4,x3,1
ldr x5,[x0,x3,lsl 3] // load value A[j]
ldr x6,[x0,x4,lsl 3] // load value A[j+1]
cmp x6,x5 // compare value
bge 3f
str x6,[x0,x3,lsl 3] // if smaller inversion
str x5,[x0,x4,lsl 3]
mov x7,x3 // and mov indice to newendidx
3:
add x3,x3,1 // increment index j
cmp x3,x2 // end ?
ble 2b // no -> loop 2
sub x2,x7,1 // endidx = newendidx - 1
bl displayTable
mov x3,x2 // indice
4:
add x4,x3,1
ldr x5,[x0,x3,lsl 3] // load value A[j]
ldr x6,[x0,x4,lsl 3] // load value A[j+1]
cmp x6,x5 // compare value
bge 5f
str x6,[x0,x3,lsl 3] // if smaller inversion
str x5,[x0,x4,lsl 3]
mov x8,x3 // newbeginidx = indice
5:
sub x3,x3,1 // decrement index j
cmp x3,x1 // end ?
bge 4b // no -> loop 2
add x1,x8,1 // beginidx = newbeginidx
b 1b // loop 1
100:
ldp x8,x9,[sp],16 // restaur 2 registers
ldp x6,x7,[sp],16 // restaur 2 registers
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* x0 contains the address of table */
displayTable:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
mov x2,x0 // table address
mov x3,0
1: // loop display table
ldr x0,[x2,x3,lsl 3]
ldr x1,qAdrsZoneConv
bl conversion10S // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
add x3,x3,1
cmp x3,NBELEMENTS - 1
ble 1b
ldr x0,qAdrszCarriageReturn
bl affichageMess
mov x0,x2 // table address
100:
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
Action!
PROC PrintArray(INT ARRAY a INT size)
INT i
Put('[)
FOR i=0 TO size-1
DO
IF i>0 THEN Put(' ) FI
PrintI(a(i))
OD
Put(']) PutE()
RETURN
PROC CoctailShakerSort(INT ARRAY a INT size)
INT begIdx,endIdx,newBegIdx,newEndIdx,i,tmp
begIdx=0 endIdx=size-2
WHILE begIdx<=endIdx
DO
newBegIdx=endIdx
newEndIdx=begIdx
i=begIdx
WHILE i<=endIdx
DO
IF a(i)>a(i+1) THEN
tmp=a(i) a(i)=a(i+1) a(i+1)=tmp
newEndIdx=i
FI
i==+1
OD
endIdx=newEndIdx-1
i=endIdx
WHILE i>=begIdx
DO
IF a(i)>a(i+1) THEN
tmp=a(i) a(i)=a(i+1) a(i+1)=tmp
newBegIdx=i
FI
i==-1
OD
begIdx=newBegIdx+1
OD
RETURN
PROC Test(INT ARRAY a INT size)
PrintE("Array before sort:")
PrintArray(a,size)
CoctailShakerSort(a,size)
PrintE("Array after sort:")
PrintArray(a,size)
PutE()
RETURN
PROC Main()
INT ARRAY
a(10)=[1 4 65535 0 3 7 4 8 20 65530],
b(21)=[10 9 8 7 6 5 4 3 2 1 0
65535 65534 65533 65532 65531
65530 65529 65528 65527 65526],
c(8)=[101 102 103 104 105 106 107 108],
d(12)=[1 65535 1 65535 1 65535 1
65535 1 65535 1 65535]
Test(a,10)
Test(b,21)
Test(c,8)
Test(d,12)
RETURN
- Output:
Screenshot from Atari 8-bit computer
Array before sort: [1 4 -1 0 3 7 4 8 20 -6] Array after sort: [-6 -1 0 1 3 4 4 7 8 20] Array before sort: [10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10] Array after sort: [-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10] Array before sort: [101 102 103 104 105 106 107 108] Array after sort: [101 102 103 104 105 106 107 108] Array before sort: [1 -1 1 -1 1 -1 1 -1 1 -1 1 -1] Array after sort: [-1 -1 -1 -1 -1 -1 1 1 1 1 1 1]
ALGOL 60
begin
comment Sorting algorithms/Cocktail sort with shifting bounds - Algol 60;
integer nA;
nA:=20;
begin
integer array A[1: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
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
ALGOL 68
Based on the pseudo-code with test cases from the Action! sample.
BEGIN # cocktail sort with shifting bounds #
# sorts data, using a cocktail sort with shifting bounds #
# a reference to the sorted data is returned #
# - defined as an operator as Algol 68 has operator overloading but not #
# procedure overloading #
# (similar operators with the same name could be defined for other types #
# of array) #
OP COCKTAILSORTSB = ( []INT data )REF[]INT:
BEGIN
# make a copy of the data #
REF[]INT a := HEAP[ LWB data : UPB data ]INT := data;
# `beginIdx` and `endIdx` marks the first and last index to check. #
INT begin idx := LWB a;
INT end idx := UPB a - 1;
WHILE begin idx <= end idx DO
INT new begin idx := end idx;
INT new end idx := begin idx;
FOR ii FROM begin idx TO end idx DO
IF a[ ii ] > a[ ii + 1 ] THEN
INT aii = a[ ii ];
a[ ii ] := a[ ii + 1 ];
a[ ii + 1 ] := aii;
new end idx := ii
FI
OD;
# decreases `endIdx` because the elements after `newEndIdx` are in correct order #
end idx := new end idx - 1;
FOR ii FROM end idx BY -1 TO begin idx DO
IF a[ ii ] > a[ ii + 1 ] THEN
INT aii = a[ ii ];
a[ ii ] := a[ ii + 1 ];
a[ ii + 1 ] := aii;
new begin idx := ii
FI
OD;
# increases `beginIdx` because the elements before `newBeginIdx` are in correct order. #
begin idx := new begin idx + 1
OD;
a
END # COCKTAILSORTSB # ;
# test the COCKTAILSORTSB operator #
PROC test cocktail sort with shifting bounds = ( []INT data )VOID:
BEGIN
REF[]INT sorted := COCKTAILSORTSB data;
print( ( "[" ) );
FOR i FROM LWB data TO UPB data DO print( ( " ", whole( data[ i ], 0 ) ) ) OD;
print( ( " ]", newline, " -> [" ) );
FOR i FROM LWB sorted TO UPB sorted DO print( ( " ", whole( sorted[ i ], 0 ) ) ) OD;
print( ( " ]", newline ) )
END # test cocktail sort with shifting bounds # ;
# test cases from the Action! sample #
test cocktail sort with shifting bounds( ( 1, 4, -1, 0, 3, 7, 4, 8, 20, -6 ) );
test cocktail sort with shifting bounds( ( 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10
)
);
test cocktail sort with shifting bounds( ( 101, 102, 103, 104, 105, 106, 107, 108 ) );
test cocktail sort with shifting bounds( ( 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1 ) );
# additional test cases #
test cocktail sort with shifting bounds( ( 1, 1, 1, 1, 1, 1 ) );
test cocktail sort with shifting bounds( ( 0 ) );
test cocktail sort with shifting bounds( () )
END
- Output:
[ 1 4 -1 0 3 7 4 8 20 -6 ] -> [ -6 -1 0 1 3 4 4 7 8 20 ] [ 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ] -> [ -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 ] [ 101 102 103 104 105 106 107 108 ] -> [ 101 102 103 104 105 106 107 108 ] [ 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ] -> [ -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 ] [ 1 1 1 1 1 1 ] -> [ 1 1 1 1 1 1 ] [ 0 ] -> [ 0 ] [ ] -> [ ]
ALGOL W
Based on the pseudo-code - test code based on the Algol 68 test code.
begin % cocktail sort with shifting bounds %
% sorts in-place a using a cocktail sort with shifting bounds %
% the bounds of a must be specified in lb and ub %
procedure cocktailSortWithShiftingBounds ( integer array a ( * )
; integer value lb, ub
);
begin
% `beginIdx` and `endIdx` marks the first and last index to check. %
integer beginIdx, endIdx;
beginIdx := lb;
endIdx := ub - 1;
while beginIdx <= endIdx do begin
integer newBeginIdx, newEndIdx;
newBeginIdx := endIdx;
newEndIdx := beginIdx;
for ii := beginIdx until endIdx do begin
integer aii;
if a( ii ) > a( ii + 1 ) then begin
integer aii;
aii := a( ii );
a( ii ) := a( ii + 1 );
a( ii + 1 ) := aii;
newEndIdx := ii
end
end for_ii ;
% decreases `endIdx` because the elements after `newEndIdx` are in correct order %
endIdx := newEndIdx - 1;
for ii := endIdx step -1 until beginIdx do begin
if a( ii ) > a( ii + 1 ) then begin
integer aii;
aii := a( ii );
a( ii ) := a( ii + 1 );
a( ii + 1 ) := aii;
newBeginIdx := ii
end
end for_ii ;
% increases `beginIdx` because the elements before `newBeginIdx` are in correct order. %
beginIdx := newBeginIdx + 1
end while_beginIdx_le_endIdx
end coctailSortWithShiftingBounds ;
% test the cocktailSortWithShiftingBounds procedure %
begin
integer procedure inc ( integer value result i ) ;
begin
i := i + 1;
i
end inc ;
procedure testCocktailSortWithShiftingBounds( integer array data ( * )
; integer value lb, ub
);
begin
i_w := 1; s_w := 0; % set formatting %
write( "[" );
for i := lb until ub do writeon( " ", data( i ) );
writeon( " ]" );
cocktailSortWithShiftingBounds( data, lb, ub );
write( " -> [" );
for i := lb until ub do writeon( " ", data( i ) );
writeon( " ]" )
end testCocktailSortWithShiftingBounds ;
integer array t ( 1 :: 32 );
integer tPos;
% test cases from the Action! sample %
tPos := 0;
for d := 1, 4, -1, 0, 3, 7, 4, 8, 20, -6 do t( inc( tPos ) ) := d;
testCocktailSortWithShiftingBounds( t, 1, tPos );
tPos := 0;
for d := 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10
do t( inc( tPos ) ) := d;
testCocktailSortWithShiftingBounds( t, 1, tPos );
tPos := 0;
for d := 101, 102, 103, 104, 105, 106, 107, 108 do t( inc( tPos ) ) := d;
testCocktailSortWithShiftingBounds( t, 1, tPos );
tPos := 0;
for d := 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1 do t( inc( tPos ) ) := d;
testCocktailSortWithShiftingBounds( t, 1, tPos );
% additional test cases %
tPos := 0;
for d := 1, 1, 1, 1, 1, 1 do t( inc( tPos ) ) := d;
testCocktailSortWithShiftingBounds( t, 1, tPos );
tPos := 0;
for d := 0 do t( inc( tPos ) ) := d;
testCocktailSortWithShiftingBounds( t, 1, tPos );
tPos := 0;
testCocktailSortWithShiftingBounds( t, 1, tPos );
end
end.
- Output:
[ 1 4 -1 0 3 7 4 8 20 -6 ] -> [ -6 -1 0 1 3 4 4 7 8 20 ] [ 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ] -> [ -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 ] [ 101 102 103 104 105 106 107 108 ] -> [ 101 102 103 104 105 106 107 108 ] [ 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ] -> [ -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 ] [ 1 1 1 1 1 1 ] -> [ 1 1 1 1 1 1 ] [ 0 ] -> [ 0 ] [ ] -> [ ]
ARM Assembly
/* ARM assembly Raspberry PI */
/* program cocktailSortBound.s */
/* REMARK 1 : this program use routines in a include file
see task Include a file language arm assembly
for the routine affichageMess conversion10
see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes */
/************************************/
.include "../constantes.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessSortOk: .asciz "Table sorted.\n"
szMessSortNok: .asciz "Table not sorted !!!!!.\n"
sMessResult: .asciz "Value : @ \n"
szCarriageReturn: .asciz "\n"
.align 4
TableNumber: .int 1,3,6,2,5,9,10,8,4,7
#TableNumber: .int 10,9,8,7,6,-5,4,3,2,1
.equ NBELEMENTS, (. - TableNumber) / 4
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
1:
ldr r0,iAdrTableNumber @ address number table
mov r1,#0
mov r2,#NBELEMENTS @ number of élements
bl cocktailSortBound
ldr r0,iAdrTableNumber @ address number table
bl displayTable
ldr r0,iAdrTableNumber @ address number table
mov r1,#NBELEMENTS @ number of élements
bl isSorted @ control sort
cmp r0,#1 @ sorted ?
beq 2f
ldr r0,iAdrszMessSortNok @ no !! error sort
bl affichageMess
b 100f
2: @ yes
ldr r0,iAdrszMessSortOk
bl affichageMess
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsMessResult: .int sMessResult
iAdrTableNumber: .int TableNumber
iAdrszMessSortOk: .int szMessSortOk
iAdrszMessSortNok: .int szMessSortNok
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of elements > 0 */
/* r0 return 0 if not sorted 1 if sorted */
isSorted:
push {r2-r4,lr} @ save registers
mov r2,#0
ldr r4,[r0,r2,lsl #2]
1:
add r2,#1
cmp r2,r1
movge r0,#1
bge 100f
ldr r3,[r0,r2, lsl #2]
cmp r3,r4
movlt r0,#0
blt 100f
mov r4,r3
b 1b
100:
pop {r2-r4,lr}
bx lr @ return
/******************************************************************/
/* cocktail Sort */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the first element */
/* r2 contains the number of element */
cocktailSortBound:
push {r1-r9,lr} @ save registers
sub r2,r2,#2 @ compute endidx = n - 2
@ and r1= beginidx
1: @ start loop 1
cmp r1,r2 @ compare endidx beginidx
bgt 100f
mov r8,r1 @ newbeginidx
mov r7,r2 @ newendidx
mov r3,r1 @ indice
2: @ start loop 2
add r4,r3,#1
ldr r5,[r0,r3,lsl #2] @ load value A[j]
ldr r6,[r0,r4,lsl #2] @ load value A[j+1]
cmp r6,r5 @ compare value
strlt r6,[r0,r3,lsl #2] @ if smaller inversion
strlt r5,[r0,r4,lsl #2]
movlt r7,r3 @ and mov indice to newendidx
add r3,#1 @ increment indice
cmp r3,r2 @ end ?
ble 2b @ no -> loop 2
sub r2,r7,#1 @ endidx = newendidx
//bl displayTable
mov r3,r2 @ indice
3:
add r4,r3,#1
ldr r5,[r0,r3,lsl #2] @ load value A[j]
ldr r6,[r0,r4,lsl #2] @ load value A[j+1]
cmp r6,r5 @ compare value
strlt r6,[r0,r3,lsl #2] @ if smaller inversion
strlt r5,[r0,r4,lsl #2]
movlt r8,r3 @ newbeginidx = indice
sub r3,#1 @ decrement indice
cmp r3,r1 @ end ?
bge 3b @ no -> loop 3
//bl displayTable
add r1,r8,#1 @ beginidx = newbeginidx + 1
b 1b @ loop 1
100:
pop {r1-r9,lr}
bx lr @ return
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* r0 contains the address of table */
displayTable:
push {r0-r3,lr} @ save registers
mov r2,r0 @ table address
mov r3,#0
1: @ loop display table
ldr r0,[r2,r3,lsl #2]
ldr r1,iAdrsZoneConv @
bl conversion10S @ décimal conversion
ldr r0,iAdrsMessResult
ldr r1,iAdrsZoneConv @ insert conversion
bl strInsertAtCharInc
bl affichageMess @ display message
add r3,#1
cmp r3,#NBELEMENTS - 1
ble 1b
ldr r0,iAdrszCarriageReturn
bl affichageMess
100:
pop {r0-r3,lr}
bx lr
iAdrsZoneConv: .int sZoneConv
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
Arturo
cocktailShiftSort: function [items][
a: new items
beginIdx: 0
endIdx: (size a)-2
while [beginIdx =< endIdx][
newBeginIdx: endIdx
newEndIdx: beginIdx
loop beginIdx..endIdx 'i [
if a\[i] > a\[i+1] [
tmp: a\[i]
a\[i]: a\[i+1]
a\[i+1]: tmp
newEndIdx: i
]
]
endIdx: newEndIdx - 1
loop endIdx..beginIdx 'i [
if a\[i] > a\[i+1] [
tmp: a\[i]
a\[i]: a\[i+1]
a\[i+1]: tmp
newBeginIdx: i
]
]
beginIdx: newBeginIdx - 1
]
return a
]
print cocktailShiftSort [3 1 2 8 5 7 9 4 6]
- Output:
1 2 3 4 5 6 7 8 9
AutoHotkey
cocktailShakerSort(A){
beginIdx := 1
endIdx := A.Count() - 1
while (beginIdx <= endIdx) {
newBeginIdx := endIdx
newEndIdx := beginIdx
ii := beginIdx
while (ii <= endIdx) {
if (A[ii] > A[ii + 1]) {
tempVal := A[ii], A[ii] := A[ii+1], A[ii+1] := tempVal
newEndIdx := ii
}
ii++
}
endIdx := newEndIdx - 1
ii := endIdx
while (ii >= beginIdx) {
if (A[ii] > A[ii + 1]) {
tempVal := A[ii], A[ii] := A[ii+1], A[ii+1] := tempVal
newBeginIdx := ii
}
ii--
}
beginIdx := newBeginIdx + 1
}
}
Examples:
A := [8,6,4,3,5,2,7,1]
cocktailShakerSort(A)
for k, v in A
output .= v ", "
MsgBox % "[" Trim(output, ", ") "]" ; show output
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
C
#include <stdio.h>
#include <string.h>
void swap(char* p1, char* p2, size_t size) {
for (; size-- > 0; ++p1, ++p2) {
char tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
}
void cocktail_shaker_sort(void* base, size_t count, size_t size,
int (*cmp)(const void*, const void*)) {
char* begin = base;
char* end = base + size * count;
if (end == begin)
return;
for (end -= size; begin < end; ) {
char* new_begin = end;
char* new_end = begin;
for (char* p = begin; p < end; p += size) {
char* q = p + size;
if (cmp(p, q) > 0) {
swap(p, q, size);
new_end = p;
}
}
end = new_end;
for (char* p = end; p > begin; p -= size) {
char* q = p - size;
if (cmp(q, p) > 0) {
swap(p, q, size);
new_begin = p;
}
}
begin = new_begin;
}
}
int string_compare(const void* p1, const void* p2) {
const char* const* s1 = p1;
const char* const* s2 = p2;
return strcmp(*s1, *s2);
}
void print(const char** a, size_t len) {
for (size_t i = 0; i < len; ++i)
printf("%s ", a[i]);
printf("\n");
}
int main() {
const char* a[] = { "one", "two", "three", "four", "five",
"six", "seven", "eight" };
const size_t len = sizeof(a)/sizeof(a[0]);
printf("before: ");
print(a, len);
cocktail_shaker_sort(a, len, sizeof(char*), string_compare);
printf("after: ");
print(a, len);
return 0;
}
- Output:
before: one two three four five six seven eight after: eight five four one seven six three two
C++
#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <vector>
// This only works for random access iterators
template <typename iterator>
void cocktail_shaker_sort(iterator begin, iterator end) {
if (begin == end)
return;
for (--end; begin < end; ) {
iterator new_begin = end;
iterator new_end = begin;
for (iterator i = begin; i < end; ++i) {
iterator j = i + 1;
if (*j < *i) {
std::iter_swap(i, j);
new_end = i;
}
}
end = new_end;
for (iterator i = end; i > begin; --i) {
iterator j = i - 1;
if (*i < *j) {
std::iter_swap(i, j);
new_begin = i;
}
}
begin = new_begin;
}
}
template <typename iterator>
void print(iterator begin, iterator end) {
if (begin == end)
return;
std::cout << *begin++;
while (begin != end)
std::cout << ' ' << *begin++;
std::cout << '\n';
}
int main() {
std::vector<int> v{5, 1, -6, 12, 3, 13, 2, 4, 0, 15};
std::cout << "before: ";
print(v.begin(), v.end());
cocktail_shaker_sort(v.begin(), v.end());
assert(std::is_sorted(v.begin(), v.end()));
std::cout << "after: ";
print(v.begin(), v.end());
return 0;
}
- Output:
before: 5 1 -6 12 3 13 2 4 0 15 after: -6 0 1 2 3 4 5 12 13 15
FreeBASIC
Sub cocktailShakerSort(bs() As Long)
Dim As Long i, lb = Lbound(bs), ub = Ubound(bs) -1
Dim As Long newlb, newub, tmp
Do While lb <= ub
newlb = ub
newub = lb
For i = lb To ub
If bs(i) > bs(i + 1) Then
tmp = bs(i): bs(i) = bs(i + 1): bs(i + 1) = tmp
newub = i
End If
Next i
ub = newub - 1
For i = ub To lb Step -1
If bs(i) > bs(i + 1) Then
tmp = bs(i): bs(i) = bs(i + 1): bs(i + 1) = tmp
newlb = i
End If
Next i
lb = newlb + 1
Loop
End Sub
'--- Programa Principal ---
Dim As Long i, array(-7 To 7)
Dim As Long a = Lbound(array), b = Ubound(array)
Randomize Timer
For i = a To b : array(i) = i : Next i
For i = a To b
Swap array(i), array(Int(Rnd * (b - a + 1)) + a)
Next i
Print "unsort ";
For i = a To b : Print Using "####"; array(i); : Next i
cocktailShakerSort(array()) ' ordenar el array
Print !"\n sort ";
For i = a To b : Print Using "####"; array(i); : Next i
Print !"\n--- terminado, pulsa RETURN---"
Sleep
- Output:
unsort -4 0 5 -7 -2 4 3 -5 -1 7 2 1 6 -3 -6 sort -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7
Go
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
Groovy
class CocktailSort {
static void main(String[] args) {
Integer[] array = [ 5, 1, -6, 12, 3, 13, 2, 4, 0, 15 ]
println("before: " + Arrays.toString(array))
cocktailSort(array)
println("after: " + Arrays.toString(array))
}
// Sorts an array of elements that implement the Comparable interface
static void cocktailSort(Object[] array) {
int begin = 0
int end = array.length
if (end == 0) {
return
}
for (--end; begin < end; ) {
int new_begin = end
int new_end = begin
for (int i = begin; i < end; ++i) {
Comparable c1 = (Comparable)array[i]
Comparable c2 = (Comparable)array[i + 1]
if (c1 > c2) {
swap(array, i, i + 1)
new_end = i
}
}
end = new_end
for (int i = end; i > begin; --i) {
Comparable c1 = (Comparable)array[i - 1]
Comparable c2 = (Comparable)array[i]
if (c1 > c2) {
swap(array, i, i - 1)
new_begin = i
}
}
begin = new_begin
}
}
private static void swap(Object[] array, int i, int j) {
Object tmp = array[i]
array[i] = array[j]
array[j] = tmp
}
}
- Output:
before: [5, 1, -6, 12, 3, 13, 2, 4, 0, 15] after: [-6, 0, 1, 2, 3, 4, 5, 12, 13, 15]
Java
import java.util.*;
public class CocktailSort {
public static void main(String[] args) {
Integer[] array = new Integer[]{ 5, 1, -6, 12, 3, 13, 2, 4, 0, 15 };
System.out.println("before: " + Arrays.toString(array));
cocktailSort(array);
System.out.println("after: " + Arrays.toString(array));
}
// Sorts an array of elements that implement the Comparable interface
public static void cocktailSort(Object[] array) {
int begin = 0;
int end = array.length;
if (end == 0)
return;
for (--end; begin < end; ) {
int new_begin = end;
int new_end = begin;
for (int i = begin; i < end; ++i) {
Comparable c1 = (Comparable)array[i];
Comparable c2 = (Comparable)array[i + 1];
if (c1.compareTo(c2) > 0) {
swap(array, i, i + 1);
new_end = i;
}
}
end = new_end;
for (int i = end; i > begin; --i) {
Comparable c1 = (Comparable)array[i - 1];
Comparable c2 = (Comparable)array[i];
if (c1.compareTo(c2) > 0) {
swap(array, i, i - 1);
new_begin = i;
}
}
begin = new_begin;
}
}
private static void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
- Output:
before: [5, 1, -6, 12, 3, 13, 2, 4, 0, 15] after: [-6, 0, 1, 2, 3, 4, 5, 12, 13, 15]
Julia
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)
Kotlin
fun <T> swap(array: Array<T>, i: Int, j: Int) {
val temp = array[i]
array[i] = array[j]
array[j] = temp
}
fun <T> cocktailSort(array: Array<T>) where T : Comparable<T> {
var begin = 0
var end = array.size
if (end == 0) {
return
}
--end
while (begin < end) {
var newBegin = end
var newEnd = begin
for (i in begin until end) {
val c1 = array[i]
val c2 = array[i + 1]
if (c1 > c2) {
swap(array, i, i + 1)
newEnd = i
}
}
end = newEnd
for (i in end downTo begin + 1) {
val c1 = array[i - 1]
val c2 = array[i]
if (c1 > c2) {
swap(array, i, i - 1)
newBegin = i
}
}
begin = newBegin
}
}
fun main() {
val array: Array<Int> = intArrayOf(5, 1, -6, 12, 3, 13, 2, 4, 0, 15).toList().toTypedArray()
println("before: ${array.contentToString()}")
cocktailSort(array)
println("after: ${array.contentToString()}")
}
- Output:
before: [5, 1, -6, 12, 3, 13, 2, 4, 0, 15] after: [-6, 0, 1, 2, 3, 4, 5, 12, 13, 15]
Mathematica/Wolfram Language
ClearAll[CocktailShakerSort]
CocktailShakerSort[in_List] :=
Module[{x = in, swapped, begin = 1, end = Length[in] - 1},
swapped = True;
While[swapped,
swapped = False;
Do[
If[x[[i]] > x[[i + 1]],
x[[{i, i + 1}]] //= Reverse;
swapped = True;
]
,
{i, begin, end}
];
end--;
Do[
If[x[[i]] > x[[i + 1]],
x[[{i, i + 1}]] //= Reverse;
swapped = True;
]
,
{i, end, begin, -1}
];
begin++;
];
x
]
CocktailShakerSort[{44, 21, 5, 88, 52, 44, 36, 93, 66, 18, 88, 61, 45, 47, 47, 68, 19, 60}]
- Output:
{5, 18, 19, 21, 36, 44, 44, 45, 47, 47, 52, 60, 61, 66, 68, 88, 88, 93}
Nim
proc cocktailShakerSort[T](a: var openarray[T]) =
var beginIdx = 0
var endIdx = a.len - 2
while beginIdx <= endIdx:
var newBeginIdx = endIdx
var newEndIdx = beginIdx
for i in beginIdx..endIdx:
if a[i] > a[i + 1]:
swap a[i], a[i + 1]
newEndIdx = i
endIdx = newEndIdx - 1
for i in countdown(endIdx, beginIdx):
if a[i] > a[i + 1]:
swap a[i], a[i + 1]
newBeginIdx = i
beginIdx = newBeginIdx + 1
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
cocktailShakerSort a
echo a
- Output:
@[-31, 0, 2, 2, 4, 65, 83, 99, 782]
Perl
use strict;
use warnings;
use feature 'say';
sub cocktail_sort {
my @a = @_;
my ($min, $max) = (0, $#a-1);
while (1) {
my $swapped_forward = 0;
for my $i ($min .. $max) {
if ($a[$i] gt $a[$i+1]) {
@a[$i, $i+1] = @a[$i+1, $i];
$swapped_forward = 1
}
}
last if not $swapped_forward;
$max -= 1;
my $swapped_backward = 0;
for my $i (reverse $min .. $max) {
if ($a[$i] gt $a[$i+1]) {
@a[$i, $i+1] = @a[$i+1, $i];
$swapped_backward = 1;
}
}
last if not $swapped_backward;
$min += 1;
}
@a
}
say join ' ', cocktail_sort( <t h e q u i c k b r o w n f o x j u m p s o v e r t h e l a z y d o g> );
- Output:
a b c d e e e f g h h i j k l m n o o o o p q r r s t t u u v w x y z
Phix
Averages 7 or 8% better than Sorting_algorithms/Cocktail_sort#Phix which already shifted the bounds, however this shifts >1 (sometimes).
with javascript_semantics function cocktailShakerSort(sequence s) s = deep_copy(s) integer beginIdx = 1, endIdx = length(s)-1 while beginIdx <= endIdx do integer newBeginIdx = endIdx, newEndIdx = beginIdx for ii=beginIdx to endIdx do object si = s[ii], sn = s[ii+1] if si>sn then s[ii] = sn s[ii+1] = si 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 object si = s[ii], sn = s[ii+1] if si>sn then s[ii] = sn s[ii+1] = si 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"}}
Python
"""
Python example of
http://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort_with_shifting_bounds
based on
http://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort#Python
"""
def cocktailshiftingbounds(A):
beginIdx = 0
endIdx = len(A) - 1
while beginIdx <= endIdx:
newBeginIdx = endIdx
newEndIdx = beginIdx
for ii in range(beginIdx,endIdx):
if A[ii] > A[ii + 1]:
A[ii+1], A[ii] = A[ii], A[ii+1]
newEndIdx = ii
endIdx = newEndIdx
for ii in range(endIdx,beginIdx-1,-1):
if A[ii] > A[ii + 1]:
A[ii+1], A[ii] = A[ii], A[ii+1]
newBeginIdx = ii
beginIdx = newBeginIdx + 1
test1 = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
cocktailshiftingbounds(test1)
print(test1)
test2=list('big fjords vex quick waltz nymph')
cocktailshiftingbounds(test2)
print(''.join(test2))
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] abcdefghiijklmnopqrstuvwxyz
Quackery
[ stack ] is limit ( --> s )
[ stack ] is offset ( --> s )
[ offset share +
2dup 1+ peek dip peek > ] is compare ( [ n --> b )
[ offset share +
dup 1+ unrot
2dup peek
dip
[ 2dup 1+ peek
unrot poke
swap ]
unrot poke ] is exchange ( [ n --> [ )
[ dup size 1 - limit put
0 offset put
[ 0 swap
limit share times
[ dup i^ compare if
[ i^ exchange
dip 1+ ] ]
over while
limit share times
[ dup i compare if
[ i exchange
dip 1+ ] ]
over while
-2 limit tally
1 offset tally
nip again ]
nip
limit release
offset release ] is cocktail ( [ --> [ )
randomise
[] 20 times [ 89 random 10 + join ]
dup echo cr
cocktail echo
- Output:
[ 88 46 64 82 35 34 92 15 48 78 94 19 50 79 62 19 42 79 43 50 ] [ 15 19 19 34 35 42 43 46 48 50 50 62 64 78 79 79 82 88 92 94 ]
Raku
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
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; _=@.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.*/
- 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
Rust
fn cocktail_shaker_sort<T: PartialOrd>(a: &mut [T]) {
let mut begin = 0;
let mut end = a.len();
if end == 0 {
return;
}
end -= 1;
while begin < end {
let mut new_begin = end;
let mut new_end = begin;
for i in begin..end {
if a[i + 1] < a[i] {
a.swap(i, i + 1);
new_end = i;
}
}
end = new_end;
let mut i = end;
while i > begin {
if a[i] < a[i - 1] {
a.swap(i, i - 1);
new_begin = i;
}
i -= 1;
}
begin = new_begin;
}
}
fn main() {
let mut v = vec![5, 1, -6, 12, 3, 13, 2, 4, 0, 15];
println!("before: {:?}", v);
cocktail_shaker_sort(&mut v);
println!("after: {:?}", v);
}
- Output:
before: [5, 1, -6, 12, 3, 13, 2, 4, 0, 15] after: [-6, 0, 1, 2, 3, 4, 5, 12, 13, 15]
Swift
func cocktailShakerSort<T: Comparable>(_ a: inout [T]) {
var begin = 0
var end = a.count
if end == 0 {
return
}
end -= 1
while begin < end {
var new_begin = end
var new_end = begin
var i = begin
while i < end {
if a[i + 1] < a[i] {
a.swapAt(i, i + 1)
new_end = i
}
i += 1
}
end = new_end
i = end
while i > begin {
if a[i] < a[i - 1] {
a.swapAt(i, i - 1)
new_begin = i
}
i -= 1
}
begin = new_begin
}
}
var array = [5, 1, -6, 12, 3, 13, 2, 4, 0, 15]
print("before: \(array)")
cocktailShakerSort(&array)
print(" after: \(array)")
var array2 = ["one", "two", "three", "four", "five", "six", "seven", "eight"]
print("before: \(array2)")
cocktailShakerSort(&array2)
print(" after: \(array2)")
- Output:
before: [5, 1, -6, 12, 3, 13, 2, 4, 0, 15] after: [-6, 0, 1, 2, 3, 4, 5, 12, 13, 15] before: ["one", "two", "three", "four", "five", "six", "seven", "eight"] after: ["eight", "five", "four", "one", "seven", "six", "three", "two"]
VBA
' 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
' 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
' 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
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
XPL0
Translation of the pseudo code from Wikipedia.
procedure CocktailShakerSort(A, Length);
integer A, Length;
integer BeginIdx, EndIdx; \mark the first and last index to check
integer NewBeginIdx, NewEndIdx, II, T;
begin
BeginIdx:= 0;
EndIdx:= Length - 1;
while BeginIdx <= EndIdx do
begin
NewBeginIdx:= EndIdx;
NewEndIdx:= BeginIdx;
for II:= BeginIdx to EndIdx - 1 do
begin
if A(II) > A(II + 1) then
begin
T:= A(II+1); A(II+1):= A(II); A(II):= T;
NewEndIdx:= II;
end;
end;
\Decreases EndIdx because the elements after NewEndIdx are in correct order
EndIdx:= NewEndIdx;
for II:= EndIdx downto BeginIdx - 1 do
begin
if A(II) > A(II + 1) then
begin
T:= A(II+1); A(II+1):= A(II); A(II):= T;
NewBeginIdx:= II;
end;
end;
\Increases BeginIdx because elements before NewBeginIdx are in correct order
BeginIdx:= NewBeginIdx + 1;
end;
end;
int Test, Len, I;
begin
Test:= [7, 6, 5, 9, 8, 4, 3, 1, 2, 0];
Len:= 10;
CocktailShakerSort(Test, Len);
for I:= 0 to Len-1 do
begin
IntOut(0, Test(I));
ChOut(0, ^ );
end;
end
- Output:
0 1 2 3 4 5 6 7 8 9