Introducción al algoritmo de clasificación de shell
La ordenación de shell es una técnica de ordenación que divide una lista determinada en sublistas y luego las ordena mediante ordenación por inserción. El algoritmo utiliza un espacio n que elige elementos que están separados por n espacios para formar las sublistas.
A continuación, las sublistas se ordenan mediante la ordenación por inserción, después de lo cual se combinan. La lista combinada no está completamente ordenada, pero le da al algoritmo la ventaja de tener los elementos más cerca de sus posiciones finales.
La ordenación por inserción se usa nuevamente para ordenar finalmente la lista.
Una mirada más cercana al tipo de caparazón
Es posible que la descripción anterior no tenga mucho sentido, pero un ejemplo debería ayudar. Suponga que tiene la lista: [39, 6, 2, 51, 30, 42, 7, 4, 16] y un valor de espacio de tres.
La primera sublista tendría elementos: 39, 51, 7
La segunda sublista: 6, 30, 4
La tercera y última sublista: 2, 42, 16
Después de la ordenación por inserción, cada una de las sublistas se ordenaría de la siguiente manera:
El primero: 7, 39, 51
El segundo: 4, 6, 30
El tercero: 2, 16, 42
La sublista ordenada ahora se combina de una manera particular. Cada elemento de la sublista se coloca en el índice del que se recopiló el valor original de la sublista sin clasificar.
Por lo tanto, terminará con la siguiente secuencia:
[7, 4, 2, 39, 6, 16, 51, 30, 42]
Observe que la lista aún no está ordenada, pero los elementos están más cerca de las posiciones en las que se supone que deben estar. Después de realizar la ordenación por inserción en esta combinación de lista, la lista finalmente se ordenará:
[2, 4, 6, 7, 16, 30, 39, 42, 51]
Análisis de algoritmos
La complejidad del tipo de caparazón está entre O (n) y O (n2). El cálculo de esta conclusión está más allá del alcance de este artículo.
Implementación de Python:
def shellSort(my_list):
n = len(my_list)
interval = n // 2 # floor division
while interval > 0:
for val in range(interval, n):
temp = my_list[val]
x = val
while x >= interval and my_list[x - interval] > temp:
my_list[x] = my_list[x - interval]
x = x - interval
my_list[x] = temp
interval = interval // 2Pasar a la ordenación combinada
Hay varios algoritmos de clasificación, cada uno con un funcionamiento único. El tipo de combinación, por ejemplo, utiliza una estrategia de dividir y conquistar y tiene una complejidad de O (nlogn).
La ordenación por fusión es, en algunos casos, mejor que la ordenación por shell y definitivamente vale la pena verla. Debería ser el siguiente en su lista de lectura de algoritmos de clasificación.