Sorting algorithms/Cocktail sort: Difference between revisions

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 [[wp:Cocktail sort|wikipedia]]):

'''function''' ''cocktailSort''( A : list of sortable items )

'''while''' swapped; ''// if no elements have been swapped,''

''// then the list is sorted''

 

=={{header|ActionScript}}==

do {

var swapped:Boolean=false;

} while (swapped);

return input;

 

=={{header|Ada}}==

 

procedure Cocktail_Sort_Test is

Cocktail_Sort(Data);

Put_Line(Data);

 

=={{header|ALGOL 68}}==

PROC swap = (REF DATA a,b)VOID:(

DATA tmp:=a; a:=b; b:=tmp

[32]CHAR data := "big fjords vex quick waltz nymph";

cocktail sort(data);

{{out}}

<pre> abcdefghiijklmnopqrstuvwxyz</pre>

indirectly, thus removing the need to actually swap large chunks of memory

as only addresses are swapped.

PROC swap = (REF DATA a,b)VOID:(

DATA tmp:=a; a:=b; b:=tmp

cocktail sort(ref data);

FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line);

{{out}}<pre> abcdefghiijklmnopqrstuvwxyz

big fjords vex quick waltz nymph</pre>

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%.

FOR offset FROM 0 DO

BOOL swapped := FALSE;

OD;

break do od loop: SKIP

 

=={{header|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.

% As algol W does not allow overloading, we have to have type-specific %

% sorting procedures - this coctail sorts an integer array %

writeData;

end test ;

{{out}}

<pre>

-6 0 2 8 9 9 14 16 23 90

</pre>

 

=={{header|AutoHotkey}}==

contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276379.html#276379 forum]

MsgBox % CocktailSort("xxx")

MsgBox % CocktailSort("3,2,1")

sorted .= "," . array%A_Index%

Return SubStr(sorted,2) ; drop leading comma

 

=={{header|AWK}}==

Sort the standard input and print it to standard output

line[NR] = $0

}

print line[i]

}

 

=={{header|BBC BASIC}}==

Sorting an integer array. '%' indicates integer variable in BBC BASIC

 

Start%=2

UNTIL ( ( End% * Direction% ) < ( Start% * Direction% ) )

 

 

=={{header|C}}==

 

}

}

 

 

return 0;

 

=={{header|C++}}==

#include <iostream>

#include <windows.h>

return 0;

}

 

=== Alternate version ===

Uses C++11. Compile with

g++ -std=c++11 cocktail.cpp

#include <iostream>

#include <iterator>

copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));

std::cout << "\n";

{{out}}

<pre>

-199 -52 2 3 33 56 99 100 177 200

</pre>

 

=={{header|COBOL}}==

This is procedure division only.

C-000.

DISPLAY "SORT STARTING".

 

F-999.

 

=={{header|Common Lisp}}==

This version works on lists and vectors alike. The vector implementation is coded directly. The list version uses an intermediate vector.

(labels ((scan (start step &aux swapped)

(loop for i = start then (+ i step) while (< 0 i len) do

(list (map-into sequence 'identity

(cocktail-sort-vector (coerce sequence 'vector)

 

=={{header|D}}==

module rosettaCode.sortingAlgorithms.cocktailSort;

 

["Alice", "Jane", "Joe", "John", "Kate", "Zerg"]);

}

 

{{out}}

import rosettaCode.sortingAlgorithms.cocktailSort;

 

//generate 10 sorted random numbers in [0 .. 10)

rndGen.take(10).map!(a=>a%10).array.cocktailSort.writeln();

<pre>[2, 2, 3, 4, 5, 5, 7, 7, 7, 8]</pre>

 

 

Static array is an arbitrary-based array of fixed length

 

{$APPTYPE CONSOLE}

Writeln;

Readln;

{{out}}

<pre>

 

=={{header|E}}==

def cocktailSort(array) {

def swapIndexes := 0..(array.size() - 2)

}

}

Note that this solution contains no repeated code to handle the forward and reverse passes.

=={{header|Eiffel}}==

 

class

end

 

Test:

 

class

end

 

{{out}}

<pre>

sorted

1 2 3 5 99

</pre>

 

=={{header|Euphoria}}==

integer swapped, d

object temp

constant s = rand(repeat(1000,10))

? s

{{out}}

<pre>{963,398,374,455,53,210,611,285,984,308}

{53,210,285,308,374,398,455,611,963,984}

</pre>

 

=={{header|Forth}}==

\ e.g. ' < is precedes

: sort ( a n --)

-1 cells +loop

repeat then drop 2r> 2drop

This is an optimized version:

1- cells bounds 1

begin

>r negate >r swap r@ cells + r> r>

until drop drop drop

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

IMPLICIT NONE

 

END SUBROUTINE Cocktail_sort

 

 

=={{header|Go}}==

 

import "fmt"

}

}

More generic version that sorts anything that implements <code>sort.Interface</code>:

 

import (

}

}

 

=={{header|Groovy}}==

Solution:

def checkSwap = { a, i, j = i+1 -> [(a[i] > a[j])].find{ it }.each { makeSwap(a, i, j) } }

}

list

Test:

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 ])

