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.
Algoritmo:
cada iteración del algoritmo se divide en 2 etapas:
- La primera etapa recorre la array de izquierda a derecha, al igual que Bubble Sort. Durante el bucle, 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.
- 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.
CPP
// 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 arr[] = { 5, 1, 4, 2, 8, 0, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
CocktailSort(arr, n);
printf("Sorted array :\n");
printArray(arr, n);
return 0;
}
Sorted array : 0 1 2 2 4 5 8
Complejidad de tiempo de peor caso y promedio: O(n 2 ).
Complejidad temporal del mejor caso: O(n). El mejor de los casos ocurre cuando la array ya está ordenada.
Espacio Auxiliar: O(1)
¡ Consulte el artículo completo sobre Clasificación de cócteles para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA