Estructura de datos y algoritmos: clasificación de shell

La clasificación de shell es un algoritmo de clasificación altamente eficiente y se basa en un algoritmo de clasificación por inserción. Este algoritmo evita grandes cambios como en el caso de la ordenación por inserción, si el valor más pequeño está en el extremo derecho y debe moverse hacia el extremo izquierdo.

Este algoritmo utiliza la ordenación por inserción en elementos muy extendidos, primero para ordenarlos y luego ordena los elementos menos espaciados. Este espaciado se denomina comointerval. Este intervalo se calcula según la fórmula de Knuth como:

Fórmula de Knuth

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

Este algoritmo es bastante eficiente para conjuntos de datos de tamaño mediano, ya que su complejidad promedio y en el peor de los casos de este algoritmo depende de la secuencia de espacios, la más conocida es Ο (n), donde n es el número de elementos. Y el peor caso de complejidad espacial es O (n).

¿Cómo funciona Shell Sort?

Consideremos el siguiente ejemplo para tener una idea de cómo funciona la ordenación de shell. Tomamos la misma matriz que hemos usado en nuestros ejemplos anteriores. Para nuestro ejemplo y facilidad de comprensión, tomamos el intervalo de 4. Haga una sublista virtual de todos los valores ubicados en el intervalo de 4 posiciones. Aquí estos valores son {35, 14}, {33, 19}, {42, 27} y {10, 44}

Comparamos valores en cada sublista y los intercambiamos (si es necesario) en la matriz original. Después de este paso, la nueva matriz debería verse así:

Luego, tomamos el intervalo de 1 y esta brecha genera dos sublistas: {14, 27, 35, 42}, {19, 10, 33, 44}

Comparamos e intercambiamos los valores, si es necesario, en la matriz original. Después de este paso, la matriz debería verse así:

Finalmente, ordenamos el resto de la matriz usando el intervalo de valor 1. La ordenación de shell usa la ordenación por inserción para ordenar la matriz.

A continuación se muestra la descripción paso a paso:

Vemos que solo requirió cuatro intercambios para ordenar el resto de la matriz.

Algoritmo

A continuación se muestra el algoritmo para la clasificación 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

Pseudocódigo

A continuación se muestra el pseudocódigo para la ordenación 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 conocer la implementación de la clasificación de shell en el lenguaje de programación C, haga clic aquí .