{{out}}

<pre>..............................................................................................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]

 

=={{header|Haskell}}==

cocktailSort l

| not swapped1 = l

| otherwise = swappingPass op (swapped, x1 : l) (x2 : xs)

swappingPass _ (swapped, l) [x] = (swapped, x : l)

 

 

 

 

 

 

 

 

=={{header|Icon}} and {{header|Unicon}}==

demosort(cocktailsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")

end

X[i+1] :=: X[swapped := i]

return X

 

Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| the supporting procedures 'sortop', and 'demosort' in Bubble Sort]].

on string : "qwerty"

with op = &null: "eqrtwy" (0 ms)</pre>

 

=={{header|J}}==

{{eff note|J|/:~}}

smallToLeft=: (([ (<. , >.) {.@]) , }.@])/

Test run:

4 6 8 6 5 8 6 6 6 9

cocktailSort ?. 10 $ 10

As is usual with J, <code>/:~</code> is the preferred method of sorting in practice.

 

This algorithm sorts in place.

Call it with a copy of the array to preserve the unsorted order.

boolean swapped;

do {

//if no elements have been swapped, then the list is sorted

} while (swapped);

 

=={{header|jq}}==

{{ works with|jq|1.4}}

def until(cond; next):

def _until:

if cond then . else (next|_until) end;

def swap(i;j): .[i] as $t | .[i] = .[j] | .[j] = $t;

 

else .

end )

'''Tests:'''

 

([],

[1.5, -1.5],

["cocktail", ["sort"], null, {}]

{{out}}

 

=={{header|Julia}}==

b = copy(a)

isordered = false

while !isordered && hi > lo

isordered = true

for i in lo+1:hi

if b[i] < b[i-1]

isordered = false

end

end

hi -= 1

for i in hi:-1:lo+1

if b[i-1] > b[i]

isordered = false

end

end

 

 

{{out}}

 

 

 

=={{header|Lua}}==

local swapped

repeat

 

until swapped==false

{{out|Example}}

cocktailSort(list)

for i=1,#list do

print(list[i]j)

 

While[ swapped == True,

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

{{out|Example}}

<pre>cocktailSort[{2,1,5,3,6}]

 

=={{header|MATLAB}} / {{header|Octave}}==

%We have to do this because the do...while loop doesn't exist in MATLAB

end %for

end %while

{{out|Sample usage}}

 

ans =

 

 

=={{header|MAXScript}}==

(

local swapped = true

)

return arr

 

=={{header|NetRexx}}==

options replace format comments java crossref savelog symbols binary

 

 

method isFalse public constant binary returns boolean

{{out}}

<pre>

 

=={{header|Nim}}==

if a[i] < a[i-1]:

swap a[i], a[i-1]

while not t:

t = true

if t: break

for i in countdown(l-1, 1): trySwap

var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]

cocktailSort a

{{out}}

<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>

 

=={{header|Objeck}}==

class Cocktail {

function : Main(args : String[]) ~ Nil {

}

}

 

=={{header|OCaml}}==

let tmp = a.(i) in

a.(i) <- a.(j);

Array.iter (Printf.printf " %d") a;

print_newline();

{{out}}

<pre>

 

=={{header|Octave}}==

swapped = true;

while(swapped)

endwhile

sl = l;

{{out|Example}}

1, 8, 6, 2, 3 ]);

 

=={{header|ooRexx}}==

{{Trans|NetRexx}}

 

placesList = .array~of( -

end swaps

 

{{out}}

<pre>

 

=={{header|Oz}}==

proc {CocktailSort Arr}

proc {Swap I J}

in

{CocktailSort Arr}

 

=={{header|PARI/GP}}==

while(1,

my(done=1);

if(done, return(v))

)

=={{header|Pascal}}==

See [[Sorting_algorithms/Cocktail_sort#Delphi | Delphi]]

 

=={{header|Perl}}==

use warnings;

 

my $swapped_forward = 0;

$swapped_forward = 1;

}

last if not $swapped_forward;

 

my $swapped_backward = 0;

$swapped_backward = 1;

}

last if not $swapped_backward;

}

}

 

 

=={{header|PHP}}==

if (is_string($arr)) $arr = str_split(preg_replace('/\s+/','',$arr));

 

