Algoritmo de classificação de shell com EXEMPLO
Sarah Chen
O que é classificação de shell
O método Shell, ou classificação Shell na estrutura de dados, é um algoritmo eficiente de classificação por comparação no local. Seu nome é uma homenagem a Donald Shell quando ele propôs a ideia inicial em 1959. Shell sort é uma extensão generalizada do algoritmo de classificação por inserção.
A ideia fundamental deste algoritmo de classificação é agrupar os elementos que estão distantes e classificá-los de acordo. Em seguida, diminua gradualmente a distância entre eles. A classificação Shell supera a complexidade média do tempo de caso da classificação por inserção, comparando e trocando elementos que estão distantes.
Essa lacuna, conhecida como intervalo, é reduzida de acordo com algumas sequências de lacunas ótimas. O tempo de execução do shell sort também depende dessas sequências. Existem várias sequências de lacunas, como a sequência original de Shell, a fórmula de Knuth, os incrementos de Hibbard, etc. A sequência de lacunas original de Shell é - n/2, n/4, n/8, ……….1
Algoritmo de classificação de shell
As etapas ou procedimentos para o algoritmo de classificação de shell são as seguintes:
Passo 1) Inicialize o valor do intervalo, h = n/2. (Neste exemplo, n é o tamanho da matriz)
Passo 2) Coloque todos os elementos a uma distância do intervalo h em uma sublista.
Passo 3) Classifique essas sublistas usando classificação por inserção.
Passo 4) Defina o novo intervalo, h=h/2.
Passo 5) Se h>0, vá para a etapa 2. Caso contrário, vá para a etapa 6.
Passo 6) A saída resultante será a matriz classificada.
Como funciona a classificação de shell
Na classificação por inserção, os elementos são movidos apenas uma posição por vez. Pelo contrário, o shell sort divide o array em partes menores com base no valor do intervalo e executa a classificação por inserção nessas partes.
Gradualmente, o valor do intervalo diminui e o tamanho das peças divididas aumenta. Como as peças são classificadas individualmente de antemão, a fusão dessas peças requer menos etapas do que a tipo de inserção.
O GIF a seguir mostra uma demonstração de classificação de shell. Nesta demonstração, os valores indicados em vermelho e azul são comparados e trocados com base na classificação por inserção. Em seguida, o intervalo diminui e a classificação do shell inicia a classificação por inserção nos dados quase classificados.
Funcionamento do algoritmo de classificação Shell
Vejamos o seguinte exemplo de algoritmo de classificação de shell. Neste exemplo, classificaremos o seguinte array usando shell sort:
Passo 1) Aqui, o tamanho do array é 8. Assim, o valor do intervalo será h = 8/2 ou 4.
Passo 2) Agora, armazenaremos todos os elementos a uma distância de 4. Para o nosso caso, as sublistas são- {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Passo 3) Agora, essas sublistas serão classificadas usando classificação por inserção, onde uma variável temporária é usada para comparar os dois números e classificar de acordo.
A matriz seria semelhante à seguinte após a troca de operações-
Passo 4) Agora diminuiremos o valor inicial do intervalo. O novo intervalo será h=h/2 ou 4/2 ou 2.
Passo 5) Como 2>0, iremos para a etapa 2 para armazenar todos os elementos a uma distância de 2. Por enquanto, as sublistas são-
{1, 5, 8, 7}, {4, 2, 6, 3}
Em seguida, essas sublistas serão classificadas usando classificação por inserção. Depois de comparar e trocar a primeira sublista, o array seria o seguinte.
Após classificar a segunda sublista, o array original será:
Então, novamente, o intervalo será diminuído. Agora o intervalo será h=h/2 ou 2/1 ou 1. Portanto, usaremos o algoritmo de classificação por inserção para classificar o array modificado.
A seguir está a descrição do procedimento passo a passo da classificação por inserção.
O intervalo é novamente dividido por 2. Nesse momento, o intervalo se torna 0. Então, vamos para a etapa 6.
Passo 6) Como o intervalo é 0, o array é classificado neste momento. A matriz classificada é-
Pseudo-código
Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
for (i = interval; i & lt; n; i += 1)
temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; temp; j -= interval)
a[j] = a[j - interval];
a[j] = temp;
End
Programa de classificação de shell em C/C++
Entrada:
//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
for (int interval = size / 2; interval > 0; interval /= 2) {
for (int i = interval; i < size; i += 1) {
int temp = data[i];
int j;
for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
data[j] = data[j - interval];
}
data[j] = temp;
}
}
}
int main() {
int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
int size = sizeof(data) / sizeof(data[0]);
ShellSort(data, size);
cout << "Sorted Output: \n";
for (int i = 0; i < size; i++)
cout << data[i] << " ";
cout << "\n";
}
Saída:
Sorted Output: 1 2 3 4 5 6 7 8
Exemplo de classificação de shell em Python
Entrada:
#Shell Sort Example in Python
def ShellSort(data, size):
interval = size // 2
while interval > 0:
for i in range(interval, size):
temp = data[i]
j = i
while j >= interval and data[j - interval] > temp:
data[j] = data[j - interval]
j -= interval
data[j] = temp
interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)
Saída:
Sorted Output: [1, 2, 3, 4, 5, 6, 7, 8]
Aplicações de Shell Sort
Aqui estão aplicações importantes do Shell Sort:
- A classificação Shell é usada no Kernel do Linux porque não usa uma pilha de chamadas.
- A biblioteca uClibc usa classificação Shell.
- O compressor bzip2 usa classificação Shell para parar de exceder a recursão.
Vantagens e desvantagens do tipo Shell
| Diferenciais | Desvantagens |
|---|---|
| Nenhuma chamada de pilha é necessária. | Não é eficiente para tamanhos de array enormes. |
| Fácil implementação. | Ineficiente para elementos amplamente espalhados. |
| Eficiente para elementos menos espaçados. |
Análise de complexidade de classificação de shell
Complexidade de tempo do Shell Sort
A complexidade de tempo do algoritmo de classificação de shell é O (n ^ 2). O raciocínio é o seguinte:
Para o melhor cenário, a quantidade total de testes para todos os intervalos quando a matriz foi previamente organizada é igual ao log n. Assim, a complexidade seria O(n*log n).
Para o pior cenário, vamos considerar que o array consiste de tal forma que os elementos requerem o maior número de comparações. Então, todos os elementos não serão comparados e trocados até a última iteração. Portanto, o total de comparações necessárias para o incremento final é O(n^2).
Em conclusão, as complexidades de tempo seriam
- Melhor complexidade do caso: O(n*log n)
- Complexidade média do caso: O(n*log n)
- Complexidade de pior caso: O (n ^ 2)
A complexidade do tempo de execução da classificação de shell depende muito das sequências de incremento de intervalo usadas. No entanto, a melhor sequência de incremento para classificação de shell ainda é desconhecida.
Complexidade do espaço de classificação de shell
Nesta classificação de comparação, não precisamos de nenhum espaço auxiliar adicional. Assim, a complexidade espacial deste tipo de algoritmo é O(1).
