En shellSort, hacemos que la array esté ordenada por h para un valor grande de h. Seguimos reduciendo el valor de h hasta que se convierte en 1. Se dice que una array está ordenada por h si todas las sublistas de cada h\’th elemento están ordenadas.
Python
# Python program for implementation of Shell Sort
def shellSort(arr):
# Start with a big gap, then reduce the gap
n = len(arr)
gap = n/2
# Do a gapped insertion sort for this gap size.
# The first gap elements a[0..gap-1] are already in gapped
# order keep adding one more element until the entire array
# is gap sorted
while gap > 0:
for i in range(gap,n):
# add a[i] to the elements that have been gap sorted
# save a[i] in temp and make a hole at position i
temp = arr[i]
# shift earlier gap-sorted elements up until the correct
# location for a[i] is found
j = i
while j >= gap and arr[j-gap] >temp:
arr[j] = arr[j-gap]
j -= gap
# put temp (the original a[i]) in its correct location
arr[j] = temp
gap /= 2
# Driver code to test above
arr = [ 12, 34, 54, 2, 3]
n = len(arr)
print ("Array before sorting:")
for i in range(n):
print(arr[i]),
shellSort(arr)
print ("\nArray after sorting:")
for i in range(n):
print(arr[i]),
# This code is contributed by Mohit Kumra
Producción:
Array before sorting: 12 34 54 2 3 Array after sorting: 2 3 12 34 54
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(1)
Consulte el artículo completo sobre ShellSort 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