echo implode(',',$arr) . '<br>';

echo implode(',',$arr2) . '<br>';

{{out}}

<pre>

 

=={{header|PicoLisp}}==

(use (Swapped L)

(loop

(on Swapped) )

(T (== Lst L)) )

{{out}}

<pre>: (cocktailSort (make (do 9 (link (rand 1 999)))))

 

=={{header|PL/I}}==

declare A(*) fixed;

declare t fixed;

end;

end;

 

=={{header|PowerShell}}==

Based on the entry for PowerShell in [[Bubble Sort]]

$l = $a.Length

$m = 0

}

 

 

=={{header|Prolog}}==

ctail(fwrd, [A,B|T], In, Rev, unsorted) :- A > B, !,

ctail(fwrd, [B,A|T], In, Rev, _).

cocktail(In, R),

writef('-> %w\n', [R]).

{{out|Example}}

<pre>?- test.

=={{header|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.

Procedure cocktailSort(Array a(1))

Protected index, hasChanged, low, high

low + 1

Until hasChanged = #False ;if no elements have been changed, then the array is sorted

 

=={{header|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.

up = range(len(A)-1)

while True:

swapped = True

if not swapped:

{{out|Usage}}

cocktailSort(test1)

print test1

cocktailSort(test2)

print ''.join(test2)

 

=={{header|R}}==

{

{

}

{

}

}

 

 

=={{header|Racket}}==

#lang racket

(require (only-in srfi/43 vector-swap!))

[(zero? (bubble (- len 2) 0 -1)) xs]

[(loop)])))

 

 

 

 

 

 

element 1 before sort: ---the 22 card tarot deck (larger deck has 56 additional cards in 4 suits)---

element 1 after sort: ---the 22 card tarot deck (larger deck has 56 additional cards in 4 suits)---

</pre>

 

===version handles non-blanks===

 

 

 

 

 

=={{header|Ruby}}==

def cocktailsort!

begin

self

end

 

Another way

def cocktailsort!

start, finish, way = 0, size-1, 1

self

end

 

Test:

p ary.cocktailsort!

ary = ["John", "Kate", "Zerg", "Alice", "Joe", "Jane"]

 

{{out}}

 

=={{header|Run BASIC}}==

a(i) = rnd(0) * 100

next i

print i;" ";a(i)

next i

 

=={{header|Seed7}}==

local

var boolean: swapped is FALSE;

end if;

until not swapped;

 

Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#cocktailSort]

 

=={{header|Sidef}}==

func cmpsw(i) {

if (a[i] > a[i+1]) {

}

Test:

 

{{out}}

<pre>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

=={{header|Slate}}==

[ |swapped|

swapped: False.

swapped: False].

] loop

{{out|Example}}

 

=={{header|Smalltalk}}==

{{works with|GNU Smalltalk}}

swap: indexA and: indexB [

|t|

^ self

]

{{out|Example}}

 

=={{header|Tcl}}==

{{tcllib|struct::list}}<!-- convenient element swapping only -->

package require struct::list

 

}

return $A

{{out|Example}}

 

=={{header|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 (<code>=></code>) avoids explicit recursion.

 

test program:

 

{{out}}

<pre>

'aabbddddddeffgggiiijkkkkklllmoqsstuuwxxy'

</pre>

 

=={{header|VBScript}}==

 

;Implementation

dim swapped

dim i

a = b

b = tmp

;Invocation

a = array( "portcullis", "redoubt", "palissade", "turret", "collins", "the parapet", "the quarterdeck")

wscript.echo join( a, ", ")

dim b

b = cocktailSort( a )

{{out}}

<pre>

portcullis, redoubt, palissade, turret, collins, the parapet, the quarterdeck

collins, palissade, portcullis, redoubt, the parapet, the quarterdeck, turret

</pre>

 

=={{header|XPL0}}==

 

proc CocktailSort(A, L); \Sort array A of length L

CocktailSort(A, 10);

for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];

 

{{out}}

=={{header|zkl}}==

This has the Wikipedia optimizations.

swapped,begin,end:=False,-1,a.len() - 2;

do{

}while(swapped);

a

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();

{{out}}

<pre>

</pre>

 

its a "cocktail" bubble sort, but the writer called it 'zigzag' since the name was unknown

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"

5064 IF d AND i<la THEN GO TO 5020

5072 PRINT AT 12,0;a$

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)

5002 LET a$="": FOR f=1 TO 96: LET a$=a$+CHR$ (48+INT (RND*48)): NEXT f

5004 PRINT 'a$

5510 IF i-1>=1 THEN IF a$(i)=a$(i-1) THEN LET i=i+1: GO TO 5500

5520 RETURN

 

{{omit from|GUISS}}