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.
Python
# 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 to test above
a = [5, 1, 4, 2, 8, 0, 2]
cocktailSort(a)
print("Sorted array is:")
for i in range(len(a)):
print ("%d" %a[i]),
Producción:
Sorted array is: 0 1 2 2 4 5 8
Complejidad de tiempo : O(n 2 ) para el peor y promedio de los casos y O(n) para el mejor de los casos.
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