Classificação Shell

Neste tutorial, você aprenderá como funciona a classificação de shell. Além disso, você encontrará exemplos de trabalho de classificação de shell em C, C ++, Java e Python.

A classificação de shell é um algoritmo que primeiro classifica os elementos distantes uns dos outros e reduz sucessivamente o intervalo entre os elementos a serem classificados. É uma versão generalizada do tipo de inserção.

Na classificação de shell, os elementos em um intervalo específico são classificados. O intervalo entre os elementos é reduzido gradualmente com base na sequência usada. O desempenho da classificação do shell depende do tipo de sequência usada para um determinado array de entrada.

Algumas das sequências ideais usadas são:

  • Sequência original de Shell: N/2 , N/4 ,… , 1
  • Incrementos de Knuth: 1, 4, 13,… , (3k - 1) / 2
  • Incrementos de Sedgewick: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Incrementos de Hibbard: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Incremento de Papernov e Stasevich: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Como funciona a classificação Shell?

  1. Suponha que precisamos classificar o seguinte array. Matriz inicial
  2. Estamos usando a sequência original do shell (N/2, N/4,… 1) como intervalos em nosso algoritmo.
    No primeiro loop, se o tamanho do array for N = 8then, os elementos situados no intervalo de N/2 = 4serão comparados e trocados se não estiverem em ordem.
    1. O 0º elemento é comparado com o 4º elemento.
    2. Se o 0º elemento for maior que o 4º então, o 4º elemento é primeiro armazenado na tempvariável e o 0thelemento (isto é, o elemento maior) é armazenado na 4thposição e o elemento armazenado tempé armazenado na 0thposição. Reorganizar os elementos no intervalo n / 2
      Este processo continua para todos os elementos restantes. Reorganizar todos os elementos no intervalo n / 2
  3. No segundo loop, um intervalo de N/4 = 8/4 = 2é obtido e novamente os elementos situados nesses intervalos são classificados. Reorganize os elementos no intervalo n / 4
    Você pode ficar confuso neste ponto. Todos os elementos da matriz no intervalo atual são comparados.
    Os elementos na 4ª 2ndposição e na posição são comparados. Os elementos na 2ª 0thposição e na posição também são comparados. Todos os elementos da matriz no intervalo atual são comparados.
  4. O mesmo processo ocorre para os elementos restantes. Reorganizar todos os elementos no intervalo n / 4
  5. Finalmente, quando o intervalo é N/8 = 8/8 =1, os elementos da matriz no intervalo de 1 são classificados. A matriz agora está completamente classificada. Reorganizar os elementos no intervalo n / 8

Algoritmo de classificação de shell

 shellSort (array, size) para o intervalo i <- size / 2n até 1 para cada intervalo "i" no array classifica todos os elementos no intervalo "i" final shellSort

Exemplos de Python, Java e C / C ++

Python Java C C ++ 
# Shell sort in python def shellSort(array, n): # Rearrange elements at each n/2, n/4, n/8,… intervals interval = n // 2 while interval> 0: for i in range(interval, n): temp = array(i) j = i while j>= interval and array(j - interval)> temp: array(j) = array(j - interval) j -= interval array(j) = temp interval //= 2 data = (9, 8, 3, 7, 5, 6, 4, 1) size = len(data) shellSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Shell sort in Java programming import java.util.Arrays; // Shell sort class ShellSort ( // Rearrange elements at each n/2, n/4, n/8,… intervals void shellSort(int array(), int n) ( for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 8, 3, 7, 5, 6, 4, 1 ); int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) ) 
// Shell Sort in C programming #include // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); printf("Sorted array: "); printArray(data, size); ) 
// Shell Sort in C++ programming #include using namespace std; // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); cout << "Sorted array: "; printArray(data, size); )

Complexidade

A classificação de shell é um algoritmo de classificação instável porque esse algoritmo não examina os elementos situados entre os intervalos.

Complexidade de tempo

  • Complexidade de pior caso : menor ou igual a A complexidade de pior caso para classificação de shell é sempre menor ou igual a . De acordo com o Teorema de Poonen, a complexidade do pior caso para classificação de shell é ou ou ou algo entre os dois.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Melhor caso de complexidade : O(n*log n)
    quando a matriz já está classificada, o número total de comparações para cada intervalo (ou incremento) é igual ao tamanho da matriz.
  • Complexidade média do caso : O(n*log n)
    É próximo .O(n1.25)

A complexidade depende do intervalo escolhido. As complexidades acima diferem para diferentes sequências de incremento escolhidas. A melhor sequência de incremento é desconhecida.

Complexidade do espaço:

A complexidade do espaço para classificação de shell é O(1).

Aplicativos de classificação Shell

A classificação Shell é usada quando:

  • chamar uma pilha é uma sobrecarga. A biblioteca uClibc usa esse tipo.
  • a recursão excede um limite. O compressor bzip2 usa.
  • A classificação por inserção não funciona bem quando os elementos próximos estão distantes. A classificação da concha ajuda a reduzir a distância entre os elementos próximos. Dessa forma, haverá menos troca de trocas a serem realizadas.

Artigos interessantes...