Tipo de cóctel

Cocktail Sort es una variación de Bubble sort . El algoritmo de clasificación de burbujas siempre atraviesa los elementos desde la izquierda y mueve el elemento más grande a su posición correcta en la primera iteración y el segundo más grande en la segunda iteración y así sucesivamente. Cocktail Sort atraviesa una array dada en ambas direcciones alternativamente. La clasificación cóctel no pasa por la iteración innecesaria, lo que la hace eficiente para arreglos grandes.

Los tipos de cóctel rompen las barreras que impiden que los tipos de burbujas sean lo suficientemente eficientes en arreglos grandes al no permitirles pasar por iteraciones innecesarias en una región específica (o grupo) antes de pasar a otra sección de un arreglo.
Algoritmo: 
cada iteración del algoritmo se divide en 2 etapas: 

1. La primera etapa recorre la array de izquierda a derecha, al igual que Bubble Sort. Durante el ciclo, los elementos adyacentes se comparan y si el valor de la izquierda es mayor que el valor de la derecha, se intercambian los valores. Al final de la primera iteración, el número más grande residirá al final de la array.
2. La segunda etapa recorre la array en dirección opuesta, comenzando desde el elemento justo antes del elemento ordenado más recientemente y volviendo al inicio de la array. Aquí también, los elementos adyacentes se comparan y se intercambian si es necesario.

Ejemplo : 

Consideremos una array de ejemplo (5 1 4 2 8 0 2)

Primer pase hacia adelante: 
( 5 1 4 2 8 0 2) ? ( 1 5 4 2 8 0 2), Intercambiar desde 5 > 1 
(1 5 4 2 8 0 2) ? (1 4 5 2 8 0 2), Intercambiar desde 5 > 4 
(1 4 5 2 8 0 2) ? (1 4 2 5 8 0 2), Intercambiar desde 5 > 2 
(1 4 2 5 8 0 2) ? (1 4 2 5 8 0 2) 
(1 4 2 5 8 0 2) ? (1 4 2 5 0 8 2), Intercambiar desde 8 > 0 
(1 4 2 5 0 8 2 ) ? (1 4 2 5 0 2 8 ), Intercambiar desde 8 > 2
Después del primer paso hacia adelante, el elemento más grande de la array estará presente en el último índice de la array.
Primer pase hacia atrás: 
(1 4 2 5 0 2 8) ? (1 4 2 5 0 2 8) 
(1 4 2 5 0 2 8) ? (1 4 2 0 5 2 8), Intercambiar desde 5 > 0 
(1 4 2 0 5 2 8) ? (1 4 0 2 5 2 8), Intercambiar desde 2 > 0 
(1 4 0 2 5 2 8) ? (1 0 4 2 5 2 8), Intercambiar desde 4 > 0 
( 1 0 4 2 5 2 8) ? ( 0 1 4 2 5 2 8), Cambiar desde 1 > 0
Después del primer paso hacia atrás, el elemento más pequeño de la array estará presente en el primer índice de la array.
Segundo pase hacia adelante: 
(0 1 4 2 5 2 8) ? (0 1 4 2 5 2 8) 
(0 1 4 2 5 2 8) ? (0 1 2 4 5 2 8), Intercambiar desde 4 > 2 
(0 1 2 4 5 2 8) ? (0 1 2 4 5 2 8) 
(0 1 2 4 5 2 8) ? (0 1 2 4 2 5 8), Intercambio desde 5 > 2
Segundo pase hacia atrás: 
(0 1 2 4 2 5 8) ? (0 1 2 2 4 5 8), Cambiar desde 4 > 2
Ahora, la array ya está ordenada, pero nuestro algoritmo no sabe si está completa. El algoritmo necesita completar todo este pase sin ningún intercambio para saber que está ordenado. 
(0 1 2 2 4 5 8) ? (0 1 2 2 4 5 8) 
(0 1 2 2 4 5 8) ? (01 2 2 4 5 8)
A continuación se muestra la implementación del algoritmo anterior:

// C++ implementation of Cocktail Sort
#include <bits/stdc++.h>
using namespace std;
 
