ソートアルゴリズム——カクテルソート(Cocktail sort)【コード実装】

ぎじふごう

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

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

C

#include 
 
// 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;
}

C++

#include 
#include 
 
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;
}

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

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

汎用版

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

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

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

Julia

function coctailsort(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
 -> ordered: ", cocktailsort(v))

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(", "))
    }
}

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

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
";
my @C=cocktailSort(@B);
print "@C
";
################### 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
}

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

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) . '
';

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

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

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

より多くのコードを更新し続けます!ネットワークから整理する.