Comb Sort es principalmente una mejora sobre Bubble Sort. La ordenación de burbuja siempre compara valores adyacentes. Entonces todas las inversiones se eliminan una por una. Comb Sort mejora el Bubble Sort al usar un espacio de tamaño superior a 1. El espacio comienza con un valor grande y se reduce en un factor de 1,3 en cada iteración hasta que alcanza el valor 1. Por lo tanto, Comb Sort elimina más de una inversión cuenta con uno swap y funciona mejor que Bubble Sort.
Se ha encontrado empíricamente que el factor de reducción es 1.3 (al probar Combsort en más de 200,000 listas aleatorias) [Fuente: Wiki ]
Aunque, en promedio, funciona mejor que Bubble Sort, el peor de los casos sigue siendo O (n 2 ).
Python
# Python program for implementation of CombSort
# To find next gap from current
def getNextGap(gap):
# Shrink gap by Shrink factor
gap = (gap * 10)/13
if gap < 1:
return 1
return gap
# Function to sort arr[] using Comb Sort
def combSort(arr):
n = len(arr)
# Initialize gap
gap = n
# Initialize swapped as true to make sure that
# loop runs
swapped = True
# Keep running while gap is more than 1 and last
# iteration caused a swap
while gap !=1 or swapped == 1:
# Find next gap
gap = getNextGap(gap)
# Initialize swapped as false so that we can
# check if swap happened or not
swapped = False
# Compare all elements with current gap
for i in range(0, n-gap):
if arr[i] > arr[i + gap]:
arr[i], arr[i + gap]=arr[i + gap], arr[i]
swapped = True
# Driver code to test above
arr = [ 8, 4, 1, 3, -44, 23, -6, 28, 0]
combSort(arr)
print ("Sorted array:")
for i in range(len(arr)):
print (arr[i]),
# This code is contributed by Mohit Kumra
Producción :
Sorted array: -44 -6 0 1 3 4 8 23 28 56
¡ Consulte el artículo completo sobre Comb Sort 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