Sorting algorithms/Cocktail 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

cocktail sort with shifting bounds

11l

Translation of: Python

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

Translation of: PL/I

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

Works with: as version Raspberry Pi 3B version Buster 64 bits

/* 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

Works with: A60

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

Works with: as version Raspberry Pi

/* 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% ) ) ENDPROC

C

#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

Works with: Fortran version 90 and later

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

procedure main() #: demonstrate various ways to sort a list and string  demosort(cocktailsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty") end procedure cocktailsort(X,op) #: return sorted list  local i,swapped op := sortop(op,X) # select how and what we sort swapped := 1 repeat # translation of pseudo code. Contractions used to eliminate second loop. every (if /swapped then break break else swapped := &null & next) | ( i := 1 to *X-1) | (if /swapped then break break else swapped := &null & next) | ( i := *X-1 to 1 by -1) do if op(X[i+1],X[i]) then X[i+1] :=: X[swapped := i] return X end

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 DEF

J

Generally, this task should be accomplished in J using /:~. Here we take an approach that's more comparable with the other examples on this page.

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

Works with: jq version 1.4

# 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

Works with: Julia version 0.6

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

Translation of: NetRexx

/* 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 f = 1, t = length(s)-1, d = 1  do  bool swapped = false  for i=f to t by d do  object {si,sn} = s[i..i+1]  if si>sn then  s[i..i+1] = {sn,si}  swapped = true  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}  until not swapped  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;

Pluto

Translation of: Wren

local function cocktail_sort(a)  local last = #a  while true do  local swapped = false  for i = 1, last - 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 then return end  swapped = false  if last >= 1 then  for i = last - 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  end  if !swapped then return end  end end local a = {170, 45, 75, -90, -802, 24, 2, 66} print($"Before: \{{a:concat(", ")}}") cocktail_sort(a) print($"After : \{{a:concat(", ")}}")

Output:

Before: {170, 45, 75, -90, -802, 24, 2, 66} After : {-802, -90, 2, 24, 45, 66, 75, 170}

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 end

RPL

Works with: RPL version HP-49C

« 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 end

Rust

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

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

Library: Tcllib (Package: struct::list)

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

Translation of: C

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

Translation of: Phix

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

Translation of: Go

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