Algoritmo de classificação de shell com EXEMPLO

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

1. Melhor complexidade do caso: O(n*log n)
2. Complexidade média do caso: O(n*log n)
3. 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).