Jump to content

Algorithm Implementation/Sorting/Cocktail sort

From Wikibooks, open books for an open world
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;    
}

Follow the Java example above, but replace the first line with

int cocktailSort (int []numbers)

.

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

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