Algorithm Implementation/Sorting/Cocktail sort
Appearance
Java
[edit | edit source]public static int[] cocktailSort(int[] numbers)
{
boolean swapped = true;
int i = 0;
int j = numbers.length - 1;
while(i < j && swapped)
{
swapped = false;
for(int k = i; k < j; k++)
{
if(numbers[k] > numbers[k + 1])
{
int temp = numbers[k];
numbers[k] = numbers[k + 1];
numbers[k + 1] = temp;
swapped = true;
}
}
j--;
if(swapped)
{
swapped = false;
for(int k = j; k > i; k--)
{
if(numbers[k] < numbers[k - 1])
{
int temp = numbers[k];
numbers[k] = numbers[k - 1];
numbers[k - 1] = temp;
swapped = true;
}
}
}
i++;
}
return numbers;
}
C++
[edit | edit source]Follow the Java example above, but replace the first line with
int cocktailSort (int []numbers)
.
Perl
[edit | edit source]sub swap {
@_[ 0, 1 ] = @_[ 1, 0 ];
return 1;
}
sub cocktail_sort {
# returns a sorted copy
my @a = @_;
for ( my $swapped = 1 ; $swapped ; ) {
for ( $swapped = 0, my $i = 0 ; $i < ( $#a - 1 ) ; $i += 1 ) {
$swapped = swap $a[ $i + 1 ], $a[$i] if $a[$i] > $a[ $i + 1 ];
}
for ( $swapped = 0, my $i = ( $#a - 1 ) ; $i > 0 ; $i -= 1 ) {
$swapped = swap $a[ $i + 1 ], $a[$i] if $a[$i] > $a[ $i + 1 ];
}
}
wantarray ? @a : \@a;
}
Phix
[edit | edit source]function cocktail_sort(sequence s)
integer swapped = 1, f = 1, t = length(s)-1, d = 1
while swapped do
swapped = 0
for i=f to t by d do
if s[i]>s[i+1] then
{s[i],s[i+1],swapped} = {s[i+1],s[i],1}
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}
end while
return s
end function
Python
[edit | edit source]def cocktail_sort(A):
for k in range(len(A)-1, 0, -1):
swapped = False
for i in range(k, 0, -1):
if A[i]<A[i-1]:
A[i], A[i-1] = A[i-1], A[i]
swapped = True
for i in range(k):
if A[i] > A[i+1]:
A[i], A[i+1] = A[i+1], A[i]
swapped = True
if not swapped:
return A
VB.NET
[edit | edit source] Public Sub cocktailsort(ByRef a() As Integer)
Dim i As Integer = 0
Dim num As Integer = 0
Do
num = 0
While Not i = a.Length - 1
If a(i) > a(i + 1) Then
swap(a(i), a(i + 1))
num += 1
End If
i += 1
End While
If num = 0 Then
Exit Do
End If
While Not i = 0
If a(i) < a(i - 1) Then
swap(a(i), a(i - 1))
num += 1
End If
i -= 1
End While
Loop Until num = 0
End Sub
Dual Cocktail Shaker Sort
[edit | edit source]A variant of Cocktail Shaker Sort that sorts from both ends of the array simultaneously, improving performance.
Java
[edit | edit source]public static int[] cocktailTwisterSort(int[] arr)
{
if (arr.length <= 1) { return arr; }
boolean swapped = true;
int start = 0;
int end = arr.length;
while (swapped == true)
{
swapped = false;
for (int i = start, j = end - 1; i < end - 1; ++i, --j)
{
if (arr[i] > arr[i + 1])
{
swapped = true;
int temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
if (arr[j] < arr[j - 1])
{
swapped = true;
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
++start;
--end;
}
return arr;
}
Rust
[edit | edit source]fn cocktail_twister_sort(arr: &mut Vec<i32>)
{
if arr.len() <= 1 { return; }
let mut swapped: bool = true;
let mut start: usize = 0;
let mut end: usize = arr.len();
while swapped == true
{
swapped = false;
let mut j: usize = end - 1; // Remove this line if declaring j inside the inner loop is preferred
for i in start..end - 1
{
// let j: usize = end - 1 - (i - start);
if arr[i] > arr[i + 1]
{
arr.swap(i, i + 1);
swapped = true;
}
if arr[j] < arr[j - 1]
{
arr.swap(j, j - 1);
swapped = true;
}
j -= 1; // Do not decrement j if j pointer is inside the inner loop
}
start += 1;
end -= 1;
}
}