Sorting algorithms/Cocktail sort: Difference between revisions

{{task|Sorting Algorithms}}

{{Sorting Algorithm}}

{{Wikipedia|Cocktail sort}}

 

:*   [https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort_with_shifting_bounds cocktail sort with shifting bounds]

<br><br>

 

=={{header|360 Assembly}}==

{{trans|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.

COCKTSRT CSECT

USING COCKTSRT,R13 base register

YREGS

RI EQU 6 i

{{out}}

<pre>

-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782

</pre>

 

=={{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 60}}==

{{works with|A60}}

comment Sorting algorithms/Cocktail sort - Algol 60;

integer nA;

writetable(1,nA)

end

{{out}}

<pre>

 

=={{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}}==

 

// can be any swap function. This swap is optimized for numbers.

printf("%d ", a[i]);

return 0;

 

'''Output''':

 

 

===Generic version===

This version can be used with arrays of any type, like the standard library function qsort.

#include <stdio.h>

#include <string.h>

print(a, len);

return 0;

 

{{out}}

 

=={{header|C sharp|C#}}==

{

bool swapped;

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

} while (swapped);

 

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

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

 

=={{header|Elena}}==

import system'math;

import system'routines;

swapped := false;

{

if (list[i]>list[i+1])

swapped := false;

{

if (list[i]>list[i+1])

console.printLine("before:", list.asEnumerable());

console.printLine("after :", list.cocktailSort().asEnumerable())

{{out}}

<pre>

 

=={{header|Elixir}}==

def cocktail_sort(list) when is_list(list), do: cocktail_sort(list, [], [])

end

 

 

{{out}}

 

=={{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}

===Pseudocode translation===

This is a faithful translation of the pseudocode given in the task description. It uses lexical variables.

 

:: cocktail-sort! ( seq -- seq' )

] when

] do while

 

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

 

SYMBOL: swapped?

 

: cocktail-sort! ( seq -- seq' )

 

=={{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|FreeBASIC}}==

' compile with: fbc -s console

' for boundry checks on array's compile with: fbc -s console -exx

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>unsorted -2 -4 7 -5 -7 4 2 -1 5 -6 6 1 0 -3 3

=={{header|Gambas}}==

'''[https://gambas-playground.proko.eu/?gist=ee5467e58f0ef649373eed5a2503b988 Click this link to run this code]'''

Dim siCount, siRev, siProcess As Short

Dim bSorting As Boolean

Print

Output:

<pre>

 

=={{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|Haxe}}==

@:generic

public static function sort<T>(arr:Array<T>) {

Sys.println('Sorted Strings: ' + stringArray);

}

 

{{out}}

 

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

 

=={{header|Io}}==

cocktailSortInPlace := method(

start := 0

 

l := list(2, 3, 4, 5, 1)

 

=={{header|IS-BASIC}}==

110 RANDOMIZE

120 NUMERIC ARRAY(5 TO 24)

340 LET EN=ST:LET ST=CH-D:LET D=-1*D

350 LOOP UNTIL EN*D<ST*D

 

=={{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|JavaScript}}==

// Node 5.4.1 tested implementation (ES6)

"use strict";

console.log(arr);

 

 

 

=={{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}}==

{{works with|Julia|0.6}}

 

b = copy(a)

isordered = false

 

v = rand(-10:10, 10)

 

{{out}}

 

=={{header|Kotlin}}==

 

fun cocktailSort(a: IntArray) {

println(a.joinToString(", "))

}

 

{{out}}

 

=={{header|Lua}}==

local swapped

repeat

 

until swapped==false

{{out|Example}}

cocktailSort(list)

for i=1,#list do

print(list[i]j)

 

=={{header|Maple}}==

len := numelems(arr):

swap := proc(arr, a, b)

if (not swapped) then break: end if:

end do:

{{Output|Out}}

<pre>[0,0,2,3,3,8,17,36,40,72]</pre>

 

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}}==

 

=={{header|Perl}}==

use warnings;

 

 

}

 

 

=={{header|Phix}}==

{{out}}

<pre>

</pre>

 

=={{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)

 

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.

for i in range(len(a)//2):

swap = False

swap = True

if not swap:

 

=={{header|R}}==

{

{

}

{

}

}

 

 

=={{header|Racket}}==

#lang racket

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

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

[(loop)])))

 

=={{header|Raku}}==

(formerly Perl 6)

my $range = 0 ..^ @a.end;

loop {

 

my @weights = (^50).map: { 100 + ( 1000.rand.Int / 10 ) };

 

=={{header|REXX}}==

===version handles blanks===

This REXX version can handle array elements that may contain blanks or spaces.

/* bidirectional bubble sort, */

/* cocktail shaker sort, ripple sort,*/

/* shuffle sort, shuttle sort, or */

/* a bubble sort variation. */

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

 

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the internal default inputs:}}

 

(Shown at three-quarter size.)

<pre style="font-size:75%">

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

element 16 before sort: temperance ◄─── XIV

element 17 before sort: the devil ◄─── XV

█████████████████████████████████████████████████████████████████████████████████████████████████████

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

element 3 after sort: death [often unlabeled] ◄─── XIII

element 4 after sort: fortune [the wheel of] ◄─── X

</pre>

 

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

 

=={{header|Ring}}==

aList = [ 5, 6, 1, 2, 9, 14, 2, 15, 6, 7, 8, 97]

flag = 0

next

end

 

=={{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|Rust}}==

let len = a.len();

loop {

cocktail_sort(&mut v);

println!("after: {:?}", v);

 

{{out}}

 

=={{header|Scala}}==

def sort(arr: Array[Int]) = {

var swapped = false

println(sort(Array(170, 45, 75, -90, -802, 24, 2, 66)).mkString(", "))

 

 

=={{header|Scilab}}==

swapped = %T;

while swapped

endfunction

 

{{out}}

<pre> 1. 2. 3. 4. 5. 6. 7. 8. 9.</pre>

 

=={{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}}==

var swapped = false

func cmpsw(i) {

} while (swapped)

return a

Test:

say cocktailsort(numbers)

 

var strs = ["John", "Kate", "Zerg", "Alice", "Joe", "Jane"]

{{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|Swift}}==

 

public func cocktailSorted() -> [Element] {

var swapped = false

 

print("Before: \(arr)")

 

{{out}}

=={{header|Tcl}}==

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

package require struct::list

 

}

return $A

{{out|Example}}

 

=={{header|uBasic/4tH}}==

n = FUNC (_InitArray)

PROC _ShowArray (n)

PRINT

 

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

=={{header|Vala}}==

{{trans|C}}

if (array[i1] == array[i2])

return;

stdout.printf("%d ", i);

}

 

{{out}}

 

=={{header|VBA}}==

Dim swapped As Boolean

Dim f As Integer, t As Integer, d As Integer, tmp As Integer

Debug.Print Join(s, ", ")

Debug.Print Join(cocktail_sort(s), ", ")

<pre>45, 414, 862, 790, 373, 961, 871, 56, 949, 364

45, 56, 364, 373, 414, 790, 862, 871, 949, 961</pre>

 

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

</pre>

 

input := 'Input'

output := 'Output'

arr = [-8, 15, 1, 4, -3, 20]

cocktail(mut arr)

{{out}}

<pre>Input : [6, 9, 1, 4]

=={{header|Wren}}==

{{trans|Go}}

var last = a.count - 1

while (true) {

System.print("Before: %(a)")

cocktailSort.call(a)

 

{{out}}

 

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

=={{header|ZX Spectrum Basic}}==

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}}