Tipo de concha

En este tutorial, aprenderá cómo funciona la ordenación de shell. Además, encontrará ejemplos prácticos de ordenación de shell en C, C ++, Java y Python.

La ordenación de shell es un algoritmo que primero ordena los elementos lejos unos de otros y reduce sucesivamente el intervalo entre los elementos que se van a ordenar. Es una versión generalizada del ordenamiento por inserción.

En la ordenación de shell, se ordenan los elementos en un intervalo específico. El intervalo entre los elementos se reduce gradualmente en función de la secuencia utilizada. El rendimiento de la clasificación de shell depende del tipo de secuencia utilizada para una matriz de entrada determinada.

Algunas de las secuencias óptimas utilizadas son:

• Secuencia 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 y Stasevich: 1, 3, 5, 9, 17, 33, 65,…
• Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

¿Cómo funciona Shell Sort?

1. Supongamos que necesitamos ordenar la siguiente matriz. Matriz inicial
2. Estamos usando la secuencia original del shell (N/2, N/4,… 1) como intervalos en nuestro algoritmo.
   En el primer ciclo, si el tamaño de la matriz es N = 8entonces, los elementos que se encuentran en el intervalo de N/2 = 4se comparan y se intercambian si no están en orden.
   1. El elemento 0 se compara con el elemento 4.
   2. Si el 0º elemento es mayor que el 4º, entonces, el 4º elemento se almacena primero en tempvariable y el 0thelemento (es decir, el elemento mayor) se almacena en la 4thposición y el elemento almacenado en tempse almacena en la 0thposición. Reorganizar los elementos en un intervalo n / 2
      Este proceso continúa para todos los elementos restantes. Reorganizar todos los elementos en un intervalo n / 2
3. En el segundo ciclo, N/4 = 8/4 = 2se toma un intervalo de y de nuevo se clasifican los elementos que se encuentran en estos intervalos. Reorganizar los elementos en un intervalo de n / 4
   Es posible que se confunda en este punto. Se comparan todos los elementos de la matriz que se encuentran en el intervalo actual.
   Se 2ndcomparan los elementos en 4ª posición y . 0thTambién se comparan los elementos en 2ª y posición. Se comparan todos los elementos de la matriz que se encuentran en el intervalo actual.
4. El mismo proceso continúa para los elementos restantes. Reorganizar todos los elementos en un intervalo n / 4
5. Finalmente, cuando el intervalo es, N/8 = 8/8 =1se ordenan los elementos de la matriz que se encuentran en el intervalo de 1. La matriz ahora está completamente ordenada. Reorganizar los elementos en un intervalo de n / 8

Algoritmo de clasificación de shell

 shellSort (matriz, tamaño) para el intervalo i <- tamaño / 2n hasta 1 para cada intervalo "i" en la matriz ordenar todos los elementos en el intervalo "i" end shellSort

Ejemplos de Python, Java y 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); ) 

Complejidad

La clasificación de shell es un algoritmo de clasificación inestable porque este algoritmo no examina los elementos que se encuentran entre los intervalos.

Complejidad del tiempo

• Complejidad del peor caso : menor o igual que La complejidad del peor caso para la ordenación del shell es siempre menor o igual que . De acuerdo con el Teorema de Poonen, la complejidad del peor caso para la ordenación de shell es o o o algo intermedio.O(n2)
O(n2)
Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
• Mejor complejidad de caso : O(n*log n)
  cuando la matriz ya está ordenada, el número total de comparaciones para cada intervalo (o incremento) es igual al tamaño de la matriz.
• Complejidad de casos promedio : O(n*log n)
  está alrededor .O(n1.25)

La complejidad depende del intervalo elegido. Las complejidades anteriores difieren para las diferentes secuencias de incremento elegidas. Se desconoce la mejor secuencia de incrementos.

Complejidad espacial:

La complejidad del espacio para la clasificación de conchas es O(1).

Aplicaciones de clasificación de shell

La clasificación de shell se utiliza cuando:

• llamar a una pila es una sobrecarga. La biblioteca uClibc usa este tipo.
• la recursividad supera un límite. El compresor bzip2 lo usa.
• La ordenación por inserción no funciona bien cuando los elementos cercanos están muy separados. La clasificación de conchas ayuda a reducir la distancia entre los elementos cercanos. Por lo tanto, habrá menos intercambios a realizar.