Sorting algorithms/Cocktail sort: Difference between revisions
Added XPL0 |
|||
Line 1,723: | Line 1,723: | ||
ary.cocktailsort! |
ary.cocktailsort! |
||
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang> |
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang> |
||
=={{header|Run BASIC}}== |
|||
<lang runbasic>for i = 1 to 100 ' fill array |
|||
a(i) = rnd(0) * 100 |
|||
next i |
|||
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</lang> |
|||
=={{header|Slate}}== |
=={{header|Slate}}== |
Revision as of 08:47, 30 December 2012
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
This page uses content from Wikipedia. The original article was at Cocktail sort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
The cocktail shaker sort is an improvement on the Bubble Sort. The improvement is basically that values "bubble" both directions through the array, because on each iteration the cocktail shaker sort bubble sorts once forwards and once backwards. Pseudocode for the algorithm (from wikipedia):
function cocktailSort( A : list of sortable items ) do swapped := false for each i in 0 to length( A ) - 2 do if A[ i ] > A[ i+1 ] then // test whether the two // elements are in the wrong // order swap( A[ i ], A[ i+1 ] ) // let the two elements // change places swapped := true; if swapped = false then // we can exit the outer loop here if no swaps occurred. break do-while loop; swapped := false for each i in length( A ) - 2 down to 0 do if A[ i ] > A[ i+1 ] then swap( A[ i ], A[ i+1 ] ) swapped := true; while swapped; // if no elements have been swapped, // then the list is sorted
ActionScript
<lang 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;
}</lang>
Ada
<lang 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;</lang>
ALGOL 68
<lang algol68>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)</lang>
- 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. <lang algol68>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))</lang>
- 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%. <lang algol68>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
);</lang>
AutoHotkey
contributed by Laszlo on the ahk forum <lang AutoHotkey>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
}</lang>
AWK
Sort the standard input and print it to standard output <lang awk>{
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] }
}</lang>
BBC BASIC
Sorting an integer array. '%' indicates integer variable in BBC BASIC <lang 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</lang>
C
<lang c>#include <stdio.h>
- define try_swap { if (a[i] < a[i - 1])\
{ t = a[i]; a[i] = a[i - 1]; a[i - 1] = t; t = 0;} }
void cocktailsort(int *a, size_t len) { size_t i; int t = 0; while (!t) { for (i = 1, t = 1; i < len; i++) try_swap; if (t) break; for (i = len - 1, t = 1; i; i--) try_swap; } }
int main() { int x[] = { 5, -1, 101, -4, 0, 1, 8, 6, 2, 3 }; size_t i, len = sizeof(x)/sizeof(x[0]);
cocktailsort(x, len); for (i = 0; i < len; i++) printf("%d\n", x[i]); return 0; }</lang>
C#
<lang csharp>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); }</lang>
COBOL
This is procedure division only. <lang cobol> 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.</lang>
Common Lisp
This version works on lists and vectors alike. The vector implementation is coded directly. The list version uses an intermediate vector. <lang lisp>(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)))))</lang>
D
<lang d>import std.stdio, std.algorithm;
void cocktailSort(Range)(Range data) {
bool swapped = false; do { foreach (i; 0 .. data.length - 1) if (data[i] > data[i + 1]) { swap(data[i], data[i + 1]); swapped = true; } if (!swapped) break; swapped = false; foreach_reverse (i; 0 .. data.length - 1) if (data[i] > data[i + 1]) { swap(data[i], data[i + 1]); swapped = true; } } while(swapped);
}
void main() {
auto array = ["John", "Kate", "Zerg", "Alice", "Joe", "Jane"]; cocktailSort(array); writeln(array);
}</lang>
- Output:
[Alice, Jane, Joe, John, Kate, Zerg]
Delphi
Dynamic array is a 0-based array of variable length
Static array is an arbitrary-based array of fixed length <lang Delphi>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.</lang>
- 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
<lang 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 } } }
}</lang> Note that this solution contains no repeated code to handle the forward and reverse passes.
Euphoria
<lang 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)</lang>
- Output:
{963,398,374,455,53,210,611,285,984,308} {53,210,285,308,374,398,455,611,963,984}
Fortran
<lang fortran>PROGRAM COCKTAIL
IMPLICIT NONE
INTEGER :: intArray(10) = (/ 4, 9, 3, -2, 0, 7, -5, 1, 6, 8 /)
WRITE(*,"(A,10I5)") "Unsorted array:", intArray CALL Cocktail_sort(intArray) WRITE(*,"(A,10I5)") "Sorted array :", intArray
CONTAINS
SUBROUTINE Cocktail_sort(a) INTEGER, INTENT(IN OUT) :: a(:) INTEGER :: i, bottom, top, temp LOGICAL :: swapped bottom = 1 top = SIZE(a) - 1 DO WHILE (bottom < top ) swapped = .FALSE. DO i = bottom, top IF (array(i) > array(i+1)) THEN temp = array(i) array(i) = array(i+1) array(i+1) = temp swapped = .TRUE. END IF END DO IF (.NOT. swapped) EXIT DO i = top, bottom + 1, -1 IF (array(i) < array(i-1)) THEN temp = array(i) array(i) = array(i-1) array(i-1) = temp swapped = .TRUE. END IF END DO IF (.NOT. swapped) EXIT bottom = bottom + 1 top = top - 1 END DO END SUBROUTINE Cocktail_sort
END PROGRAM COCKTAIL</lang>
Go
<lang 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 } }
}</lang>
More generic version that sorts anything that implements sort.Interface
:
<lang go>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 } }
}</lang>
Groovy
Solution: <lang groovy>def makeSwap = { a, i, j = i+1 -> print "."; aj,i = ai,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
}</lang> Test: <lang groovy>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 ])</lang>
- 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
<lang 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</lang>
Io
<lang 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)</lang>
Icon and Unicon
<lang Icon>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</lang>
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)
J
<lang j>bigToLeft=: (([ (>. , <.) {.@]) , }.@])/ smallToLeft=: (([ (<. , >.) {.@]) , }.@])/ cocktailSort=: |. @: (|. @: smallToLeft @: |. @: bigToLeft ^:_)</lang> Test run: <lang j> ?. 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</lang>
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. <lang java>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); }</lang>
Lua
<lang 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</lang>
- Example:
<lang lua>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</lang>
Mathematica
<lang Mathematica>cocktailSort[A_List] := Module[ { swapped = True }, While[ swapped == True,
swapped=False; For[ i = 1, i< Length[A]-1,i++, If[ Ai > Ai+1, Ai;;i+1 = Ai+1;;i;;-1; swapped=True;] ];
If[swapped == False, Break[]]; swapped=False; For [ i= Length[A]-1, i > 0, i--,
If[ Ai > Ai+1, Ai;;i+1 = Ai+1;;i;;-1; swapped = True;] ]]]</lang>
- Example:
cocktailSort[{2,1,5,3,6}] ->{1,2,3,5,6}
MATLAB / Octave
<lang MATLAB>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</lang>
- Sample usage:
<lang MATLAB>cocktailSort([6 3 7 8 5 1 2 4 9])
ans =
1 2 3 4 5 6 7 8 9</lang>
MAXScript
<lang 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
)</lang>
NetRexx
<lang 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</lang>
- 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
Objeck
<lang 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); } }
}</lang>
OCaml
<lang 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();
- </lang>
- Output:
1 2 3 4 5 6 7 8 9
Octave
<lang 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</lang>
- Example:
<lang octave>s = cocktailsort([5, -1, 101, -4, 0, \ 1, 8, 6, 2, 3 ]); disp(s);</lang>
ooRexx
<lang ooRexx>/* Rexx */
placesList = .array~of( -
"UK London", "US New York" , "US Boston", "US Washington" - , "UK Washington", "US Birmingham" , "UK Birmingham", "UK Boston" -
)
sortedList = cocktailSort(placesList~allItems())
lists = .array~of(placesList, sortedList) loop ln = 1 to lists~items()
cl = lists[ln] loop ct = 1 to cl~items() say cl[ct] end ct say end ln
return exit
- routine cocktailSort
use arg A
Alength = A~items() swapped = isFalse() loop label swaps until \swapped swapped = isFalse() 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 = isTrue() end end i_ if \swapped then do leave swaps end swapped = isFalse() 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 = isTrue() end end i_ end swaps
return A
- routine isTrue
return 1 == 1
- routine isFalse
return \isTrue()
</lang>
- 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
<lang 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}</lang>
PARI/GP
<lang parigp>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)) )
};</lang>
Pascal
See Delphi
Perl
<lang perl>use strict; use warnings;
my @B=qw(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); print "@B\n"; my @C=cocktailSort(@B); print "@C\n";
- cocktailSort #####################
sub cocktailSort { #( A : list of sortable items ) defined as:
my @A = @_; my $swapped = 1; while ($swapped == 1) { $swapped = 0; for (my $i=0; $i<($#A-1); $i+=1) {
if ($A[$i] gt $A[$i+1]) { # test whether the two # elements are in the wrong # order
($A[$i+1], $A[$i])=($A[$i], $A[$i+1]); # let the two elements # change places $swapped = 1; } } if ($swapped == 0) { # we can exit the outer loop here if no swaps occurred. print "no more swaps"; } else { $swapped = 0; for (my $i=($#A-1); $i>0 ; $i-=1) {
if($A[$i] gt $A[$i+1]) {
($A[$i+1], $A[$i])=($A[$i], $A[$i+1]); $swapped = 1; } } }
- if no elements have been swapped,
- then the list is sorted
}
return (@A);
- end sub
}</lang>
Perl 6
<lang perl6>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';</lang>
PHP
<lang 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) . '
';
echo implode(',',$arr2) . '
';
echo implode(,$strg) . '
';</lang>
- Output:
1,2,3,4,5,6,7 Alice,Jane,Joe,John,Kate abcdefghiijklmnopqrstuvwxyz
PicoLisp
<lang 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) ) ) )</lang>
- 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
<lang 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;</lang>
PowerShell
Based on the entry for PowerShell in Bubble Sort <lang PowerShell>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 ) } )</lang>
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. <lang PureBasic>;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</lang>
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. <lang 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</lang>
- Usage:
<lang python>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</lang>
R
<lang R>cocktailsort <- function(x) {
lenx <- length(x) repeat { swapped <- FALSE for(i in 1:(lenx-1)) { if(x[i] > x[i+1]) { temp <- x[i] x[i] <- x[i+1] x[i+1] <- temp swapped <- TRUE } } if(!swapped) break swapped <- FALSE for(i in (lenx-1):1) { if(x[i] > x[i+1]) { temp <- x[i] x[i] <- x[i+1] x[i+1] <- temp swapped <- TRUE } } if(!swapped) break } x
}
print(cocktailsort(c(5, -1, 101, -4, 0, 1, 8, 6, 2, 3)))</lang>
REXX
version handles blanks
This REXX version can handle an array that may contain blanks or spaces. <lang rexx>/*REXX program sorts an array using the cocktail-sort method, a.k.a.: */
/* bidirectional bubble sort, */ /* cocktail shaker sort, */ /* a selection sort variation,*/ /* ripple sort, */ /* shuffle sort, */ /* shuttle sort, */ /* happy hour sort, */ /* a bubble sort variation. */
call gen@ /*generate some array elements. */ call show@ 'before sort' /*show unsorted array elements.*/ call cocktailSort highItem /*invoke cocktail sort subroutine*/ call show@ ' after sort' /*show sorted array elements.*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────COCKTAILSORT subroutine─────────────*/ cocktailSort: procedure expose @.; parse arg N /*N=# of items.*/
do until done; done=1
do j=1 for N-1; jp=j+1 if @.j>@.jp then do; done=0; _=@.j; @.j=@.jp; @.jp=_; end end /*j*/
if done then leave /*No swaps done? Then we're done*/
do k=N-1 for N-1 by -1; kp=k+1 if @.k>@.kp then do; done=0; _=@.k; @.k=@.kp; @.kp=_; end end /*k*/
end /*until*/
return /*──────────────────────────────────GEN@ subroutine─────────────────────*/ gen@: @.= /*assign default value for stem. */ @.1 ='---the 22 card tarot deck (larger deck has 56 additional cards in 4 suits)---' @.2 ='==========symbol====================pip======================================' @.3 ='the juggler ◄─── I' @.4 ='the high priestess [Popess] ◄─── II' @.5 ='the empress ◄─── III' @.6 ='the emperor ◄─── IV' @.7 ='the hierophant [Pope] ◄─── V' @.8 ='the lovers ◄─── VI' @.9 ='the chariot ◄─── VII' @.10='justice ◄─── VIII' @.11='the hermit ◄─── IX' @.12='fortune [the wheel of] ◄─── X' @.13='strength ◄─── XI' @.14='the hanging man ◄─── XII' @.15='death [often unlabeled] ◄─── XIII' @.16='temperance ◄─── XIV' @.17='the devil ◄─── XV' @.18='lightning [the tower] ◄─── XVI' @.18='the stars ◄─── XVII' @.20='the moon ◄─── XVIII' @.21='the sun ◄─── XIX' @.22='judgment ◄─── XX' @.23='the world ◄─── XXI' @.24='the fool [often unnumbered] ◄─── XXII'
do i=1 while @.i\==; end /*find how many entries in array.*/
highItem=i-1 /*adjust for DO loop advancement.*/ return /*──────────────────────────────────SHOW@ subroutine────────────────────*/ show@: widthH=length(highItem) /*the maximum width of any line. */
do j=1 for highItem say 'element' right(j,widthH) arg(1)":" @.j end
say copies('─',79) /*show a separator line or fence.*/ return</lang>
- Output:
element 1 before sort: ---the 22 card tarot deck (larger deck has 56 additional cards in 4 suits)--- element 2 before sort: ==========symbol=====================pip===================================== element 3 before sort: the juggler ◄─── I element 4 before sort: the high priestess [Popess] ◄─── II element 5 before sort: the empress ◄─── III element 6 before sort: the emperor ◄─── IV element 7 before sort: the hierophant [Pope] ◄─── V element 8 before sort: the lovers ◄─── VI element 9 before sort: the chariot ◄─── VII element 10 before sort: justice ◄─── VIII element 11 before sort: the hermit ◄─── IX element 12 before sort: fortune [the wheel of] ◄─── X element 13 before sort: strength ◄─── XI element 14 before sort: the hanging man ◄─── XII element 15 before sort: death [often unlabeled] ◄─── XIII element 16 before sort: temperance ◄─── XIV element 17 before sort: the devil ◄─── XV element 18 before sort: the stars ◄─── XVII ──────────────────────────────────────────────────────────────────────────────── element 1 after sort: ---the 22 card tarot deck (larger deck has 56 additional cards in 4 suits)--- element 2 after sort: ==========symbol=====================pip===================================== element 3 after sort: death [often unlabeled] ◄─── XIII element 4 after sort: fortune [the wheel of] ◄─── X element 5 after sort: justice ◄─── VIII element 6 after sort: strength ◄─── XI element 7 after sort: temperance ◄─── XIV element 8 after sort: the chariot ◄─── VII element 9 after sort: the devil ◄─── XV element 10 after sort: the emperor ◄─── IV element 11 after sort: the empress ◄─── III element 12 after sort: the hanging man ◄─── XII element 13 after sort: the hermit ◄─── IX element 14 after sort: the hierophant [Pope] ◄─── V element 15 after sort: the high priestess [Popess] ◄─── II element 16 after sort: the juggler ◄─── I element 17 after sort: the lovers ◄─── VI element 18 after sort: the stars ◄─── XVII ────────────────────────────────────────────────────────────────────────────────
version handles non-blanks
This faster REXX version can handle an array that doen't contain blanks or spaces by using a simplier swap mechanism. <lang rexx>/*──────────────────────────────────COCKTAILSORT2 subroutine────────────*/ cocktailSort2: procedure expose @.; parse arg N /*N=# of items.*/
/*array items may not contain blanks*/ do until done; done=1
do j=1 for N-1; jp=j+1 if @.j>@.jp then parse value 0 @.j @.jp with done @.jp @.j end /*j*/
if done then leave /*No swaps done? Then we're done*/
do k=N-1 for N-1 by -1; kp=k+1 if @.k>@.kp then parse value 0 @.k @.kp with done @.kp @.k end /*k*/
end /*until*/
return</lang>
Ruby
<lang 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 if not 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 ary = [7,6,5,9,8,4,3,1,2,0] ary.cocktailsort!
- => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang>
Run BASIC
<lang runbasic>for i = 1 to 100 ' fill array
a(i) = rnd(0) * 100
next i
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</lang>
Slate
<lang 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
].</lang>
- Example:
<lang slate>slate[1]> #( 10 9 8 7 6 0 -5) cocktailSort. {-5. 0. 6. 7. 8. 9. 10}</lang>
Smalltalk
<lang 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 ]
].</lang>
- Example:
<lang smalltalk>(#( 10 9 8 7 6 0 -5) asOrderedCollection cocktailSort) printNl.</lang>
Tcl
<lang tcl>package require Tcl 8.5 package require struct::list
proc cocktailsort {A} {
set len [llength $A] set swapped true while {$swapped} { set swapped false for {set i 0} {$i < $len - 1} {incr i} { set j [expr {$i + 1}] if {[lindex $A $i] > [lindex $A $j]} { struct::list swap A $i $j set swapped true } } if { ! $swapped} { break } set swapped false for {set i [expr {$len - 2}]} {$i >= 0} {incr i -1} { set j [expr {$i + 1}] if {[lindex $A $i] > [lindex $A $j]} { struct::list swap A $i $j set swapped true } } } return $A
}</lang>
- Example:
<lang tcl>puts [cocktailsort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</lang>
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.
<lang Ursala>#import std
ctsort = ^=+ +^|(==?/~&l+ @r+ ~&x++ @x,^/~&)+ ("p". =><> ~&r?\~&C "p"?lrhPX/~&C ~&rhPlrtPCC)^~/not ~&</lang> test program: <lang Ursala>#cast %s
test = ctsort(lleq) 'mdfdguldxisgbxjtqkadfkslakwkyioukdledbig'</lang>
- Output:
'aabbddddddeffgggiiijkkkkklllmoqsstuuwxxy'
VBScript
A few of the streets nearby.
- Implementation
<lang vb>function cocktailSort( 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</lang>
- Invocation
<lang vb>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, ", ")</lang>
- Output:
portcullis, redoubt, palissade, turret, collins, the parapet, the quarterdeck collins, palissade, portcullis, redoubt, the parapet, the quarterdeck, turret
XPL0
<lang 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, ^ )]; ]</lang>
- Output:
-5 1 1 2 3 4 4 5 6 9
- Programming Tasks
- Sorting Algorithms
- WikipediaSourced
- ActionScript
- Ada
- ALGOL 68
- AutoHotkey
- AWK
- BBC BASIC
- C
- C sharp
- COBOL
- Common Lisp
- D
- Delphi
- E
- Euphoria
- Fortran
- Go
- Groovy
- Haskell
- Io
- Icon
- Unicon
- J
- Java
- Lua
- Mathematica
- MATLAB
- Octave
- MAXScript
- NetRexx
- Objeck
- OCaml
- OoRexx
- Oz
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- PL/I
- PowerShell
- PureBasic
- Python
- R
- REXX
- Ruby
- Run BASIC
- Slate
- Smalltalk
- Tcl
- Tcllib
- Ursala
- VBScript
- XPL0
- GUISS/Omit