Uma introdução ao algoritmo de classificação Shell

A classificação por shell é uma técnica de classificação que divide uma determinada lista em sublistas e as classifica usando a classificação por inserção. O algoritmo usa um intervalo n que escolhe itens separados por n para incluir as sublistas.

As sublistas são então classificadas usando a classificação por inserção, após o que são combinadas. A lista combinada não está totalmente ordenada, mas dá ao algoritmo a vantagem de ter os itens mais próximos de suas posições finais.

A classificação por inserção é usada novamente para finalmente classificar a lista.

Um olhar mais atento sobre a classificação de cascas

A descrição acima pode não ter feito muito sentido, mas um exemplo deve ajudar. Suponha que você tenha a lista: [39, 6, 2, 51, 30, 42, 7, 4, 16] e um valor de lacuna de três.

A primeira sublista teria itens: 39, 51, 7

A segunda sublista: 6, 30, 4

A terceira e última sublista: 2, 42, 16

Após a classificação por inserção, cada uma das sublistas seria ordenada conforme abaixo:

O primeiro: 7, 39, 51

O segundo: 4, 6, 30

O terceiro: 2, 16, 42

A sublista classificada agora é combinada de uma maneira particular. Cada item da sublista é colocado no índice a partir do qual o valor da sublista original não classificado foi obtido.

Relacionado: Uma Introdução ao Algoritmo de Classificação de Bolhas

Você, portanto, terminará com a sequência abaixo:

[7, 4, 2, 39, 6, 16, 51, 30, 42]

Observe que a lista ainda não está classificada, mas os itens estão mais próximos das posições em que deveriam estar. Após realizar a classificação por inserção nesta combinação de lista, a lista será finalmente classificada:

[2, 4, 6, 7, 16, 30, 39, 42, 51]

Análise de Algoritmo

A complexidade da classificação de shell está entre O (n) e O (n2). O cálculo para essa conclusão está além do escopo deste artigo.

Implementação 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 // 2

Seguindo para a mesclagem de classificação

Existem vários algoritmos de classificação, cada um com um funcionamento único. A classificação de mesclagem, por exemplo, usa uma estratégia de divisão e conquista e tem uma complexidade de O (nlogn).

A classificação por mesclagem é, em alguns casos, melhor do que a classificação por shell e definitivamente vale a pena dar uma olhada. Deve ser o próximo na sua lista de leitura de algoritmos de classificação.