Sorting algorithms/Cocktail sort
(Redirected from Cocktail Sort)
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 shaker sort is an improvement on the Bubble Sort.
The improvement is basically that values "bubble" both directions through the array, because on each iteration the cocktail shaker sort bubble sorts once forwards and once backwards. Pseudocode for the algorithm (from wikipedia):
function cocktailSort( A : list of sortable items )
do
swapped := false
for each i in 0 to length( A ) - 2 do
if A[ i ] > A[ i+1 ] then // test whether the two
// elements are in the wrong
// order
swap( A[ i ], A[ i+1 ] ) // let the two elements
// change places
swapped := true;
if swapped = false then
// we can exit the outer loop here if no swaps occurred.
break do-while loop;
swapped := false
for each i in length( A ) - 2 down to 0 do
if A[ i ] > A[ i+1 ] then
swap( A[ i ], A[ i+1 ] )
swapped := true;
while swapped; // if no elements have been swapped,
// then the list is sorted
- Related task
11l
F cocktailSort(&A)
L
L(indices) ((0 .< A.len-1).step(1), (A.len-2 .. 0).step(-1))
V swapped = 0B
L(i) indices
I A[i] > A[i + 1]
swap(&A[i], &A[i + 1])
swapped = 1B
I !swapped
R
V test1 = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
cocktailSort(&test1)
print(test1)- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
360 Assembly
The program uses 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 25/06/2016
COCKTSRT CSECT
USING COCKTSRT,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
STM R14,R12,12(R13) prolog
ST R13,4(R15) "
ST R15,8(R13) "
LR R13,R15 "
L R2,N n
BCTR R2,0 n-1
ST R2,NM1 nm1=n-1
DO UNTIL=(CLI,STABLE,EQ,X'01') repeat
MVI STABLE,X'01' stable=true
LA RI,1 i=1
DO WHILE=(C,RI,LE,NM1) do i=1 to n-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
MVI STABLE,X'00' stable=false
ST R5,0(R2) a(i)=r5
ST R4,0(R3) a(i+1)=r4
ENDIF , end if
LA RI,1(RI) i=i+1
ENDDO , end do
L RI,NM1 i=n-1
DO WHILE=(C,RI,GE,=F'1') do i=n-1 to 1 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
MVI STABLE,X'00' stable=false
ST R5,0(R2) a(i)=r5
ST R4,0(R3) a(i+1)=r4
ENDIF , end if
BCTR RI,0 i=i-1
ENDDO , end do
ENDDO , until stable
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) epilog
LM R14,R12,12(R13) "
XR R15,R15 "
BR R14 exit
A DC F'4',F'65',F'2',F'-31',F'0',F'99',F'2',F'83',F'782',F'1'
DC F'45',F'82',F'69',F'82',F'104',F'58',F'88',F'112',F'89',F'74'
N DC A((N-A)/L'A) number of items of a
NM1 DS F n-1
PG DC CL80' ' buffer
XDEC DS CL12 temp for xdeco
STABLE DS X stable
YREGS
RI EQU 6 i
END COCKTSRT- Output:
-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782
6502 Assembly
Implemented in Easy6502. Output is provided below but it's best to watch this in action. Just copy and paste the code in, hit Assemble then Run. Make sure you check the Monitor box and set the address to 1200 and the length to 100. This takes about half as long as the bubble sort.
define z_HL $00
define z_L $00
define z_H $01
define temp $02
define temp2 $03
define yINC $04
define yDEC $05
set_table:
dex
txa
sta $1200,y
iny
bne set_table ;stores $ff at $1200, $fe at $1201, etc.
lda #$12
sta z_H
lda #$00
sta z_L ;get the base address of the data table
lda #0
tax
tay ;clear regs
sty yINC ;yINC = 0
dey ;LDY #255
sty yDEC ;yDEC = 255
iny ;LDY #0
JSR COCKTAILSORT
BRK
COCKTAILSORT:
;yINC starts at the beginning and goes forward, yDEC starts at the end and goes back.
LDY yINC
LDA (z_HL),y ;get item Y
STA temp
INY
LDA (z_HL),y ;get item Y+1
DEY
STA temp2
CMP temp
bcs doNothing_Up ;if Y<=Y+1, do nothing. Otherwise swap them.
;we had to re-arrange an item.
lda temp
iny
sta (z_HL),y ;store the higher value at base+y+1
inx ;sort count. If zero at the end, we're done.
dey
lda temp2
sta (z_HL),y ;store the lower value at base+y
doNothing_Up:
LDY yDEC
LDA (z_HL),y
STA temp
DEY
LDA (z_HL),y
INY
STA temp2
CMP temp
bcc doNothing_Down ;if Y<=Y+1, do nothing. Otherwise swap them.
;we had to re-arrange an item.
lda temp
dey
sta (z_HL),y ;store the higher value at base+y+1
inx ;sort count. If zero at the end, we're done.
iny
lda temp2
sta (z_HL),y ;store the lower value at base+y
doNothing_Down:
INC yINC
DEC yDEC
LDA yINC
BPL COCKTAILSORT
CPX #0
BEQ doneSorting
LDX #0 ;reset the counter
LDY #0
STY yINC
DEY ;LDY #$FF
STY yDEC
INY ;LDY #0
JMP COCKTAILSORT
doneSorting:
RTS- Output:
1200: 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 1210: 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f 1220: 20 21 22 23 24 25 26 27 28 29 2a 2b 2c 2d 2e 2f 1230: 30 31 32 33 34 35 36 37 38 39 3a 3b 3c 3d 3e 3f 1240: 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f 1250: 50 51 52 53 54 55 56 57 58 59 5a 5b 5c 5d 5e 5f 1260: 60 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 1270: 70 71 72 73 74 75 76 77 78 79 7a 7b 7c 7d 7e 7f 1280: 80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f 1290: 90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f 12a0: a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 aa ab ac ad ae af 12b0: b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf 12c0: c0 c1 c2 c3 c4 c5 c6 c7 c8 c9 ca cb cc cd ce cf 12d0: d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 da db dc dd de df 12e0: e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 ea eb ec ed ee ef 12f0: f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 fa fb fc fd fe ff
AArch64 Assembly
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program cocktailSort64.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 cocktailSort
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 */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the first element */
/* x2 contains the number of element */
cocktailSort:
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,1 // compute i = n - 1
1: // start loop 1
mov x3,x1 // start index
mov x9,0
sub x7,x2,1
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 x9,1 // top table not sorted
3:
add x3,x3,1 // increment index j
cmp x3,x7 // end ?
ble 2b // no -> loop 2
cmp x9,0 // table sorted ?
beq 100f // yes -> end
mov x9,0
mov x3,x7
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 x9,1 // top table not sorted
5:
sub x3,x3,1 // decrement index j
cmp x3,x1 // end ?
bge 4b // no -> loop 2
cmp x9,0 // table sorted ?
bne 1b // no -> 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
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 CoctailSort(INT ARRAY a INT size)
INT i,tmp
BYTE swapped
DO
swapped=0
i=0
WHILE i<size-1
DO
IF a(i)>a(i+1) THEN
tmp=a(i) a(i)=a(i+1) a(i+1)=tmp
swapped=1
FI
i==+1
OD
IF swapped=0 THEN EXIT FI
swapped=0
i=size-1
WHILE i>=0
DO
IF a(i)>a(i+1) THEN
tmp=a(i) a(i)=a(i+1) a(i+1)=tmp
swapped=1
FI
i==-1
OD
UNTIL swapped=0
OD
RETURN
PROC Test(INT ARRAY a INT size)
PrintE("Array before sort:")
PrintArray(a,size)
CoctailSort(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]
ActionScript
function cocktailSort(input:Array):Array {
do {
var swapped:Boolean=false;
for (var i:uint = 0; i < input.length-1; i++) {
if (input[i]>input[i+1]) {
var tmp=input[i];
input[i]=input[i+1];
input[i+1]=tmp;
swapped=true;
}
}
if (! swapped) {
break;
}
for (i = input.length -2; i >= 0; i--) {
if (input[i]>input[i+1]) {
tmp=input[i];
input[i]=input[i+1];
input[i+1]=tmp;
swapped=true;
}
}
} while (swapped);
return input;
}
Ada
with Ada.Text_Io; use Ada.Text_Io;
procedure Cocktail_Sort_Test is
procedure Cocktail_Sort (Item : in out String) is
procedure Swap(Left, Right : in out Character) is
Temp : Character := Left;
begin
Left := Right;
Right := Temp;
end Swap;
Swapped : Boolean := False;
begin
loop
for I in 1..Item'Last - 1 loop
if Item(I) > Item(I + 1) then
Swap(Item(I), Item(I + 1));
Swapped := True;
end if;
end loop;
if not Swapped then
for I in reverse 1..Item'Last - 1 loop
if Item(I) > Item(I + 1) then
Swap(Item(I), Item(I + 1));
Swapped := True;
end if;
end loop;
end if;
exit when not Swapped;
Swapped := False;
end loop;
end Cocktail_Sort;
Data : String := "big fjords vex quick waltz nymph";
begin
Put_Line(Data);
Cocktail_Sort(Data);
Put_Line(Data);
end Cocktail_Sort_Test;
ALGOL 60
begin
comment Sorting algorithms/Cocktail sort - 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
MODE DATA = CHAR;
PROC swap = (REF DATA a,b)VOID:(
DATA tmp:=a; a:=b; b:=tmp
);
PROC cocktail sort = (REF[]DATA a)VOID: (
WHILE
BOOL swapped := FALSE;
FOR i FROM LWB a TO UPB a - 1 DO
IF a[ i ] > a[ i + 1 ] THEN # test whether the two elements are in the wrong order #
swap( a[ i ], a[ i + 1 ] ); # let the two elements change places #
swapped := TRUE
FI
OD;
IF NOT swapped THEN
# we can exit the outer loop here if no swaps occurred. #
break do while loop
FI;
swapped := FALSE;
FOR i FROM UPB a - 1 TO LWB a DO
IF a[ i ] > a[ i + 1 ] THEN
swap( a[ i ], a[ i + 1 ] );
swapped := TRUE
FI
OD;
# WHILE # swapped # if no elements have been swapped, then the list is sorted #
DO SKIP OD;
break do while loop: SKIP
);
[32]CHAR data := "big fjords vex quick waltz nymph";
cocktail sort(data);
print(data)- Output:
abcdefghiijklmnopqrstuvwxyz
Alternatively - when the data records are large - the data can be manipulated indirectly, thus removing the need to actually swap large chunks of memory as only addresses are swapped.
MODE DATA = REF CHAR;
PROC swap = (REF DATA a,b)VOID:(
DATA tmp:=a; a:=b; b:=tmp
);
PROC (REF[]DATA a)VOID cocktail sort;
[32]CHAR data := "big fjords vex quick waltz nymph";
[UPB data]DATA ref data; FOR i TO UPB data DO ref data[i] := data[i] OD;
cocktail sort(ref data);
FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line);
print((data))- Output:
abcdefghiijklmnopqrstuvwxyz big fjords vex quick waltz nymph
The above two routines both scan the entire width of the array, in both directions, even though the first and last elements of each sweep had already reached their final destination during the previous pass. The solution is to zig-zag, but have the sweeps shorten and converge on the centre element. This reduces the number of comparisons required by about 50%.
PROC odd even sort = (REF []DATA a)VOID: (
FOR offset FROM 0 DO
BOOL swapped := FALSE;
FOR i FROM LWB a + offset TO UPB a - 1 - offset DO
IF a[ i ] > a[ i + 1 ] THEN # test whether the two elements are in the wrong order #
swap( a[ i ], a[ i + 1 ] ); # let the two elements change places #
swapped := TRUE
FI
OD;
# we can exit the outer loop here if no swaps occurred. #
IF NOT swapped THEN break do od loop FI;
swapped := FALSE;
FOR i FROM UPB a - 1 - offset - 1 BY - 1 TO LWB a + offset DO
IF a[ i ] > a[ i + 1 ] THEN
swap( a[ i ], a[ i + 1 ] );
swapped := TRUE
FI
OD;
# if no elements have been swapped, then the list is sorted #
IF NOT swapped THEN break do od loop FI;
OD;
break do od loop: SKIP
);ALGOL W
As noted in the ALGOL 68 sample above, the highest and lowest elements are sorted into their correct positions each time through the main loop. This implementation optimises by reducing the number of elements to sort on each pass through the main loop.
begin
% As algol W does not allow overloading, we have to have type-specific %
% sorting procedures - this coctail sorts an integer array %
% as there is no way for the procedure to determine the array bounds, we %
% pass the lower and upper bounds in lb and ub %
procedure coctailSortIntegers( integer array item( * )
; integer value lb
; integer value ub
) ;
begin
integer lower, upper;
lower := lb;
upper := ub - 1;
while
begin
logical swapped;
procedure swap( integer value i ) ;
begin
integer val;
val := item( i );
item( i ) := item( i + 1 );
item( i + 1 ) := val;
swapped := true;
end swap ;
swapped := false;
for i := lower until upper do if item( i ) > item( i + 1 ) then swap( i );
if swapped
then begin
% there was at least one unordered element so try a 2nd sort pass %
for i := upper step -1 until lower do if item( i ) > item( i + 1 ) then swap( i );
upper := upper - 1; lower := lower + 1;
end if_swapped ;
swapped
end
do begin end;
end coctailSortIntegers ;
begin % test the sort %
integer array data( 1 :: 10 );
procedure writeData ;
begin
write( data( 1 ) );
for i := 2 until 10 do writeon( data( i ) );
end writeData ;
% initialise data to unsorted values %
integer dPos;
dPos := 1;
for i := 16, 2, -6, 9, 90, 14, 0, 23, 8, 9
do begin
data( dPos ) := i;
dPos := dPos + 1;
end for_i ;
i_w := 3; s_w := 1; % set output format %
writeData;
coctailSortIntegers( data, 1, 10 );
writeData;
end test ;
end.- Output:
16 2 -6 9 90 14 0 23 8 9 -6 0 2 8 9 9 14 16 23 90
ARM Assembly
/* ARM assembly Raspberry PI */
/* program cocktailSort.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 cocktailSort
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 */
cocktailSort:
push {r1-r9,lr} @ save registers
sub r2,r2,#1 @ compute i = n - 1
add r8,r1,#1
1: @ start loop 1
mov r3,r1 @ start index
mov r9,#0
sub r7,r2,#1 @ max
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 r9,#1 @ top table not sorted
add r3,#1 @ increment index j
cmp r3,r7 @ end ?
ble 2b @ no -> loop 2
cmp r9,#0 @ table sorted ?
beq 100f @ yes -> end
@ bl displayTable
mov r9,#0
mov r3,r7
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 r9,#1 @ top table not sorted
sub r3,#1 @ decrement index j
cmp r3,r1 @ end ?
bge 3b @ no -> loop 2
@ bl displayTable
cmp r9,#0 @ table sorted ?
bne 1b @ no -> 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 signed
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
trySwap: function [arr,i][
if arr\[i] < arr\[i-1] [
tmp: arr\[i]
arr\[i]: arr\[i-1]
arr\[i-1]: tmp
return null
]
return true
]
cocktailSort: function [items][
t: false
l: size items
while [not? t][
t: true
loop 1..dec l 'i [
if null? trySwap items i ->
t: false
]
if t -> break
loop (l-1)..1 'i [
if null? trySwap items i ->
t: false
]
]
return items
]
print cocktailSort [3 1 2 8 5 7 9 4 6]
- Output:
1 2 3 4 5 6 7 8 9
AutoHotkey
contributed by Laszlo on the ahk forum
MsgBox % CocktailSort("")
MsgBox % CocktailSort("xxx")
MsgBox % CocktailSort("3,2,1")
MsgBox % CocktailSort("dog,000000,xx,cat,pile,abcde,1,cat,zz,xx,z")
CocktailSort(var) { ; SORT COMMA SEPARATED LIST
StringSplit array, var, `, ; make array
i0 := 1, i1 := array0 ; start, end
Loop { ; break when sorted
Changed =
Loop % i1-- -i0 { ; last entry will be in place
j := i0+A_Index, i := j-1
If (array%j% < array%i%) ; swap?
t := array%i%, array%i% := array%j%, array%j% := t
,Changed = 1 ; change has happened
}
IfEqual Changed,, Break
Loop % i1-i0++ { ; first entry will be in place
i := i1-A_Index, j := i+1
If (array%j% < array%i%) ; swap?
t := array%i%, array%i% := array%j%, array%j% := t
,Changed = 1 ; change has happened
}
IfEqual Changed,, Break
}
Loop % array0 ; construct string from sorted array
sorted .= "," . array%A_Index%
Return SubStr(sorted,2) ; drop leading comma
}
AWK
Sort the standard input and print it to standard output
{
line[NR] = $0
}
END { # sort it with cocktail sort
swapped = 0
do {
for(i=1; i < NR; i++) {
if ( line[i] > line[i+1] ) {
t = line[i]
line[i] = line[i+1]
line[i+1] = t
swapped = 1
}
}
if ( swapped == 0 ) break
swapped = 0
for(i=NR-1; i >= 1; i--) {
if ( line[i] > line[i+1] ) {
t = line[i]
line[i] = line[i+1]
line[i+1] = t
swapped = 1
}
}
} while ( swapped == 1 )
#print it
for(i=1; i <= NR; i++) {
print line[i]
}
}
BBC BASIC
Sorting an integer array. '%' indicates integer variable in BBC BASIC
DEF PROC_ShakerSort(Size%)
Start%=2
End%=Size%
Direction%=1
LastChange%=1
REPEAT
FOR J% = Start% TO End% STEP Direction%
IF data%(J%-1) > data%(J%) THEN
SWAP data%(J%-1),data%(J%)
LastChange% = J%
ENDIF
NEXT J%
End% = Start%
Start% = LastChange% - Direction%
Direction% = Direction% * -1
UNTIL ( ( End% * Direction% ) < ( Start% * Direction% ) )
ENDPROCC
#include <stdio.h>
// can be any swap function. This swap is optimized for numbers.
void swap(int *x, int *y) {
if(x == y)
return;
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
void cocktailsort(int *a, size_t n) {
while(1) {
// packing two similar loops into one
char flag;
size_t start[2] = {1, n - 1},
end[2] = {n, 0},
inc[2] = {1, -1};
for(int it = 0; it < 2; ++it) {
flag = 1;
for(int i = start[it]; i != end[it]; i += inc[it])
if(a[i - 1] > a[i]) {
swap(a + i - 1, a + i);
flag = 0;
}
if(flag)
return;
}
}
}
int main(void) {
int a[] = { 5, -1, 101, -4, 0, 1, 8, 6, 2, 3 };
size_t n = sizeof(a)/sizeof(a[0]);
cocktailsort(a, n);
for (size_t i = 0; i < n; ++i)
printf("%d ", a[i]);
return 0;
}
Output:
-4 -1 0 1 2 3 5 6 8 101
Generic version
This version can be used with arrays of any type, like the standard library function qsort.
#include <stdbool.h>
#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_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;
bool swapped = true;
for (end -= size; swapped; ) {
swapped = false;
for (char* p = begin; p < end; p += size) {
char* q = p + size;
if (cmp(p, q) > 0) {
swap(p, q, size);
swapped = true;
}
}
if (!swapped)
break;
swapped = false;
for (char* p = end; p > begin; p -= size) {
char* q = p - size;
if (cmp(q, p) > 0) {
swap(p, q, size);
swapped = true;
}
}
}
}
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", "nine", "ten" };
const size_t len = sizeof(a)/sizeof(a[0]);
printf("before: ");
print(a, len);
cocktail_sort(a, len, sizeof(char*), string_compare);
printf("after: ");
print(a, len);
return 0;
}
- Output:
before: one two three four five six seven eight nine ten after: eight five four nine one seven six ten three two
C#
public static void cocktailSort(int[] A)
{
bool swapped;
do
{
swapped = false;
for (int i = 0; i <= A.Length - 2; i++)
{
if (A[i] > A[i + 1])
{
//test whether the two elements are in the wrong order
int temp = A[i];
A[i] = A[i + 1];
A[i + 1] = temp;
swapped = true;
}
}
if (!swapped)
{
//we can exit the outer loop here if no swaps occurred.
break;
}
swapped = false;
for (int i = A.Length - 2; i >= 0; i--)
{
if (A[i] > A[i + 1])
{
int temp = A[i];
A[i] = A[i + 1];
A[i + 1] = temp;
swapped = true;
}
}
//if no elements have been swapped, then the list is sorted
} while (swapped);
}
C++
#include <iostream>
#include <windows.h>
const int EL_COUNT = 77, LLEN = 11;
class cocktailSort
{
public:
void sort( int* arr, int len )
{
bool notSorted = true;
while( notSorted )
{
notSorted = false;
for( int a = 0; a < len - 1; a++ )
{
if( arr[a] > arr[a + 1] )
{
sSwap( arr[a], arr[a + 1] );
notSorted = true;
}
}
if( !notSorted ) break;
notSorted = false;
for( int a = len - 1; a > 0; a-- )
{
if( arr[a - 1] > arr[a] )
{
sSwap( arr[a], arr[a - 1] );
notSorted = true;
}
}
}
}
private:
void sSwap( int& a, int& b )
{
int t = a;
a = b; b = t;
}
};
int main( int argc, char* argv[] )
{
srand( GetTickCount() );
cocktailSort cs;
int arr[EL_COUNT];
for( int x = 0; x < EL_COUNT; x++ )
arr[x] = rand() % EL_COUNT + 1;
std::cout << "Original: " << std::endl << "==========" << std::endl;
for( int x = 0; x < EL_COUNT; x += LLEN )
{
for( int s = x; s < x + LLEN; s++ )
std::cout << arr[s] << ", ";
std::cout << std::endl;
}
//DWORD now = GetTickCount();
cs.sort( arr, EL_COUNT );
//now = GetTickCount() - now;
std::cout << std::endl << std::endl << "Sorted: " << std::endl << "========" << std::endl;
for( int x = 0; x < EL_COUNT; x += LLEN )
{
for( int s = x; s < x + LLEN; s++ )
std::cout << arr[s] << ", ";
std::cout << std::endl;
}
std::cout << std::endl << std::endl << std::endl << std::endl;
//std::cout << now << std::endl << std::endl;
return 0;
}
Alternate version
Uses C++11. Compile with
g++ -std=c++11 cocktail.cpp
#include <algorithm>
#include <iostream>
#include <iterator>
template <typename RandomAccessIterator>
void cocktail_sort(RandomAccessIterator begin, RandomAccessIterator end) {
bool swapped = true;
while (begin != end-- && swapped) {
swapped = false;
for (auto i = begin; i != end; ++i) {
if (*(i + 1) < *i) {
std::iter_swap(i, i + 1);
swapped = true;
}
}
if (!swapped) {
break;
}
swapped = false;
for (auto i = end - 1; i != begin; --i) {
if (*i < *(i - 1)) {
std::iter_swap(i, i - 1);
swapped = true;
}
}
++begin;
}
}
int main() {
int a[] = {100, 2, 56, 200, -52, 3, 99, 33, 177, -199};
cocktail_sort(std::begin(a), std::end(a));
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
}
- Output:
-199 -52 2 3 33 56 99 100 177 200
COBOL
This is procedure division only.
C-SORT SECTION.
C-000.
DISPLAY "SORT STARTING".
MOVE 2 TO WC-START
MOVE WC-SIZE TO WC-END.
MOVE 1 TO WC-DIRECTION
WC-LAST-CHANGE.
PERFORM E-SHAKER UNTIL WC-END * WC-DIRECTION <
WC-START * WC-DIRECTION.
DISPLAY "SORT FINISHED".
C-999.
EXIT.
E-SHAKER SECTION.
E-000.
PERFORM F-PASS VARYING WB-IX-1 FROM WC-START BY WC-DIRECTION
UNTIL WB-IX-1 = WC-END + WC-DIRECTION.
MOVE WC-START TO WC-END.
SUBTRACT WC-DIRECTION FROM WC-LAST-CHANGE GIVING WC-START.
MULTIPLY WC-DIRECTION BY -1 GIVING WC-DIRECTION.
E-999.
EXIT.
F-PASS SECTION.
F-000.
IF WB-ENTRY(WB-IX-1 - 1) > WB-ENTRY(WB-IX-1)
SET WC-LAST-CHANGE TO WB-IX-1
MOVE WB-ENTRY(WB-IX-1 - 1) TO WC-TEMP
MOVE WB-ENTRY(WB-IX-1) TO WB-ENTRY(WB-IX-1 - 1)
MOVE WC-TEMP TO WB-ENTRY(WB-IX-1).
F-999.
EXIT.
Common Lisp
This version works on lists and vectors alike. The vector implementation is coded directly. The list version uses an intermediate vector.
(defun cocktail-sort-vector (vector predicate &aux (len (length vector)))
(labels ((scan (start step &aux swapped)
(loop for i = start then (+ i step) while (< 0 i len) do
(when (funcall predicate (aref vector i)
(aref vector (1- i)))
(rotatef (aref vector i)
(aref vector (1- i)))
(setf swapped t)))
swapped))
(loop while (and (scan 1 1)
(scan (1- len) -1))))
vector)
(defun cocktail-sort (sequence predicate)
(etypecase sequence
(vector (cocktail-sort-vector sequence predicate))
(list (map-into sequence 'identity
(cocktail-sort-vector (coerce sequence 'vector)
predicate)))))
D
// Written in the D programming language.
module rosettaCode.sortingAlgorithms.cocktailSort;
import std.range;
Range cocktailSort(Range)(Range data)
if (isRandomAccessRange!Range && hasLvalueElements!Range) {
import std.algorithm : swap;
bool swapped = void;
void trySwap(E)(ref E lhs, ref E rhs) {
if (lhs > rhs) {
swap(lhs, rhs);
swapped = true;
}
}
if (data.length > 0) do {
swapped = false;
foreach (i; 0 .. data.length - 1)
trySwap(data[i], data[i + 1]);
if (!swapped)
break;
swapped = false;
foreach_reverse (i; 0 .. data.length - 1)
trySwap(data[i], data[i + 1]);
} while(swapped);
return data;
}
unittest {
assert (cocktailSort([3, 1, 5, 2, 4]) == [1, 2, 3, 4, 5]);
assert (cocktailSort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5]);
assert (cocktailSort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]);
assert (cocktailSort((int[]).init) == []);
assert (cocktailSort(["John", "Kate", "Zerg", "Alice", "Joe", "Jane"]) ==
["Alice", "Jane", "Joe", "John", "Kate", "Zerg"]);
}
- Output:
import rosettaCode.sortingAlgorithms.cocktailSort;
void main() {
import std.stdio, std.algorithm, std.range, std.random;
//generate 10 sorted random numbers in [0 .. 10)
rndGen.take(10).map!(a=>a%10).array.cocktailSort.writeln();
}
[2, 2, 3, 4, 5, 5, 7, 7, 7, 8]
Delphi
Dynamic array is a 0-based array of variable length
Static array is an arbitrary-based array of fixed length
program TestShakerSort;
{$APPTYPE CONSOLE}
{.$DEFINE DYNARRAY} // remove '.' to compile with dynamic array
type
TItem = Integer; // declare ordinal type for array item
{$IFDEF DYNARRAY}
TArray = array of TItem; // dynamic array
{$ELSE}
TArray = array[0..15] of TItem; // static array
{$ENDIF}
procedure ShakerSort(var A: TArray);
var
Item: TItem;
K, L, R, J: Integer;
begin
L:= Low(A) + 1;
R:= High(A);
K:= High(A);
repeat
for J:= R downto L do begin
if A[J - 1] > A[J] then begin
Item:= A[J - 1];
A[J - 1]:= A[J];
A[J]:= Item;
K:= J;
end;
end;
L:= K + 1;
for J:= L to R do begin
if A[J - 1] > A[J] then begin
Item:= A[J - 1];
A[J - 1]:= A[J];
A[J]:= Item;
K:= J;
end;
end;
R:= K - 1;
until L > R;
end;
var
A: TArray;
I: Integer;
begin
{$IFDEF DYNARRAY}
SetLength(A, 16);
{$ENDIF}
for I:= Low(A) to High(A) do
A[I]:= Random(100);
for I:= Low(A) to High(A) do
Write(A[I]:3);
Writeln;
ShakerSort(A);
for I:= Low(A) to High(A) do
Write(A[I]:3);
Writeln;
Readln;
end.
- Output:
0 3 86 20 27 67 31 16 37 42 8 47 7 84 5 29 0 3 5 7 8 16 20 27 29 31 37 42 47 67 84 86
E
/** Cocktail sort (in-place) */
def cocktailSort(array) {
def swapIndexes := 0..(array.size() - 2)
def directions := [swapIndexes, swapIndexes.descending()]
while (true) {
for direction in directions {
var swapped := false
for a ? (array[a] > array[def b := a + 1]) in direction {
def t := array[a]
array[a] := array[b]
array[b] := t
swapped := true
}
if (!swapped) { return }
}
}
}Note that this solution contains no repeated code to handle the forward and reverse passes.
EasyLang
proc sort . d[] .
a = 1
b = len d[] - 1
while a <= b
h = a
for i = a to b
if d[i] > d[i + 1]
swap d[i] d[i + 1]
h = i
.
.
b = h - 1
h = b
for i = b downto a
if d[i] > d[i + 1]
swap d[i] d[i + 1]
h = i
.
.
a = h + 1
.
.
l[] = [ 5 6 1 2 9 14 2 15 6 7 8 97 ]
sort l[]
print l[]
- Output:
[ 1 2 2 5 6 6 7 8 9 14 15 97 ]
Eiffel
class
COCKTAIL_SORT [G -> COMPARABLE]
feature
cocktail_sort (ar: ARRAY [G]): ARRAY [G]
-- Array sorted in ascending order.
require
ar_not_empty: ar.count >= 1
local
not_swapped: BOOLEAN
sol: ARRAY [G]
i, j: INTEGER
t: G
do
create Result.make_empty
Result.deep_copy (ar)
from
until
not_swapped = True
loop
not_swapped := True
from
i := Result.lower
until
i = Result.upper - 1
loop
if Result [i] > Result [i + 1] then
Result := swap (Result, i)
not_swapped := False
end
i := i + 1
end
from
j := Result.upper - 1
until
j = Result.lower
loop
if Result [j] > Result [j + 1] then
Result := swap (Result, j)
not_swapped := False
end
j := j - 1
end
end
ensure
ar_is_sorted: is_sorted (Result)
end
feature{NONE}
swap (ar: ARRAY [G]; i: INTEGER): ARRAY [G]
-- Array with elements i and i+1 swapped.
require
ar_not_void: ar /= Void
i_is_in_bounds: ar.valid_index (i)
local
t: G
do
create Result.make_empty
Result.deep_copy (ar)
t := Result [i]
Result [i] := Result [i + 1]
Result [i + 1] := t
ensure
swapped_right: Result [i + 1] = ar [i]
swapped_left: Result [i] = ar [i + 1]
end
is_sorted (ar: ARRAY [G]): BOOLEAN
--- Is 'ar' sorted in ascending order?
require
ar_not_empty: ar.is_empty = False
local
i: INTEGER
do
Result := True
from
i := ar.lower
until
i = ar.upper
loop
if ar [i] > ar [i + 1] then
Result := False
end
i := i + 1
end
end
end
Test:
class
APPLICATION
create
make
feature
make
do
test := <<5, 1, 99, 3, 2>>
io.put_string ("unsorted%N")
across
test as t
loop
io.put_string (t.item.out + "%T")
end
io.new_line
io.put_string ("sorted%N")
create cs
test := cs.cocktail_sort (test)
across
test as ar
loop
io.put_string (ar.item.out + "%T")
end
end
cs: COCKTAIL_SORT [INTEGER]
test: ARRAY [INTEGER]
end
- Output:
unsorted 5 1 99 3 2 sorted 1 2 3 5 99
Elena
ELENA 6.x :
import extensions;
import system'math;
import system'routines;
extension op
{
cocktailSort()
{
var list := self.clone();
bool swapped := true;
while(swapped)
{
swapped := false;
for(int i := 0; i <= list.Length - 2; i += 1)
{
if (list[i]>list[i+1])
{
list.exchange(i,i+1);
swapped := true
}
};
ifnot (swapped)
{
^ list
};
swapped := false;
for(int i := list.Length - 2; i >= 0; i -= 1)
{
if (list[i]>list[i+1])
{
list.exchange(i,i+1);
swapped := true
}
}
};
^ list
}
}
public program()
{
var list := new int[]{3, 5, 1, 9, 7, 6, 8, 2, 4 };
console.printLine("before:", list.asEnumerable());
console.printLine("after :", list.cocktailSort().asEnumerable())
}- Output:
before:3,5,1,9,7,6,8,2,4 after :1,2,3,4,5,6,7,8,9
Elixir
defmodule Sort do
def cocktail_sort(list) when is_list(list), do: cocktail_sort(list, [], [])
defp cocktail_sort([], minlist, maxlist), do: Enum.reverse(minlist, maxlist)
defp cocktail_sort([x], minlist, maxlist), do: Enum.reverse(minlist, [x | maxlist])
defp cocktail_sort(list, minlist, maxlist) do
{max, rev} = cocktail_max(list, [])
{min, rest} = cocktail_min(rev, [])
cocktail_sort(rest, [min | minlist], [max | maxlist])
end
defp cocktail_max([max], list), do: {max, list}
defp cocktail_max([x,y | t], list) when x<y, do: cocktail_max([y | t], [x | list])
defp cocktail_max([x,y | t], list) , do: cocktail_max([x | t], [y | list])
defp cocktail_min([min], list), do: {min, list}
defp cocktail_min([x,y | t], list) when x>y, do: cocktail_min([y | t], [x | list])
defp cocktail_min([x,y | t], list) , do: cocktail_min([x | t], [y | list])
end
IO.inspect Sort.cocktail_sort([5,3,9,4,1,6,8,2,7])
- Output:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Euphoria
function cocktail_sort(sequence s)
integer swapped, d
object temp
sequence fromto
fromto = {1,length(s)-1}
swapped = 1
d = 1
while swapped do
swapped = 0
for i = fromto[(1-d)/2+1] to fromto[(1+d)/2+1] by d do
if compare(s[i],s[i+1])>0 then
temp = s[i]
s[i] = s[i+1]
s[i+1] = temp
swapped = 1
end if
end for
d = -d
end while
return s
end function
constant s = rand(repeat(1000,10))
? s
? cocktail_sort(s)- Output:
{963,398,374,455,53,210,611,285,984,308}
{53,210,285,308,374,398,455,611,963,984}
Factor
Pseudocode translation
This is a faithful translation of the pseudocode given in the task description. It uses lexical variables.
USING: kernel locals math math.ranges sequences ;
:: cocktail-sort! ( seq -- seq' )
f :> swapped! ! bind false to mutable lexical variable 'swapped'. This must be done outside both while quotations so it is in scope of both.
[ swapped ] [ ! is swapped true? Then execute body quotation. 'do' executes body quotation before predicate on first pass.
f swapped! ! set swapped to false
seq length 2 - [| i | ! for each i in 0 to seq length - 2 do
i i 1 + [ seq nth ] bi@ > ! is element at index i greater than element at index i + 1?
[ i i 1 + seq exchange t swapped! ] when ! if so, swap them and set swapped to true
] each-integer
swapped [ ! skip to end of loop if swapped is false
seq length 2 - 0 [a,b] [| i | ! for each i in seq length - 2 to 0 do
i i 1 + [ seq nth ] bi@ > ! is element at index i greater than element at index i + 1?
[ i i 1 + seq exchange t swapped! ] when ! if so, swap them and set swapped to true
] each
] when
] do while
seq ; ! return the sequence
More idiomatic
This is perhaps a more idiomatic solution, eschewing the use of lexical variables. If we had tried to translate the pseudocode directly, we'd be dealing with a data stack that is 6+ values deep. Our main strategy against this is to factor the problem into short words that deal with only a few items at a time. When writing mutating words, we can simplify matters by writing words that return nothing, and letting the caller decide if and how to leave references on the data stack.
USING: fry kernel math math.ranges namespaces sequences ;
SYMBOL: swapped?
: dupd+ ( m obj -- m n obj ) [ dup 1 + ] dip ;
: 2nth ( n seq -- elt1 elt2 ) dupd+ [ nth ] curry bi@ ;
: ?exchange ( n seq -- )
2dup 2nth > [ dupd+ exchange swapped? on ] [ 2drop ] if ;
: cocktail-pass ( seq forward? -- )
'[ length 2 - 0 _ [ swap ] when [a,b] ] [ ] bi
[ ?exchange ] curry each ;
: (cocktail-sort!) ( seq -- seq' )
swapped? off dup t cocktail-pass
swapped? get [ dup f cocktail-pass ] when ;
: cocktail-sort! ( seq -- seq' )
[ swapped? get ] [ (cocktail-sort!) ] do while ;
Forth
defer precedes ( addr addr -- flag )
\ e.g. ' < is precedes
: sort ( a n --)
1- cells bounds 2>r false
begin
0= dup
while
2r@ ?do
i cell+ @ i @ over over precedes ( mark unsorted )
if i cell+ ! i ! dup xor else drop drop then
1 cells +loop
0= dup
while
2r@ swap 1 cells - ?do
i cell+ @ i @ over over precedes ( mark unsorted )
if i cell+ ! i ! dup xor else drop drop then
-1 cells +loop
repeat then drop 2r> 2drop
;
This is an optimized version:
: sort
1- cells bounds 1
begin
>r over over r@ -rot true -rot
r> 0< if 1 cells - then
?do
i cell+ @ i @ over over precedes ( mark unsorted )
if i cell+ ! i ! dup xor else drop drop then
over cells +loop
>r negate >r swap r@ cells + r> r>
until drop drop drop
;
Fortran
PROGRAM COCKTAIL
IMPLICIT NONE
INTEGER :: intArray(10) = (/ 4, 9, 3, -2, 0, 7, -5, 1, 6, 8 /)
WRITE(*,"(A,10I5)") "Unsorted array:", intArray
CALL Cocktail_sort(intArray)
WRITE(*,"(A,10I5)") "Sorted array :", intArray
CONTAINS
SUBROUTINE Cocktail_sort(a)
INTEGER, INTENT(IN OUT) :: a(:)
INTEGER :: i, bottom, top, temp
LOGICAL :: swapped
bottom = 1
top = SIZE(a) - 1
DO WHILE (bottom < top )
swapped = .FALSE.
DO i = bottom, top
IF (array(i) > array(i+1)) THEN
temp = array(i)
array(i) = array(i+1)
array(i+1) = temp
swapped = .TRUE.
END IF
END DO
IF (.NOT. swapped) EXIT
DO i = top, bottom + 1, -1
IF (array(i) < array(i-1)) THEN
temp = array(i)
array(i) = array(i-1)
array(i-1) = temp
swapped = .TRUE.
END IF
END DO
IF (.NOT. swapped) EXIT
bottom = bottom + 1
top = top - 1
END DO
END SUBROUTINE Cocktail_sort
END PROGRAM COCKTAIL
FreeBASIC
' version 21-10-2016
' compile with: fbc -s console
' for boundry checks on array's compile with: fbc -s console -exx
Sub cocktailsort(bs() As Long)
' sort from lower bound to the highter bound
' array's can have subscript range from -2147483648 to +2147483647
Dim As Long lb = LBound(bs)
Dim As Long ub = UBound(bs) -1
Dim As Long done, i
Do
done = 0 ' going up
For i = lb To ub
If bs(i) > bs(i +1) Then
Swap bs(i), bs(i +1)
done = 1
End If
Next
ub = ub -1
If done = 0 Then Exit Do ' 0 means the array is sorted
done = 0 ' going down
For i = ub To lb Step -1
If bs(i) > bs(i +1) Then
Swap bs(i), bs(i +1)
done = 1
End If
Next
lb = lb +1
Loop Until done = 0 ' 0 means the array is sorted
End Sub
' ------=< MAIN >=------
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
For i = a To b ' little shuffle
Swap array(i), array(Int(Rnd * (b - a +1)) + a)
Next
Print "unsorted ";
For i = a To b : Print Using "####"; array(i); : Next : Print
cocktailsort(array()) ' sort the array
Print " sorted ";
For i = a To b : Print Using "####"; array(i); : Next : Print
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
- Output:
unsorted -2 -4 7 -5 -7 4 2 -1 5 -6 6 1 0 -3 3 sorted -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7
Gambas
Click this link to run this code
Public Sub Main()
Dim siCount, siRev, siProcess As Short
Dim bSorting As Boolean
Dim byToSort As Byte[] = [249, 28, 111, 36, 171, 98, 29, 448, 44, 154, 147, 102, 46, 183, 24,
120, 19, 123, 2, 17, 226, 11, 211, 25, 191, 205, 77]
Print "To sort: -"
ShowWorking(byToSort)
Print
Repeat
bSorting = False
siRev = byToSort.Max - 1
For siCount = 0 To byToSort.Max - 1
siProcess = siCount
GoSub Check
siProcess = siRev
GoSub Check
Dec siRev
Next
If bSorting Then ShowWorking(byToSort)
Until bSorting = False
Return
Check:
If byToSort[siProcess] > byToSort[siProcess + 1] Then
Swap byToSort[siProcess], byToSort[siProcess + 1]
bSorting = True
Endif
Return
End
'-----------------------------------------
Public Sub ShowWorking(byToSort As Byte[])
Dim siCount As Byte
For siCount = 0 To byToSort.Max
Print Str(byToSort[siCount]);
If siCount <> byToSort.Max Then Print ",";
Next
Print
End
Output:
To sort: - 249,28,111,36,171,98,29,192,44,154,147,102,46,183,24,120,19,123,2,17,226,11,211,25,191,205,77 2,28,111,36,171,98,29,192,44,154,147,102,46,183,24,120,19,123,11,17,226,25,211,77,191,205,249 2,11,28,36,111,98,29,171,44,154,147,102,46,183,24,120,19,123,17,25,192,77,211,191,205,226,249 2,11,17,28,36,98,29,111,44,154,147,102,46,171,24,120,19,123,25,77,183,191,192,205,211,226,249 2,11,17,19,28,36,29,98,44,111,147,102,46,154,24,120,25,123,77,171,183,191,192,205,211,226,249 2,11,17,19,24,28,29,36,44,98,111,102,46,147,25,120,77,123,154,171,183,191,192,205,211,226,249 2,11,17,19,24,25,28,29,36,44,98,102,46,111,77,120,123,147,154,171,183,191,192,205,211,226,249 2,11,17,19,24,25,28,29,36,44,46,98,77,102,111,120,123,147,154,171,183,191,192,205,211,226,249 2,11,17,19,24,25,28,29,36,44,46,77,98,102,111,120,123,147,154,171,183,191,192,205,211,226,249
Go
package main
import "fmt"
func main() {
a := []int{170, 45, 75, -90, -802, 24, 2, 66}
fmt.Println("before:", a)
cocktailSort(a)
fmt.Println("after: ", a)
}
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
}
}
}
More generic version that sorts anything that implements sort.Interface:
package main
import (
"sort"
"fmt"
)
func main() {
a := []int{170, 45, 75, -90, -802, 24, 2, 66}
fmt.Println("before:", a)
cocktailSort(sort.IntSlice(a))
fmt.Println("after: ", a)
}
func cocktailSort(a sort.Interface) {
last := a.Len() - 1
for {
swapped := false
for i := 0; i < last; i++ {
if a.Less(i+1, i) {
a.Swap(i, i+1)
swapped = true
}
}
if !swapped {
return
}
swapped = false
for i := last - 1; i >= 0; i-- {
if a.Less(i+1, i) {
a.Swap(i, i+1)
swapped = true
}
}
if !swapped {
return
}
}
}
Groovy
Solution:
def makeSwap = { a, i, j = i+1 -> print "."; a[[j,i]] = a[[i,j]] }
def checkSwap = { a, i, j = i+1 -> [(a[i] > a[j])].find{ it }.each { makeSwap(a, i, j) } }
def cocktailSort = { list ->
if (list == null || list.size() < 2) return list
def n = list.size()
def swap = checkSwap.curry(list)
while (true) {
def swapped = (0..(n-2)).any(swap) && ((-2)..(-n)).any(swap)
if ( ! swapped ) break
}
list
}
Test:
println cocktailSort([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4])
println cocktailSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1])
println cocktailSort([ 3, 14, 1, 5, 9, 2, 6, 3 ])
println cocktailSort([ 3, 14 ])
println cocktailSort([ 33, 14 ])
- Output:
..............................................................................................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99] .........................................................................................................................................[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88] ..............[1, 2, 3, 3, 5, 6, 9, 14] [3, 14] .[14, 33]
Haskell
cocktailSort :: Ord a => [a] -> [a]
cocktailSort l
| not swapped1 = l
| not swapped2 = reverse $ l1
| otherwise = cocktailSort l2
where (swapped1, l1) = swappingPass (>) (False, []) l
(swapped2, l2) = swappingPass (<) (False, []) l1
swappingPass :: Ord a => (a -> a -> Bool) -> (Bool, [a]) -> [a] -> (Bool, [a])
swappingPass op (swapped, l) (x1 : x2 : xs)
| op x1 x2 = swappingPass op (True, x2 : l) (x1 : xs)
| otherwise = swappingPass op (swapped, x1 : l) (x2 : xs)
swappingPass _ (swapped, l) [x] = (swapped, x : l)
swappingPass _ pair [] = pair
Ksh
#!/bin/ksh
# cocktail shaker sort
# # Variables:
#
integer TRUE=1
integer FALSE=0
typeset -a arr=( 5 -1 101 -4 0 1 8 6 2 3 )
# # Functions:
#
function _swap {
typeset _i ; integer _i=$1
typeset _j ; integer _j=$2
typeset _array ; nameref _array="$3"
typeset _swapped ; nameref _swapped=$4
typeset _tmp ; _tmp=${_array[_i]}
_array[_i]=${_array[_j]}
_array[_j]=${_tmp}
_swapped=$TRUE
}
######
# main #
######
print "( ${arr[*]} )"
integer i j
integer swapped=$TRUE
while (( swapped )); do
swapped=$FALSE
for (( i=0 ; i<${#arr[*]}-2 ; i++ , j=i+1 )); do
(( arr[i] > arr[j] )) && _swap ${i} ${j} arr swapped
done
(( ! swapped )) && break
swapped=$FALSE
for (( i=${#arr[*]}-2 ; i>0 ; i-- , j=i+1 )); do
(( arr[i] > arr[j] )) && _swap ${i} ${j} arr swapped
done
done
print "( ${arr[*]} )"
- Output:
( 5 -1 101 -4 0 1 8 6 2 3 ) ( -4 -1 0 1 2 3 5 6 8 101 )
Haxe
class CocktailSort {
@:generic
public static function sort<T>(arr:Array<T>) {
var swapped = false;
do {
swapped = false;
for (i in 0...(arr.length - 1)) {
if (Reflect.compare(arr[i], arr[i + 1]) > 0) {
var temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
swapped = false;
var i = arr.length - 2;
while (i >= 0) {
if (Reflect.compare(arr[i], arr[i + 1]) > 0) {
var temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
i--;
}
} while (swapped);
}
}
class Main {
static function main() {
var integerArray = [1, 10, 2, 5, -1, 5, -19, 4, 23, 0];
var floatArray = [1.0, -3.2, 5.2, 10.8, -5.7, 7.3,
3.5, 0.0, -4.1, -9.5];
var stringArray = ['We', 'hold', 'these', 'truths', 'to',
'be', 'self-evident', 'that', 'all',
'men', 'are', 'created', 'equal'];
Sys.println('Unsorted Integers: ' + integerArray);
CocktailSort.sort(integerArray);
Sys.println('Sorted Integers: ' + integerArray);
Sys.println('Unsorted Floats: ' + floatArray);
CocktailSort.sort(floatArray);
Sys.println('Sorted Floats: ' + floatArray);
Sys.println('Unsorted Strings: ' + stringArray);
CocktailSort.sort(stringArray);
Sys.println('Sorted Strings: ' + stringArray);
}
}
- Output:
Unsorted Integers: [1,10,2,5,-1,5,-19,4,23,0] Sorted Integers: [-19,-1,0,1,2,4,5,5,10,23] Unsorted Floats: [1,-3.2,5.2,10.8,-5.7,7.3,3.5,0,-4.1,-9.5] Sorted Floats: [-9.5,-5.7,-4.1,-3.2,0,1,3.5,5.2,7.3,10.8] Unsorted Strings: [We,hold,these,truths,to,be,self-evident,that,all,men,are,created,equal] Sorted Strings: [We,all,are,be,created,equal,hold,men,self-evident,that,these,to,truths]
Icon and Unicon
Note: This example relies on the supporting procedures 'sortop', and 'demosort' in Bubble Sort. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.
- Abbreviated example output:
Sorting Demo using procedure cocktailsort
on list : [ 3 14 1 5 9 2 6 3 ]
with op = &null: [ 1 2 3 3 5 6 9 14 ] (0 ms)
...
on string : "qwerty"
with op = &null: "eqrtwy" (0 ms)
Io
List do (
cocktailSortInPlace := method(
start := 0
end := size - 2
loop(
swapped := false
for(idx, start, end,
if(at(idx) > at(idx + 1),
swapped := true
swapIndices(idx, idx + 1)
)
)
if(swapped not, break, end := end - 1)
for (idx, end, start, -1,
if(at(idx) > at(idx + 1),
swapped := true
swapIndices(idx, idx + 1)
)
)
if(swapped not, break, start := start + 1)
)
self)
)
l := list(2, 3, 4, 5, 1)
l cocktailSortInPlace println # ==> list(1, 2, 3, 4, 5)
IS-BASIC
100 PROGRAM "CocktSrt.bas"
110 RANDOMIZE
120 NUMERIC ARRAY(5 TO 24)
130 CALL INIT(ARRAY)
140 CALL WRITE(ARRAY)
150 CALL COCKTAILSORT(ARRAY)
160 CALL WRITE(ARRAY)
170 DEF INIT(REF A)
180 FOR I=LBOUND(A) TO UBOUND(A)
190 LET A(I)=RND(98)+1
200 NEXT
210 END DEF
220 DEF WRITE(REF A)
230 FOR I=LBOUND(A) TO UBOUND(A)
240 PRINT A(I);
250 NEXT
260 PRINT
270 END DEF
280 DEF COCKTAILSORT(REF A)
290 LET ST=LBOUND(A)+1:LET EN=UBOUND(A):LET D,CH=1
300 DO
310 FOR J=ST TO EN STEP D
320 IF A(J-1)>A(J) THEN LET T=A(J-1):LET A(J-1)=A(J):LET A(J)=T:LET CH=J
330 NEXT
340 LET EN=ST:LET ST=CH-D:LET D=-1*D
350 LOOP UNTIL EN*D<ST*D
360 END DEFJ
bigToLeft=: (([ (>. , <.) {.@]) , }.@])/
smallToLeft=: (([ (<. , >.) {.@]) , }.@])/
cocktailSort=: |. @: (|. @: smallToLeft @: |. @: bigToLeft ^:_)
Test run:
?. 10 $ 10
4 6 8 6 5 8 6 6 6 9
cocktailSort ?. 10 $ 10
4 5 6 6 6 6 6 8 8 9
As is usual with J, /:~ is the preferred method of sorting in practice.
Java
This algorithm sorts in place. Call it with a copy of the array to preserve the unsorted order.
public static void cocktailSort( int[] A ){
boolean swapped;
do {
swapped = false;
for (int i =0; i<= A.length - 2;i++) {
if (A[ i ] > A[ i + 1 ]) {
//test whether the two elements are in the wrong order
int temp = A[i];
A[i] = A[i+1];
A[i+1]=temp;
swapped = true;
}
}
if (!swapped) {
//we can exit the outer loop here if no swaps occurred.
break;
}
swapped = false;
for (int i= A.length - 2;i>=0;i--) {
if (A[ i ] > A[ i + 1 ]) {
int temp = A[i];
A[i] = A[i+1];
A[i+1]=temp;
swapped = true;
}
}
//if no elements have been swapped, then the list is sorted
} while (swapped);
}
JavaScript
// Node 5.4.1 tested implementation (ES6)
"use strict";
let arr = [4, 9, 0, 3, 1, 5];
let isSorted = true;
while (isSorted){
for (let i = 0; i< arr.length - 1;i++){
if (arr[i] > arr[i + 1])
{
let temp = arr[i];
arr[i] = arr[i + 1];
arr[i+1] = temp;
isSorted = true;
}
}
if (!isSorted)
break;
isSorted = false;
for (let j = arr.length - 1; j > 0; j--){
if (arr[j-1] > arr[j])
{
let temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
isSorted = true;
}
}
}
console.log(arr);
}
- Output:
[0, 1, 3, 4, 5, 9]
jq
# In case your jq does not have "until" defined:
def until(cond; next):
def _until:
if cond then . else (next|_until) end;
_until;def cocktailSort:
def swap(i;j): .[i] as $t | .[i] = .[j] | .[j] = $t;
def shake(stream):
reduce stream as $i
(.[0]=false;
.[1] as $A
| if $A[ $i ] > $A[ $i+1 ] then
[true, ($A|swap( $i; $i+1 ))]
else .
end);
(length - 2) as $lm2
# state: [swapped, A]
| [true, .]
| until( .[0]|not;
shake(range(0; $lm2 + 1))
| if .[0] then
# for each i in length( A ) - 2 down to 0
shake( $lm2 - range(0; $lm2 + 1))
else .
end )
| .[1];Tests:
def verify: if cocktailSort == sort then empty else . end;
([],
[1],
[1,1],
[3, 14],
[33, 14],
[3, 14, 1, 5, 9, 2, 6, 3],
[23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4],
[88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1],
[1.5, -1.5],
["cocktail", ["sort"], null, {}]
) | verify- Output:
$ jq -n -c -f cocktail_sort.jq
$
Julia
function cocktailsort(a::Vector)
b = copy(a)
isordered = false
lo, hi = 1, length(b)
while !isordered && hi > lo
isordered = true
for i in lo+1:hi
if b[i] < b[i-1]
b[i-1], b[i] = b[i], b[i-1]
isordered = false
end
end
hi -= 1
if isordered || hi ≤ lo break end
for i in hi:-1:lo+1
if b[i-1] > b[i]
b[i-1], b[i] = b[i], b[i-1]
isordered = false
end
end
lo += 1
end
return b
end
v = rand(-10:10, 10)
println("# unordered: $v\n -> ordered: ", cocktailsort(v))
- Output:
# unordered: [6, -9, 5, -10, 2, 4, 6, -6, -3, -8] -> ordered: [-10, -9, -8, -6, -3, 2, 4, 5, 6, 6]
Kotlin
// version 1.1.0
fun cocktailSort(a: IntArray) {
fun swap(i: Int, j: Int) {
val temp = a[i]
a[i] = a[j]
a[j] = temp
}
do {
var swapped = false
for (i in 0 until a.size - 1)
if (a[i] > a[i + 1]) {
swap(i, i + 1)
swapped = true
}
if (!swapped) break
swapped = false
for (i in a.size - 2 downTo 0)
if (a[i] > a[i + 1]) {
swap(i, i + 1)
swapped = true
}
}
while (swapped)
}
fun main(args: Array<String>) {
val aa = arrayOf(
intArrayOf(100, 2, 56, 200, -52, 3, 99, 33, 177, -199),
intArrayOf(4, 65, 2, -31, 0, 99, 2, 83, 782, 1),
intArrayOf(62, 83, 18, 53, 7, 17, 95, 86, 47, 69, 25, 28)
)
for (a in aa) {
cocktailSort(a)
println(a.joinToString(", "))
}
}
- Output:
-199, -52, 2, 3, 33, 56, 99, 100, 177, 200 -31, 0, 1, 2, 2, 4, 65, 83, 99, 782 7, 17, 18, 25, 28, 47, 53, 62, 69, 83, 86, 95
Lua
function cocktailSort( A )
local swapped
repeat
swapped = false
for i = 1, #A - 1 do
if A[ i ] > A[ i+1 ] then
A[ i ], A[ i+1 ] = A[ i+1 ] ,A[i]
swapped=true
end
end
if swapped == false then
break -- repeatd loop;
end
for i = #A - 1,1,-1 do
if A[ i ] > A[ i+1 ] then
A[ i ], A[ i+1 ] = A[ i+1 ] , A[ i ]
swapped=true
end
end
until swapped==false
end
- Example:
list = { 5, 6, 1, 2, 9, 14, 2, 15, 6, 7, 8, 97 }
cocktailSort(list)
for i=1,#list do
print(list[i]j)
end
M2000 Interpreter
Module cocktailSort {
k=(3,2,1)
print k
cocktailSort(k)
print k
k=("c","b","a")
print k
cocktailSortString(k)
print k
Dim a(5)
a(0)=1,2,5,6,3
print a()
cocktailSort(a())
print a()
End
Sub cocktailSort(a)
\\ this is like Link a to a() but using new for a() - shadow any a()
push &a : read new &a()
local swapped, lenA2=len(a)-2
do
for i=0 to lenA2
if a(i) > a(i+1) then swap a(i), a(i+1): swapped = true
next
if swapped then
swapped~
for i=lenA2 to 0
if a(i) > a(i+1) then swap a(i), a(i+1): swapped = true
next
end if
until not swapped
End Sub
Sub cocktailSortString(a)
push &a : read new &a$()
local swapped, lenA2=len(a)-2
do
for i=0 to lenA2
if a$(i) > a$(i+1) then
swap a$(i), a$(i+1)
swapped = true
end if
next
if swapped then
swapped~
for i=lenA2 to 0
if a$(i) > a$(i+1) then
swap a$(i), a$(i+1)
swapped = true
end if
next
end if
until not swapped
End Sub
}
cocktailSort- Output:
3 2 1 1 2 3 c b a a b c 1 2 5 6 3 1 2 3 5 6
Maple
arr := Array([17,3,72,0,36,2,3,8,40,0]):
len := numelems(arr):
swap := proc(arr, a, b)
local temp := arr[a]:
arr[a] := arr[b]:
arr[b] := temp:
end proc:
while(true) do
swapped := false:
for i to len-1 do
if arr[i] > arr[i+1] then:
swap(arr, i, i+1):
swapped := true:
end if:
end do:
if (not swapped) then break: end if:
swapped := false:
for j from len-1 to 1 by -1 do
if arr[j] > arr[j+1] then
swap(arr,j,j+1):
swapped := true:
end if:
end do:
if (not swapped) then break: end if:
end do:
arr;- Out:
[0,0,2,3,3,8,17,36,40,72]
Mathematica /Wolfram Language
cocktailSort[A_List] := Module[ { swapped = True },
While[ swapped == True,
swapped=False;
For[ i = 1, i< Length[A]-1,i++,
If[ A[[i]] > A[[i+1]], A[[i;;i+1]] = A[[i+1;;i;;-1]]; swapped=True;]
];
If[swapped == False, Break[]];
swapped=False;
For [ i= Length[A]-1, i > 0, i--,
If[ A[[i]] > A[[i+1]], A[[i;;i+1]] = A[[i+1;;i;;-1]]; swapped = True;]
]]]
- Example:
cocktailSort[{2,1,5,3,6}]
->{1,2,3,5,6}
MATLAB / Octave
function list = cocktailSort(list)
%We have to do this because the do...while loop doesn't exist in MATLAB
swapped = true;
while swapped
%Bubble sort down the list
swapped = false;
for i = (1:numel(list)-1)
if( list(i) > list(i+1) )
list([i i+1]) = list([i+1 i]); %swap
swapped = true;
end
end
if ~swapped
break
end
%Bubble sort up the list
swapped = false;
for i = (numel(list)-1:-1:1)
if( list(i) > list(i+1) )
list([i i+1]) = list([i+1 i]); %swap
swapped = true;
end %if
end %for
end %while
end %cocktail sort
- Sample usage:
cocktailSort([6 3 7 8 5 1 2 4 9])
ans =
1 2 3 4 5 6 7 8 9
MAXScript
fn cocktailSort arr =
(
local swapped = true
while swapped do
(
swapped = false
for i in 1 to (arr.count-1) do
(
if arr[i] > arr[i+1] then
(
swap arr[i] arr[i+1]
swapped = true
)
)
if not swapped then exit
for i in (arr.count-1) to 1 by -1 do
(
if arr[i] > arr[i+1] then
(
swap arr[i] arr[i+1]
swapped = true
)
)
)
return arr
)NetRexx
/* NetRexx */
options replace format comments java crossref savelog symbols binary
placesList = [String -
"UK London", "US New York" -
, "US Boston", "US Washington" -
, "UK Washington", "US Birmingham" -
, "UK Birmingham", "UK Boston" -
]
sortedList = cocktailSort(String[] Arrays.copyOf(placesList, placesList.length))
lists = [placesList, sortedList]
loop ln = 0 to lists.length - 1
cl = lists[ln]
loop ct = 0 to cl.length - 1
say cl[ct]
end ct
say
end ln
return
method cocktailSort(A = String[]) public constant binary returns String[]
Alength = A.length
swapped = isFalse
loop label swapped until \swapped
swapped = isFalse
loop i_ = 0 to Alength - 2
if A[i_].compareTo(A[i_ + 1]) > 0 then do
swap = A[i_ + 1]
A[i_ + 1] = A[i_]
A[i_] = swap
swapped = isTrue
end
end i_
if \swapped then do
leave swapped
end
swapped = isFalse
loop i_ = Alength - 2 to 0 by -1
if A[i_].compareTo(A[i_ + 1]) > 0 then do
swap = A[i_ + 1]
A[i_ + 1] = A[i_]
A[i_] = swap
swapped = isTrue
end
end i_
end swapped
return A
method isTrue public constant binary returns boolean
return 1 == 1
method isFalse public constant binary returns boolean
return \isTrue
- Output:
UK London US New York US Boston US Washington UK Washington US Birmingham UK Birmingham UK Boston UK Birmingham UK Boston UK London UK Washington US Birmingham US Boston US New York US Washington
Nim
template trySwap(): untyped =
if a[i] < a[i-1]:
swap a[i], a[i-1]
t = false
proc cocktailSort[T](a: var openarray[T]) =
var t = false
var l = a.len
while not t:
t = true
for i in 1 ..< l: trySwap
if t: break
for i in countdown(l-1, 1): trySwap
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
cocktailSort a
echo a
- Output:
@[-31, 0, 2, 2, 4, 65, 83, 99, 782]
Objeck
bundle Default {
class Cocktail {
function : Main(args : String[]) ~ Nil {
values := [5, -1, 101, -4, 0, 1, 8, 6, 2, 3 ];
CocktailSort(values);
each(i : values) {
values[i]->PrintLine();
};
}
function : CocktailSort(a : Int[]) ~ Nil {
swapped : Bool;
do {
swapped := false;
continue := true;
for (i := 0; i <= a->Size() - 2 & continue; i += 1;) {
if(a[i] > a[i + 1]) {
temp := a[i];
a[i] := a[i+1];
a[i+1] := temp;
swapped := true;
};
};
if(swapped <> true) {
continue := false;
};
swapped := false;
for(i := a->Size() - 2; i >= 0; i -= 1;){
if(a[i] > a[i + 1]) {
temp := a[i];
a[i] := a[i+1];
a[i + 1] := temp;
swapped := true;
};
};
}
while(swapped);
}
}
}OCaml
let swap a i j =
let tmp = a.(i) in
a.(i) <- a.(j);
a.(j) <- tmp;
;;
let cocktail_sort a =
let begin_ = ref(-1)
and end_ = ref(Array.length a - 2) in
let swapped = ref true in
try while !swapped do
swapped := false;
incr begin_;
for i = !begin_ to !end_ do
if a.(i) > a.(i+1) then begin
swap a (i) (i+1);
swapped := true;
end;
done;
if !swapped = false then raise Exit;
swapped := false;
decr end_;
for i = !end_ downto !begin_ do
if a.(i) > a.(i+1) then begin
swap a (i) (i+1);
swapped := true
end;
done;
done with Exit -> ()
;;
let () =
let a = [| 3; 7; 4; 9; 6; 1; 8; 5; 2; |] in
cocktail_sort a;
Array.iter (Printf.printf " %d") a;
print_newline();
;;
- Output:
1 2 3 4 5 6 7 8 9
Octave
function sl = cocktailsort(l)
swapped = true;
while(swapped)
swapped = false;
for i = 1:(length(l)-1)
if ( l(i) > l(i+1) )
t = l(i);
l(i) = l(i+1);
l(i+1) = t;
swapped = true;
endif
endfor
if ( !swapped )
break;
endif
swapped = false;
for i = (length(l)-1):-1:1
if ( l(i) > l(i+1) )
t = l(i);
l(i) = l(i+1);
l(i+1) = t;
swapped = true;
endif
endfor
endwhile
sl = l;
endfunction
- Example:
s = cocktailsort([5, -1, 101, -4, 0, \
1, 8, 6, 2, 3 ]);
disp(s);
ooRexx
/* Rexx */
placesList = .array~of( -
"UK London", "US New York" , "US Boston", "US Washington" -
, "UK Washington", "US Birmingham" , "UK Birmingham", "UK Boston" -
)
sortedList = cocktailSort(placesList~allItems())
lists = .array~of(placesList, sortedList)
loop ln = 1 to lists~items()
cl = lists[ln]
loop ct = 1 to cl~items()
say cl[ct]
end ct
say
end ln
return
exit
::routine cocktailSort
use arg A
Alength = A~items()
swapped = .false
loop label swaps until \swapped
swapped = .false
loop i_ = 1 to Alength - 1
if A[i_] > A[i_ + 1] then do
swap = A[i_ + 1]
A[i_ + 1] = A[i_]
A[i_] = swap
swapped = .true
end
end i_
if \swapped then do
leave swaps
end
swapped = .false
loop i_ = Alength - 1 to 1 by -1
if A[i_] > A[i_ + 1] then do
swap = A[i_ + 1]
A[i_ + 1] = A[i_]
A[i_] = swap
swapped = .true
end
end i_
end swaps
return A
- Output:
UK London US New York US Boston US Washington UK Washington US Birmingham UK Birmingham UK Boston UK Birmingham UK Boston UK London UK Washington US Birmingham US Boston US New York US Washington
Oz
declare
proc {CocktailSort Arr}
proc {Swap I J}
Arr.J := (Arr.I := Arr.J) %% assignment returns the old value
end
IsSorted = {NewCell false}
Up = {List.number {Array.low Arr} {Array.high Arr}-1 1}
Down = {Reverse Up}
in
for until:@IsSorted break:Break do
for Range in [Up Down] do
IsSorted := true
for I in Range do
if Arr.I > Arr.(I+1) then
IsSorted := false
{Swap I I+1}
end
end
if @IsSorted then {Break} end
end
end
end
Arr = {Tuple.toArray unit(10 9 8 7 6 5 4 3 2 1)}
in
{CocktailSort Arr}
{Inspect Arr}PARI/GP
cocktailSort(v)={
while(1,
my(done=1);
for(i=2,#v,
if(v[i-1]>v[i],
my(t=v[i-1]);
v[i-1]=v[i];
v[i]=t;
done=0
)
);
if(done, return(v));
done=1;
forstep(i=#v,2,-1,
if(v[i-1]>v[i],
my(t=v[i-1]);
v[i-1]=v[i];
v[i]=t;
done=0
)
);
if(done, return(v))
)
};Pascal
See Delphi
Perl
use strict;
use warnings;
use feature 'say';
sub cocktail_sort {
my @a = @_;
while (1) {
my $swapped_forward = 0;
for my $i (0..$#a-1) {
if ($a[$i] gt $a[$i+1]) {
@a[$i, $i+1] = @a[$i+1, $i];
$swapped_forward = 1;
}
}
last if not $swapped_forward;
my $swapped_backward = 0;
for my $i (reverse 0..$#a-1) {
if ($a[$i] gt $a[$i+1]) {
@a[$i, $i+1] = @a[$i+1, $i];
$swapped_backward = 1;
}
}
last if not $swapped_backward;
}
@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
with javascript_semantics function cocktail_sort(sequence s) s = deep_copy(s) integer swapped = 1, f = 1, t = length(s)-1, d = 1 while swapped do swapped = 0 for i=f to t by d do object si = s[i], sn = s[i+1] if si>sn then s[i] = sn s[i+1] = si swapped = 1 end if end for -- swap to and from, and flip direction. -- additionally, we can reduce one element to be -- examined, depending on which way we just went. {f,t,d} = {t-d,f,-d} end while return s end function constant s = sq_rand(repeat(1000,10)) printf(1,"original: %V\n",{s}) printf(1," sorted: %V\n",{cocktail_sort(s)})
- Output:
original: {157,371,822,436,89,506,46,791,22,147}
sorted: {22,46,89,147,157,371,436,506,791,822}
PHP
function cocktailSort($arr){
if (is_string($arr)) $arr = str_split(preg_replace('/\s+/','',$arr));
do{
$swapped = false;
for($i=0;$i<count($arr);$i++){
if(isset($arr[$i+1])){
if($arr[$i] > $arr[$i+1]){
list($arr[$i], $arr[$i+1]) = array($arr[$i+1], $arr[$i]);
$swapped = true;
}
}
}
if ($swapped == false) break;
$swapped = false;
for($i=count($arr)-1;$i>=0;$i--){
if(isset($arr[$i-1])){
if($arr[$i] < $arr[$i-1]) {
list($arr[$i],$arr[$i-1]) = array($arr[$i-1],$arr[$i]);
$swapped = true;
}
}
}
}while($swapped);
return $arr;
}
$arr = array(5, 1, 7, 3, 6, 4, 2);
$arr2 = array("John", "Kate", "Alice", "Joe", "Jane");
$strg = "big fjords vex quick waltz nymph";
$arr = cocktailSort($arr);
$arr2 = cocktailSort($arr2);
$strg = cocktailSort($strg);
echo implode(',',$arr) . '<br>';
echo implode(',',$arr2) . '<br>';
echo implode('',$strg) . '<br>';
- Output:
1,2,3,4,5,6,7 Alice,Jane,Joe,John,Kate abcdefghiijklmnopqrstuvwxyz
PicoLisp
(de cocktailSort (Lst)
(use (Swapped L)
(loop
(off Swapped)
(setq L Lst)
(while (cdr L)
(when (> (car L) (cadr L))
(xchg L (cdr L))
(on Swapped) )
(pop 'L) )
(NIL Swapped Lst)
(off Swapped)
(loop
(setq L (prior L Lst)) # Not recommended (inefficient)
(when (> (car L) (cadr L))
(xchg L (cdr L))
(on Swapped) )
(T (== Lst L)) )
(NIL Swapped Lst) ) ) )- Output:
: (cocktailSort (make (do 9 (link (rand 1 999))))) -> (1 167 183 282 524 556 638 891 902) : (cocktailSort (make (do 9 (link (rand 1 999))))) -> (82 120 160 168 205 226 408 708 719)
PL/I
cocktail: procedure (A);
declare A(*) fixed;
declare t fixed;
declare stable bit (1);
declare (i, n) fixed binary (31);
n = hbound(A,1);
do until (stable);
stable = '1'b;
do i = 1 to n-1, n-1 to 1 by -1;
if A(i) > A(i+1) then
do; stable = '0'b; /* still unsorted, so set false. */
t = A(i); A(i) = A(i+1); A(i+1) = t;
end;
end;
end;
end cocktail;PowerShell
Based on the entry for PowerShell in Bubble Sort
function CocktailSort ($a) {
$l = $a.Length
$m = 0
if( $l -gt 1 )
{
$hasChanged = $true
:outer while ($hasChanged) {
$hasChanged = $false
$l--
for ($i = $m; $i -lt $l; $i++) {
if ($a[$i] -gt $a[$i+1]) {
$a[$i], $a[$i+1] = $a[$i+1], $a[$i]
$hasChanged = $true
}
}
if(-not $hasChanged) {
break outer
}
$hasChanged = $false
for ($i = $l; $i -gt $m; $i--) {
if ($a[$i-1] -gt $a[$i]) {
$a[$i-1], $a[$i] = $a[$i], $a[$i-1]
$hasChanged = $true
}
}
$m++
}
}
$a
}
$l = 10; CocktailSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( -( $l - 1 ), $l - 1 ) } )
Prolog
ctail(_, [], Rev, Rev, sorted) :- write(Rev), nl.
ctail(fwrd, [A,B|T], In, Rev, unsorted) :- A > B, !,
ctail(fwrd, [B,A|T], In, Rev, _).
ctail(bkwd, [A,B|T], In, Rev, unsorted) :- A < B, !,
ctail(bkwd, [B,A|T], In, Rev, _).
ctail(D,[A|T], In, Rev, Ch) :- !, ctail(D, T, [A|In], Rev, Ch).
cocktail([], []).
cocktail(In, [Min|Out]) :-
ctail(fwrd, In, [], [Max|Rev], SFlag),
( SFlag=sorted->reverse([Max|Rev], [Min|Out]);
(ctail(bkwd, Rev, [Max], [Min|Tmp], SortFlag),
(SortFlag=sorted->Out=Tmp; !, cocktail(Tmp, Out)))).
test :- In = [8,9,1,3,4,2,6,5,4],
writef(' input=%w\n', [In]),
cocktail(In, R),
writef('-> %w\n', [R]).
- Example:
?- test. input=[8,9,1,3,4,2,6,5,4] [9,4,5,6,2,4,3,1,8] [1,8,2,3,4,4,6,5,9] [9,8,5,6,4,4,3,2] [2,3,4,4,5,6,8,9] [9,8,6,5,4,4,3] -> [1,2,3,4,4,5,6,8,9]
PureBasic
The following approach improves on the method in the pseudo-code by not examining indexes on either end of the array that have already been sorted by reducing the index range on each subsequent pass.
;sorts an array of integers
Procedure cocktailSort(Array a(1))
Protected index, hasChanged, low, high
low = 0
high = ArraySize(a()) - 1
Repeat
hasChanged = #False
For index = low To high
If a(index) > a(index + 1)
Swap a(index), a(index + 1)
hasChanged = #True
EndIf
Next
high - 1
If hasChanged = #False
Break ;we can exit the outer loop here if no changes were made
EndIf
hasChanged = #False
For index = high To low Step -1
If a(index) > a(index + 1)
Swap a(index), a(index + 1)
hasChanged = #True
EndIf
Next
low + 1
Until hasChanged = #False ;if no elements have been changed, then the array is sorted
EndProcedure
Python
This implementation takes advantage of the identical processing of the two for loops and that a range is a first-class object in Python.
def cocktailSort(A):
up = range(len(A)-1)
while True:
for indices in (up, reversed(up)):
swapped = False
for i in indices:
if A[i] > A[i+1]:
A[i], A[i+1] = A[i+1], A[i]
swapped = True
if not swapped:
return
- Usage:
test1 = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
cocktailSort(test1)
print test1
#>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
test2=list('big fjords vex quick waltz nymph')
cocktailSort(test2)
print ''.join(test2)
#>>> abcdefghiijklmnopqrstuvwxyz
This implementation is clearer in structure to it's bubblesort origins while also being ever so slightly faster, in python 3.5.2 at least.
def cocktail(a):
for i in range(len(a)//2):
swap = False
for j in range(1+i, len(a)-i):
if a[j] < a[j-1]:
a[j], a[j-1] = a[j-1], a[j]
swap = True
if not swap:
break
swap = False
for j in range(len(a)-i-1, i, -1):
if a[j] < a[j-1]:
a[j], a[j-1] = a[j-1], a[j]
swap = True
if not swap:
break
Quackery
[ 2dup 1+ peek dip peek > ] is compare ( [ n --> b )
[ dup 1+ unrot
2dup peek
dip
[ 2dup 1+ peek
unrot poke
swap ]
unrot poke ] is exchange ( [ n --> [ )
[ [ 0 swap
dup size 1 - times
[ dup i^ compare if
[ i^ exchange
dip 1+ ] ]
over while
dup size 1 - times
[ dup i compare if
[ i exchange
dip 1+ ] ]
over while
nip again ]
nip ] is cocktail ( [ --> [ )
randomise
[] 20 times [ 89 random 10 + join ]
dup echo cr
cocktail echo- Output:
[ 46 42 73 92 95 19 27 52 33 12 60 70 34 45 93 15 64 41 12 55 ] [ 12 12 15 19 27 33 34 41 42 45 46 52 55 60 64 70 73 92 93 95 ]
R
The previously solution missed out on a cool R trick for swapping items. As R is 1-indexed, we have made some minor adjustments to the given pseudo-code. Otherwise, we have aimed to be faithful to it.
cocktailSort <- function(A)
{
repeat
{
swapped <- FALSE
for(i in seq_len(length(A) - 1))
{
if(A[i] > A[i + 1])
{
A[c(i, i + 1)] <- A[c(i + 1, i)]#The cool trick mentioned above.
swapped <- TRUE
}
}
if(!swapped) break
swapped <- FALSE
for(i in (length(A)-1):1)
{
if(A[i] > A[i + 1])
{
A[c(i, i + 1)] <- A[c(i + 1, i)]
swapped <- TRUE
}
}
if(!swapped) break
}
A
}
#Examples taken from the Haxe solution.
ints <- c(1, 10, 2, 5, -1, 5, -19, 4, 23, 0)
numerics <- c(1, -3.2, 5.2, 10.8, -5.7, 7.3, 3.5, 0, -4.1, -9.5)
strings <- c("We", "hold", "these", "truths", "to", "be", "self-evident", "that", "all", "men", "are", "created", "equal")
- Output:
> cocktailSort(ints) [1] -19 -1 0 1 2 4 5 5 10 23 > cocktailSort(numerics) [1] -9.5 -5.7 -4.1 -3.2 0.0 1.0 3.5 5.2 7.3 10.8 > cocktailSort(strings) [1] "all" "are" "be" "created" "equal" "hold" "men" [8] "self-evident" "that" "these" "to" "truths" "We"
Racket
#lang racket
(require (only-in srfi/43 vector-swap!))
(define (cocktail-sort! xs)
(define (ref i) (vector-ref xs i))
(define (swap i j) (vector-swap! xs i j))
(define len (vector-length xs))
(define (bubble from to delta)
(for/fold ([swaps 0]) ([i (in-range from to delta)])
(cond [(> (ref i) (ref (+ i 1)))
(swap i (+ i 1)) (+ swaps 1)]
[swaps])))
(let loop ()
(cond [(zero? (bubble 0 (- len 2) 1)) xs]
[(zero? (bubble (- len 2) 0 -1)) xs]
[(loop)])))
Raku
(formerly Perl 6)
sub cocktail_sort ( @a ) {
my $range = 0 ..^ @a.end;
loop {
my $swapped_forward = 0;
for $range.list -> $i {
if @a[$i] > @a[$i+1] {
@a[ $i, $i+1 ] .= reverse;
$swapped_forward = 1;
}
}
last if not $swapped_forward;
my $swapped_backward = 0;
for $range.reverse -> $i {
if @a[$i] > @a[$i+1] {
@a[ $i, $i+1 ] .= reverse;
$swapped_backward = 1;
}
}
last if not $swapped_backward;
}
return @a;
}
my @weights = (^50).map: { 100 + ( 1000.rand.Int / 10 ) };
say @weights.sort.Str eq @weights.&cocktail_sort.Str ?? 'ok' !! 'not ok';
REXX
version handles blanks
This REXX version can handle array elements that may contain blanks or spaces.
/*REXX program sorts an array using the cocktail─sort method, A.K.A.: happy hour sort,*/
/* bidirectional bubble sort, */
/* cocktail shaker sort, ripple sort,*/
/* a selection sort variation, */
/* shuffle sort, shuttle sort, or */
/* a bubble sort variation. */
call genItems /*generate some array elements. */
call showItems 'before sort' /*show unsorted array elements. */
say copies('█', 101) /*show a separator line (a fence). */
call cocktailSort /*invoke the cocktail sort subroutine. */
call showItems ' after sort' /*show sorted array elements. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
cocktailSort: procedure expose items.
nn = items.0 - 1 /*items.0: is number of items. */
do until done
done = 1
do j = 1 for nn
jp = j + 1 /* Rexx doesn't allow "items.(j+1)", so use this instead. */
if items.j > items.jp then do
done = 0
temp = items.j
items.j = items.jp
items.jp = temp
end
end /*j*/
if done then leave /*No swaps done? Finished*/
do k = nn for nn by -1
kp = k + 1 /* Rexx doesn't allow "items.(k+1)", so use this instead. */
if items.k > items.kp then do
done = 0
temp = items.k
items.k = items.kp
items.kp = temp
end
end /*k*/
end /*until*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
genitems: procedure expose items.
items.= /*assign a default value for the stem. */
items.1 ='---the 22 card tarot deck (larger deck has 56 additional cards in 4 suits)---'
items.2 ='==========symbol====================pip======================================'
items.3 ='the juggler ◄─── I'
items.4 ='the high priestess [Popess] ◄─── II'
items.5 ='the empress ◄─── III'
items.6 ='the emperor ◄─── IV'
items.7 ='the hierophant [Pope] ◄─── V'
items.8 ='the lovers ◄─── VI'
items.9 ='the chariot ◄─── VII'
items.10='justice ◄─── VIII'
items.11='the hermit ◄─── IX'
items.12='fortune [the wheel of] ◄─── X'
items.13='strength ◄─── XI'
items.14='the hanging man ◄─── XII'
items.15='death [often unlabeled] ◄─── XIII'
items.16='temperance ◄─── XIV'
items.17='the devil ◄─── XV'
items.18='lightning [the tower] ◄─── XVI'
items.19='the stars ◄─── XVII'
items.20='the moon ◄─── XVIII'
items.21='the sun ◄─── XIX'
items.22='judgment ◄─── XX'
items.23='the world ◄─── XXI'
items.24='the fool [often unnumbered] ◄─── XXII'
items.0 =24 /* number of entries in the array. */
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
showitems: procedure expose items.
parse arg phase
width = length(items.0)
do j=1 to items.0 /* items.0 is the number of items in items. */
say 'element' right(j, width) phase || ":" items.j
end /*j*/ /* ↑ */
/* └─────max width of any line number. */
return
- 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: lightning [the tower] ◄─── XVI element 19 before sort: the stars ◄─── XVII element 20 before sort: the moon ◄─── XVIII element 21 before sort: the sun ◄─── XIX element 22 before sort: judgment ◄─── XX element 23 before sort: the world ◄─── XXI element 24 before sort: the fool [often unnumbered] ◄─── XXII █████████████████████████████████████████████████████████████████████████████████████████████████████ 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: judgment ◄─── XX element 6 after sort: justice ◄─── VIII element 7 after sort: lightning [the tower] ◄─── XVI element 8 after sort: strength ◄─── XI element 9 after sort: temperance ◄─── XIV element 10 after sort: the chariot ◄─── VII element 11 after sort: the devil ◄─── XV element 12 after sort: the emperor ◄─── IV element 13 after sort: the empress ◄─── III element 14 after sort: the fool [often unnumbered] ◄─── XXII element 15 after sort: the hanging man ◄─── XII element 16 after sort: the hermit ◄─── IX element 17 after sort: the hierophant [Pope] ◄─── V element 18 after sort: the high priestess [Popess] ◄─── II element 19 after sort: the juggler ◄─── I element 20 after sort: the lovers ◄─── VI element 21 after sort: the moon ◄─── XVIII element 22 after sort: the stars ◄─── XVII element 23 after sort: the sun ◄─── XIX element 24 after sort: the world ◄─── XXI
version handles non-blanks
This faster REXX version can handle array elements that don't contain blanks or spaces by using a simpler swap mechanism. The REXX PARSE instruction separates an input into parts and assigns them to variables, in a single operation. Thus
PARSE VALUE 0 items.j items.jp WITH done items.jp items.j
sets done to 0, items.jp to items.j, and items.j to items.jp, as long as none of the input variables contain any blanks.
cocktailSort2: procedure expose items.
nn = items.0 - 1 /*N: the number of items in items.*/
do until done
done = 1
do j = 1 for nn
jp = j + 1 /* Rexx doesn't allow "items.(j+1)", so use this instead. */
if items.j > items.jp then ,
parse value 0 items.j items.jp with done items.jp items.j /* swap items.j and items.jp, and set done to 0 */
end /*j*/
if done then leave /*Did swaps? Then we're done.*/
do k = nn for nn by -1
kp = k + 1 /* Rexx doesn't allow "items.(k+1)", so use this instead. */
if items.k > items.kp then ,
parse value 0 items.k items.kp with done items.kp items.k /* swap items.k and items.kp, and set done to 0 */
end /*k*/
end /*until*/
return
Ring
aList = [ 5, 6, 1, 2, 9, 14, 2, 15, 6, 7, 8, 97]
flag = 0
cocktailSort(aList)
for i=1 to len(aList)
see "" + aList[i] + " "
next
func cocktailSort A
n = len(A)
while flag = 0
flag = 1
for i = 1 to n-1
if A[i] > A[i+1]
temp = A[i]
A[i] = A[i+1]
A [i+1] = temp
flag = 0
ok
next
endRPL
« DO 1 CF
1 OVER SIZE 1 - FOR h
DUP h DUP 1 + SUB
IF DUP EVAL > THEN
h SWAP REVLIST REPL
1 SF
ELSE DROP END
NEXT
IF 1 FS? THEN
DUP SIZE 1 - 1 FOR h
DUP h DUP 1 + SUB
IF DUP EVAL > THEN
h SWAP REVLIST REPL
1 SF
ELSE DROP END
-1 STEP
END
UNTIL 1 FC? END
» 'COCKTAILSORT' STO
{ 7 6 5 9 8 4 3 1 2 0 } COCKTAILSORT
- Output:
1: { 0 1 2 3 4 5 6 7 8 9 }
This implementation is 40 times slower than the built-in SORT function on an HP-50g.
Ruby
class Array
def cocktailsort!
begin
swapped = false
0.upto(length - 2) do |i|
if self[i] > self[i + 1]
self[i], self[i + 1] = self[i + 1], self[i]
swapped = true
end
end
break unless swapped
swapped = false
(length - 2).downto(0) do |i|
if self[i] > self[i + 1]
self[i], self[i + 1] = self[i + 1], self[i]
swapped = true
end
end
end while swapped
self
end
end
Another way
class Array
def cocktailsort!
start, finish, way = 0, size-1, 1
loop do
swapped = false
start.step(finish-way, way) do |i|
if (self[i] <=> self[i + way]) == way
self[i], self[i + way] = self[i + way], self[i]
swapped = i
end
end
break unless swapped
start, finish, way = swapped, start, -way
end
self
end
end
Test:
ary = [7,6,5,9,8,4,3,1,2,0]
p ary.cocktailsort!
ary = ["John", "Kate", "Zerg", "Alice", "Joe", "Jane"]
p ary.cocktailsort!
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ["Alice", "Jane", "Joe", "John", "Kate", "Zerg"]
Run BASIC
for i = 1 to 100 ' fill array
a(i) = rnd(0) * 100
next i
' ------- sort -------
beg = 2
siz = 100
whatWay = 1
changed = 1
while changed
changed = 0
FOR i = beg TO siz STEP whatWay
IF a(i-1) > a(i) THEN
hold = a(i)
a(i) = a(i-1)
a(i-1) = hold
changed = i
end if
NEXT i
siz = beg
beg = changed - whatWay
whatWay = 0 - whatWay
wend
' ------ print result --------
for i = 1 to 100
print i;" ";a(i)
next i
endRust
fn cocktail_sort<T: PartialOrd>(a: &mut [T]) {
let len = a.len();
loop {
let mut swapped = false;
let mut i = 0;
while i + 1 < len {
if a[i] > a[i + 1] {
a.swap(i, i + 1);
swapped = true;
}
i += 1;
}
if swapped {
swapped = false;
i = len - 1;
while i > 0 {
if a[i - 1] > a[i] {
a.swap(i - 1, i);
swapped = true;
}
i -= 1;
}
}
if !swapped {
break;
}
}
}
fn main() {
let mut v = vec![10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6];
println!("before: {:?}", v);
cocktail_sort(&mut v);
println!("after: {:?}", v);
}
- Output:
before: [10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6] after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Scala
object CocktailSort extends App {
def sort(arr: Array[Int]) = {
var swapped = false
do {
def swap(i: Int) {
val temp = arr(i)
arr(i) = arr(i + 1)
arr(i + 1) = temp
swapped = true
}
swapped = false
for (i <- 0 to (arr.length - 2)) if (arr(i) > arr(i + 1)) swap(i)
if (swapped) {
swapped = false
for (j <- arr.length - 2 to 0 by -1) if (arr(j) > arr(j + 1)) swap(j)
//if no elements have been swapped, then the list is sorted
}
} while (swapped)
arr
}
println(sort(Array(170, 45, 75, -90, -802, 24, 2, 66)).mkString(", "))
}
Scilab
function varargout=cocktailSort(list_in)
swapped = %T;
while swapped
swapped = %F;
for i = [1:length(list_in)-1]
if list_in(i) > list_in(i+1) then
list_in([i i+1])=list_in([i+1 i]);
swapped = %T;
end
end
if ~swapped
break
end
swapped = %F;
for i = [length(list_in)-1:-1:1]
if list_in(i) > list_in(i+1)
list_in([i i+1]) = list_in([i+1 i])
swapped = %T;
end
end
end
varargout=list(list_in)
endfunction
disp(cocktailSort([6 3 7 8 5 1 2 4 9]));
- Output:
1. 2. 3. 4. 5. 6. 7. 8. 9.
Seed7
const proc: cocktailSort (inout array elemType: arr) is func
local
var boolean: swapped is FALSE;
var integer: i is 0;
var elemType: help is elemType.value;
begin
repeat
swapped := FALSE;
for i range 1 to length(arr) - 1 do
if arr[i] > arr[i + 1] then
help := arr[i];
arr[i] := arr[i + 1];
arr[i + 1] := help;
swapped := TRUE;
end if;
end for;
if swapped then
swapped := FALSE;
for i range length(arr) - 1 downto 1 do
if arr[i] > arr[i + 1] then
help := arr[i];
arr[i] := arr[i + 1];
arr[i + 1] := help;
swapped := TRUE;
end if;
end for;
end if;
until not swapped;
end func;Original source: [1]
Sidef
func cocktailsort(a) {
var swapped = false
func cmpsw(i) {
if (a[i] > a[i+1]) {
a[i, i+1] = a[i+1, i]
swapped = true
}
}
var max = a.end
do {
{|i| cmpsw(i) } << ^max
swapped.not! && break
{|i| cmpsw(max-i) } << 1..max
} while (swapped)
return a
}
Test:
var numbers = [7,6,5,9,8,4,3,1,2,0]
say cocktailsort(numbers)
var strs = ["John", "Kate", "Zerg", "Alice", "Joe", "Jane"]
say cocktailsort(strs)
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ['Alice', 'Jane', 'Joe', 'John', 'Kate', 'Zerg']
Slate
s@(Sequence traits) cocktailSort
[ |swapped|
swapped: False.
s size <= 1 ifTrue: [^ s].
[{0 to: s size - 2. s size - 2 downTo: 0}
do: [|:range| range do: [|:index| (s at: index) > (s at: index + 1) ifTrue: [s swap: index with: index + 1. swapped: True]].
swapped ifFalse: [^ s].
swapped: False].
] loop
].- Example:
slate[1]> #( 10 9 8 7 6 0 -5) cocktailSort.
{-5. 0. 6. 7. 8. 9. 10}Smalltalk
OrderedCollection extend [
swap: indexA and: indexB [
|t|
t := self at: indexA.
self at: indexA put: (self at: indexB).
self at: indexB put: t
]
cocktailSort [
|swapped|
[
swapped := false.
1 to: (self size - 1) do: [ :i |
(self at: i) > (self at: (i+1)) ifTrue: [
self swap: i and: (i+1).
swapped := true
]
].
swapped ifFalse: [ ^ self ].
swapped := false.
(self size - 1) to: 1 by: -1 do: [ :i |
(self at: i) > (self at: (i+1)) ifTrue: [
self swap: i and: (i+1).
swapped := true
]
].
swapped
] whileTrue: [ ].
^ self
]
].
- Example:
(#( 10 9 8 7 6 0 -5) asOrderedCollection cocktailSort) printNl.
Swift
extension Collection where Element: Comparable {
public func cocktailSorted() -> [Element] {
var swapped = false
var ret = Array(self)
guard count > 1 else {
return ret
}
repeat {
for i in 0...ret.count-2 where ret[i] > ret[i + 1] {
(ret[i], ret[i + 1]) = (ret[i + 1], ret[i])
swapped = true
}
guard swapped else {
break
}
swapped = false
for i in stride(from: ret.count - 2, through: 0, by: -1) where ret[i] > ret[i + 1] {
(ret[i], ret[i + 1]) = (ret[i + 1], ret[i])
swapped = true
}
} while swapped
return ret
}
}
let arr = (1...10).shuffled()
print("Before: \(arr)")
print("Cocktail sort: \(arr.cocktailSorted())")
- Output:
Before: [5, 4, 7, 10, 9, 8, 1, 6, 2, 3] Cocktail sort: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Tcl
package require Tcl 8.5
package require struct::list
proc cocktailsort {A} {
set len [llength $A]
set swapped true
while {$swapped} {
set swapped false
for {set i 0} {$i < $len - 1} {incr i} {
set j [expr {$i + 1}]
if {[lindex $A $i] > [lindex $A $j]} {
struct::list swap A $i $j
set swapped true
}
}
if { ! $swapped} {
break
}
set swapped false
for {set i [expr {$len - 2}]} {$i >= 0} {incr i -1} {
set j [expr {$i + 1}]
if {[lindex $A $i] > [lindex $A $j]} {
struct::list swap A $i $j
set swapped true
}
}
}
return $A
}
- Example:
puts [cocktailsort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9
uBasic/4tH
PRINT "Cocktail sort:"
n = FUNC (_InitArray)
PROC _ShowArray (n)
PROC _Cocktailsort (n)
PROC _ShowArray (n)
PRINT
END
_Cocktailsort PARAM (1) ' Cocktail sort
LOCAL (2)
b@ = 0
DO WHILE b@ = 0
b@ = 1
FOR c@=1 TO a@-1
IF @(c@) < @(c@-1) THEN PROC _Swap (c@, c@-1) : b@ = 0
NEXT
UNTIL b@
b@ = 1
FOR c@=a@-1 TO 1 STEP -1
IF @(c@) < @(c@-1) THEN PROC _Swap (c@, c@-1) : b@ = 0
NEXT
LOOP
RETURN
_Swap PARAM(2) ' Swap two array elements
PUSH @(a@)
@(a@) = @(b@)
@(b@) = POP()
RETURN
_InitArray ' Init example array
PUSH 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
FOR i = 0 TO 9
@(i) = POP()
NEXT
RETURN (i)
_ShowArray PARAM (1) ' Show array subroutine
FOR i = 0 TO a@-1
PRINT @(i),
NEXT
PRINT
RETURN
Ursala
The same function is used for the traversal in each direction, in one case parameterized by the given predicate and in the other by its negation. Lists are used rather than arrays. The fold combinator (=>) avoids explicit recursion.
#import std
ctsort = ^=+ +^|(==?/~&l+ @r+ ~&x++ @x,^/~&)+ ("p". =><> ~&r?\~&C "p"?lrhPX/~&C ~&rhPlrtPCC)^~/not ~&test program:
#cast %s
test = ctsort(lleq) 'mdfdguldxisgbxjtqkadfkslakwkyioukdledbig'- Output:
'aabbddddddeffgggiiijkkkkklllmoqsstuuwxxy'
Vala
void swap(int[] array, int i1, int i2) {
if (array[i1] == array[i2])
return;
var tmp = array[i1];
array[i1] = array[i2];
array[i2] = tmp;
}
void cocktail_sort(int[] array) {
while(true) {
bool flag = false;
int[] start = {1, array.length - 1};
int[] end = {array.length, 0};
int[] inc = {1, -1};
for (int it = 0; it < 2; ++it) {
flag = true;
for (int i = start[it]; i != end[it]; i += inc[it])
if (array[i - 1] > array[i]) {
swap(array, i - 1, i);
flag = false;
}
}
if (flag) return;
}
}
void main() {
int[] array = {5, -1, 101, -4, 0, 1, 8, 6, 2, 3};
cocktail_sort(array);
foreach (int i in array) {
stdout.printf("%d ", i);
}
}
- Output:
-4 -1 0 1 2 3 5 6 8 101
VBA
Function cocktail_sort(ByVal s As Variant) As Variant
Dim swapped As Boolean
Dim f As Integer, t As Integer, d As Integer, tmp As Integer
swapped = True
f = 1
t = UBound(s) - 1
d = 1
Do While swapped
swapped = 0
For i = f To t Step d
If Val(s(i)) > Val(s(i + 1)) Then
tmp = s(i)
s(i) = s(i + 1)
s(i + 1) = tmp
swapped = True
End If
Next i
'-- swap to and from, and flip direction.
'-- additionally, we can reduce one element to be
'-- examined, depending on which way we just went.
tmp = f
f = t + (d = 1)
t = tmp + (d = -1)
d = -d
Loop
cocktail_sort = s
End Function
Public Sub main()
Dim s(9) As Variant
For i = 0 To 9
s(i) = CStr(Int(1000 * Rnd))
Next i
Debug.Print Join(s, ", ")
Debug.Print Join(cocktail_sort(s), ", ")
End Sub
- Output:
45, 414, 862, 790, 373, 961, 871, 56, 949, 364 45, 56, 364, 373, 414, 790, 862, 871, 949, 961
VBScript
A few of the streets nearby.
- Implementation
function cocktailSort( byval a )
dim swapped
dim i
do
swapped = false
for i = 0 to ubound( a ) - 1
if a(i) > a(i+1) then
swap a(i), a(i+1)
swapped = true
end if
next
if not swapped then exit do
swapped = false
for i = ubound( a ) - 1 to 0 step -1
if a(i) > a( i+1) then
swap a(i), a(i+1)
swapped = true
end if
next
if not swapped then exit do
loop
cocktailSort = a
end function
sub swap( byref a, byref b)
dim tmp
tmp = a
a = b
b = tmp
end sub
- Invocation
dim a
a = array( "portcullis", "redoubt", "palissade", "turret", "collins", "the parapet", "the quarterdeck")
wscript.echo join( a, ", ")
dim b
b = cocktailSort( a )
wscript.echo join( b, ", ")
- Output:
portcullis, redoubt, palissade, turret, collins, the parapet, the quarterdeck collins, palissade, portcullis, redoubt, the parapet, the quarterdeck, turret
V (Vlang)
fn cocktail(mut arr []int) {
input := 'Input'
output := 'Output'
println('${input : -7s}: ${arr.str()}')
for {
mut swapped := false
for i := 0; i < arr.len - 1; i++ {
if arr[i] > arr[i + 1] {
temp := arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = temp
swapped = true
}
}
if !swapped {
break
}
swapped = false
for i := arr.len - 2; i >= 0; i-- {
if arr[i] > arr[i + 1] {
temp := arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = temp
swapped = true
}
}
if !swapped {
break
}
}
println('${output : -7s}: ${arr.str()}')
}
fn main() {
mut arr := [6, 9, 1, 4]
cocktail(mut arr)
arr = [-8, 15, 1, 4, -3, 20]
cocktail(mut arr)
}- Output:
Input : [6, 9, 1, 4] Output : [1, 4, 6, 9] Input : [-8, 15, 1, 4, -3, 20] Output : [-8, -3, 1, 4, 15, 20]
Wren
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
}
}
var a = [170, 45, 75, -90, -802, 24, 2, 66]
System.print("Before: %(a)")
cocktailSort.call(a)
System.print("After : %(a)")
- Output:
Before: [170, 45, 75, -90, -802, 24, 2, 66] After : [-802, -90, 2, 24, 45, 66, 75, 170]
XPL0
code ChOut=8, IntOut=11;
proc CocktailSort(A, L); \Sort array A of length L
int A, L;
int Swapped, I, T;
[loop [Swapped:= false;
for I:= 0 to L-2 do
if A(I) > A(I+1) then \test if elements are in wrong order
[T:= A(I); A(I):= A(I+1); A(I+1):= T; \elements change places
Swapped:= true;
];
if Swapped = false then quit; \exit outer loop if no swaps occurred
Swapped:= false;
for I:= L-2 downto 0 do
if A(I) > A(I+1) then
[T:= A(I); A(I):= A(I+1); A(I+1):= T;
Swapped:= true;
];
\if no elements have been swapped then the list is sorted
if not Swapped then quit;
];
];
int A, I;
[A:= [3, 1, 4, 1, -5, 9, 2, 6, 5, 4];
CocktailSort(A, 10);
for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];
]- Output:
-5 1 1 2 3 4 4 5 6 9
zkl
This has the Wikipedia optimizations.
fcn cocktailSort(a){
swapped,begin,end:=False,-1,a.len() - 2;
do{
swapped,begin=False,begin + 1;
foreach i in ([begin .. end]){
if(a[i]>a[i+1]){ a.swap(i,i+1); swapped=True; }
}
if(not swapped) break;
swapped,end=False,end - 1;
foreach i in ([end..begin,-1]){
if(a[i]>a[i+1]){ a.swap(i,i+1); swapped=True; }
}
}while(swapped);
a
}cocktailSort(List(2,1)).println();
x:=List(5, -1, 101, -4, 0, 1, 8, 6, 2, 3 );
cocktailSort(x).println();
x="the lazy fox jumped over the brown dog".split(" ").copy();
cocktailSort(x).println();- Output:
L(1,2)
L(-4,-1,0,1,2,3,5,6,8,101)
L("brown","dog","fox","jumped","lazy","over","the","the"
ZX Spectrum Basic
its a "cocktail" bubble sort, but the writer called it 'zigzag' since the name was unknown
5000 CLS
5002 LET a$="": FOR f=1 TO 64: LET a$=a$+CHR$ (32+INT (RND*96)): NEXT f
5004 PRINT a$; AT 10,0;"ZigZag BubbleSORT"
5010 LET la=LEN a$
5011 LET i=1: LET u=0
5020 LET d=0: LET p=(u=0)-(u=1)
5021 LET l=(i AND u=0)+(la-i+u AND u=1)
5030 IF u=0 THEN IF a$(l+1)>=a$(l) THEN GO TO 5050
5031 IF u=1 THEN IF a$(l-1)<=a$(l) THEN GO TO 5050
5040 LET d=1
5042 LET t$=a$(l+p)
5043 LET a$(l+p)=a$(l)
5044 LET a$(l)=t$
5050 LET l=l+p
5051 PRINT AT 10,21;a$(l);AT 12,0;a$
5055 IF l<=la-i AND l>=i THEN GO TO 5023
5061 LET i=i+NOT u
5063 LET u=NOT u
5064 IF d AND i<la THEN GO TO 5020
5072 PRINT AT 12,0;a$
9000 STOP
Next is an optimisation by using the margin value's as swop comparative aswell so its swops inside and at the edges from the file
its a " Sticky (edge) Cocktail Sort" By C. Born (freeware)
5000 CLS : PRINT ;"Jumping Zig Zag BubbleSORT"'"aka Sticky Cocktail Sort"
5002 LET a$="": FOR f=1 TO 96: LET a$=a$+CHR$ (48+INT (RND*48)): NEXT f
5004 PRINT 'a$
5010 LET a=LEN a$: LET i=1: LET u=0: LET up=0: LET do=0
5020 LET d=0: LET p=(NOT u)-u: LET l=(i AND NOT u)+(a AND u)
5030 IF NOT u THEN IF a$(l+1)>=a$(l) THEN GO TO 5060
5031 IF u THEN IF a$(l-1)<=a$(l) THEN GO TO 5060
5040 LET w=l+p: GO SUB 5400
5060 IF up THEN IF a<LEN a$ THEN IF a$(l)=a$(a+1) THEN LET w=a: GO SUB 5400: GO SUB 5500
5061 IF do THEN IF i>1 THEN IF a$(l)=a$(i-1) THEN LET w=i: GO SUB 5400: GO SUB 5500
5100 LET l=l+p
5150 PRINT AT 10,0;a$(l);AT 12,0;a$
5151 PRINT AT 21,0;i;a$(i),a;a$(a)
5155 IF NOT u THEN IF l<a THEN GO TO 5030
5156 IF u THEN IF l>i THEN GO TO 5030
5170 LET do=up=1: LET up=1
5261 LET i=i+u: LET a=a-NOT u: LET u=NOT u
5264 IF d AND i<a THEN GO TO 5020
5272 PRINT AT 12,0;a$
5399 STOP
5400 LET d=1: LET t$=a$(w): LET a$(w)=a$(l): LET a$(l)=t$: RETURN
5500 IF a+1<=LEN a$ THEN IF a$(a)=a$(a+1) THEN LET a=a-1: GO TO 5500
5510 IF i-1>=1 THEN IF a$(i)=a$(i-1) THEN LET i=i+1: GO TO 5500
5520 RETURN
9999 CLEAR : SAVE "JZZB" LINE 0
Categories:
- Programming Tasks
- Sorting Algorithms
- Sorting
- WikipediaSourced
- 11l
- 360 Assembly
- 6502 Assembly
- AArch64 Assembly
- Action!
- ActionScript
- Ada
- ALGOL 60
- ALGOL 68
- ALGOL W
- ARM Assembly
- Arturo
- AutoHotkey
- AWK
- BBC BASIC
- C
- C sharp
- C++
- COBOL
- Common Lisp
- D
- Delphi
- E
- EasyLang
- Eiffel
- Elena
- Elixir
- Euphoria
- Factor
- Forth
- Fortran
- FreeBASIC
- Gambas
- Go
- Groovy
- Haskell
- Ksh
- Haxe
- Icon
- Unicon
- Io
- IS-BASIC
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Lua
- M2000 Interpreter
- Maple
- Mathematica
- Wolfram Language
- MATLAB
- Octave
- MAXScript
- NetRexx
- Nim
- Objeck
- OCaml
- OoRexx
- Oz
- PARI/GP
- Pascal
- Perl
- Phix
- PHP
- PicoLisp
- PL/I
- PowerShell
- Prolog
- PureBasic
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Run BASIC
- Rust
- Scala
- Scilab
- Seed7
- Sidef
- Slate
- Smalltalk
- Swift
- Tcl
- Tcllib
- UBasic/4tH
- Ursala
- Vala
- VBA
- VBScript
- V (Vlang)
- Wren
- XPL0
- Zkl
- ZX Spectrum Basic
- GUISS/Omit