Estrutura de dados e algoritmos - classificação Shell

A classificação shell é um algoritmo de classificação altamente eficiente e é baseado no algoritmo de classificação por inserção. Este algoritmo evita grandes deslocamentos como no caso de ordenação por inserção, se o valor menor estiver na extrema direita e tiver que ser movido na extrema esquerda.

Esse algoritmo usa a classificação por inserção em elementos amplamente distribuídos, primeiro para classificá-los e, em seguida, classifica os elementos menos espaçados. Este espaçamento é denominado comointerval. Este intervalo é calculado com base na fórmula de Knuth como -

Fórmula de Knuth

h = h * 3 + 1
where −
   h is interval with initial value 1

Este algoritmo é bastante eficiente para conjuntos de dados de tamanho médio, pois sua complexidade média e de pior caso desse algoritmo depende da sequência de lacunas mais conhecida é Ο (n), onde n é o número de itens. E o pior caso de complexidade de espaço é O (n).

Como funciona a classificação Shell?

Vamos considerar o exemplo a seguir para ter uma ideia de como funciona a classificação por shell. Pegamos o mesmo array que usamos em nossos exemplos anteriores. Para nosso exemplo e facilidade de compreensão, tomamos o intervalo de 4. Faça uma sub-lista virtual de todos os valores localizados no intervalo de 4 posições. Aqui, esses valores são {35, 14}, {33, 19}, {42, 27} e {10, 44}

Comparamos os valores em cada sub-lista e os trocamos (se necessário) na matriz original. Após esta etapa, a nova matriz deve se parecer com isto -

Então, pegamos o intervalo de 1 e essa lacuna gera duas sublistas - {14, 27, 35, 42}, {19, 10, 33, 44}

Comparamos e trocamos os valores, se necessário, na matriz original. Após esta etapa, a matriz deve ficar assim -

Por fim, classificamos o restante do array usando o intervalo de valor 1. A classificação por shell usa a classificação por inserção para classificar o array.

A seguir está a descrição passo a passo -

Vemos que foram necessárias apenas quatro trocas para classificar o restante do array.

Algoritmo

A seguir está o algoritmo para classificação de shell.

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

Pseudo-código

A seguir está o pseudocódigo para classificação de shell.

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

Para saber sobre a implementação de classificação de shell na linguagem de programação C, clique aqui .