// Sorts array a[0..n-1] using Cocktail sort
void CocktailSort(int a[], int n)
{
    bool swapped = true;
    int start = 0;
    int end = n - 1;
 
    while (swapped) {
        // reset the swapped flag on entering
        // the loop, because it might be true from
        // a previous iteration.
        swapped = false;
 
        // loop from left to right same as
        // the bubble sort
        for (int i = start; i < end; ++i) {
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                swapped = true;
            }
        }
 
        // if nothing moved, then array is sorted.
        if (!swapped)
            break;
 
        // otherwise, reset the swapped flag so that it
        // can be used in the next stage
        swapped = false;
 
        // move the end point back by one, because
        // item at the end is in its rightful spot
        --end;
 
        // from right to left, doing the
        // same comparison as in the previous stage
        for (int i = end - 1; i >= start; --i) {
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                swapped = true;
            }
        }
 
        // increase the starting point, because
        // the last stage would have moved the next
        // smallest number to its rightful spot.
        ++start;
    }
}
 
/* Prints the array */
void printArray(int a[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
}
 
// Driver code
int main()
{
    int a[] = { 5, 1, 4, 2, 8, 0, 2 };
    int n = sizeof(a) / sizeof(a[0]);
    CocktailSort(a, n);
    printf("Sorted array :\n");
    printArray(a, n);
    return 0;
}

// Java program for implementation of Cocktail Sort
public class CocktailSort
{
    void cocktailSort(int a[])
    {
        boolean swapped = true;
        int start = 0;
        int end = a.length;
 
        while (swapped == true)
        {
            // reset the swapped flag on entering the
            // loop, because it might be true from a
            // previous iteration.
            swapped = false;
 
            // loop from bottom to top same as
            // the bubble sort
            for (int i = start; i < end - 1; ++i)
            {
                if (a[i] > a[i + 1]) {
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    swapped = true;
                }
            }
 
            // if nothing moved, then array is sorted.
            if (swapped == false)
                break;
 
            // otherwise, reset the swapped flag so that it
            // can be used in the next stage
            swapped = false;
 
            // move the end point back by one, because
            // item at the end is in its rightful spot
            end = end - 1;
 
            // from top to bottom, doing the
            // same comparison as in the previous stage
            for (int i = end - 1; i >= start; i--)
            {
                if (a[i] > a[i + 1])
                {
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    swapped = true;
                }
            }
 
            // increase the starting point, because
            // the last stage would have moved the next
            // smallest number to its rightful spot.
            start = start + 1;
        }
    }
 
    /* Prints the array */
    void printArray(int a[])
    {
        int n = a.length;
        for (int i = 0; i < n; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
 
    // Driver code
    public static void main(String[] args)
    {
        CocktailSort ob = new CocktailSort();
        int a[] = { 5, 1, 4, 2, 8, 0, 2 };
        ob.cocktailSort(a);
        System.out.println("Sorted array");
        ob.printArray(a);
    }
}

# Python program for implementation of Cocktail Sort
 
 
def cocktailSort(a):
    n = len(a)
    swapped = True
    start = 0
    end = n-1
    while (swapped == True):
 
        # reset the swapped flag on entering the loop,
        # because it might be true from a previous
        # iteration.
        swapped = False
 
        # loop from left to right same as the bubble
        # sort
        for i in range(start, end):
            if (a[i] > a[i + 1]):
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
 
        # if nothing moved, then array is sorted.
        if (swapped == False):
            break
 
        # otherwise, reset the swapped flag so that it
        # can be used in the next stage
        swapped = False
 
        # move the end point back by one, because
        # item at the end is in its rightful spot
        end = end-1
 
        # from right to left, doing the same
        # comparison as in the previous stage
        for i in range(end-1, start-1, -1):
            if (a[i] > a[i + 1]):
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
 
        # increase the starting point, because
        # the last stage would have moved the next
        # smallest number to its rightful spot.
        start = start + 1
 
 
# Driver code
a = [5, 1, 4, 2, 8, 0, 2]
cocktailSort(a)
print("Sorted array is:")
for i in range(len(a)):
    print("% d" % a[i])

// C# program for implementation of Cocktail Sort
using System;
 
class GFG {
 
    static void cocktailSort(int[] a)
    {
        bool swapped = true;
        int start = 0;
        int end = a.Length;
 
        while (swapped == true) {
 
            // reset the swapped flag on entering the
            // loop, because it might be true from a
            // previous iteration.
            swapped = false;
 
            // loop from bottom to top same as
            // the bubble sort
            for (int i = start; i < end - 1; ++i) {
                if (a[i] > a[i + 1]) {
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    swapped = true;
                }
            }
 
            // if nothing moved, then array is sorted.
            if (swapped == false)
                break;
 
            // otherwise, reset the swapped flag so that it
            // can be used in the next stage
            swapped = false;
 
            // move the end point back by one, because
            // item at the end is in its rightful spot
            end = end - 1;
 
            // from top to bottom, doing the
            // same comparison as in the previous stage
            for (int i = end - 1; i >= start; i--) {
                if (a[i] > a[i + 1]) {
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    swapped = true;
                }
            }
 
            // increase the starting point, because
            // the last stage would have moved the next
            // smallest number to its rightful spot.
            start = start + 1;
        }
    }
 
    /* Prints the array */
    static void printArray(int[] a)
    {
        int n = a.Length;
        for (int i = 0; i < n; i++)
            Console.Write(a[i] + " ");
        Console.WriteLine();
    }
 
    // Driver code
    public static void Main()
    {
        int[] a = { 5, 1, 4, 2, 8, 0, 2 };
        cocktailSort(a);
        Console.WriteLine("Sorted array ");
        printArray(a);
    }
}
 
// This code is contributed by Sam007

<script>
    // Javascript program for implementation of Cocktail Sort
     
    function cocktailSort(a)
    {
        let swapped = true;
        let start = 0;
        let end = a.length;
  
        while (swapped == true) {
  
            // reset the swapped flag on entering the
            // loop, because it might be true from a
            // previous iteration.
            swapped = false;
  
            // loop from bottom to top same as
            // the bubble sort
            for (let i = start; i < end - 1; ++i) {
                if (a[i] > a[i + 1]) {
                    let temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    swapped = true;
                }
            }
  
            // if nothing moved, then array is sorted.
            if (swapped == false)
                break;
  
            // otherwise, reset the swapped flag so that it
            // can be used in the next stage
            swapped = false;
  
            // move the end point back by one, because
            // item at the end is in its rightful spot
            end = end - 1;
  
            // from top to bottom, doing the
            // same comparison as in the previous stage
            for (let i = end - 1; i >= start; i--) {
                if (a[i] > a[i + 1]) {
                    let temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    swapped = true;
                }
            }
  
            // increase the starting point, because
            // the last stage would have moved the next
            // smallest number to its rightful spot.
            start = start + 1;
        }
    }
  
    /* Prints the array */
    function printArray(a)
    {
        let n = a.length;
        for (let i = 0; i < n; i++)
            document.write(a[i] + " ");
        document.write("</br>");
    }
     
    let a = [ 5, 1, 4, 2, 8, 0, 2 ];
    cocktailSort(a);
    document.write("Sorted array :" + "</br>");
    printArray(a);
     
    // This code is contributed by decode2207.
</script>

Sorted array :
0 1 2 2 4 5 8 

La gente ha dado muchos nombres diferentes al tipo de cóctel:

• Clasificación por agitador. 
• Clasificación bidireccional.
• Tipo de coctelera.
• Clasificación de lanzadera.
• Clase de hora feliz.
• Clasificación de ondulación.

Ordenar en el lugar: Sí
Estable: Sí
Comparación con Bubble Sort: 
Las complejidades de tiempo son las mismas, pero Cocktail funciona mejor que Bubble Sort. Por lo general, la clasificación de cócteles es menos de dos veces más rápida que la clasificación de burbujas. Considere el ejemplo (2, 3, 4, 5, 1). La ordenación de burbuja requiere cuatro recorridos de una array para este ejemplo, mientras que la ordenación de cóctel requiere solo dos recorridos. (Fuente Wiki )

Referencias: 

• https://en.wikipedia.org/wiki/Cocktail_shaker_sort
• http://will.thimbleby.net/algorithms/doku.php?id=cocktail_sort
• http://www.programming-algorithms.net/article/40270/Shaker-sort

Este artículo es una contribución de Rahul Agrawal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.