Método de Ordenamiento Shell Sort en C#

Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el des elección directa o el de inserción directa.

Sin embargo, es necesario romper una lanza a favor del algoritmo ShellSort, ya que es el mejor algoritmo de ordenación in-situ... es decir, el mejor de aquellos en los que la cantidad de memoria adicional que necesita -aparte de los propios datos a ordenar, claro está- es constante, sea cual sea la cantidad de datos a ordenar. El algoritmo de la burbuja, el de selección directa, el de inserción directa y el de Shell son todos in-situ, y éste último, el de Shell, es el que mejor resultados da, sin ninguna duda de todos ellos y sus posibles variantes.

El ShellSort es una mejora del método de inserción directa que se utiliza cuando el número de elementos a ordenar es grande. El método se denomina “shell” –en honor de su inventor Donald Shell – y también método de inserción con incrementos decrecientes.

En el método de clasificación por inserción, cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es más pequeño - por ejemplo -, hay que ejecutar muchas comparaciones antes de colocarlo en su lugar definitivamente. Shell modifico los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño y con eso se conseguía la clasificación más rápida. El método se basa en fijar el tamaño de los saltos constantes, pero de más de una posición.

Considere un valor pequeño que está inicialmente almacenado en el final del vector. Usando un ordenamiento O(n2) como el ordenamiento de burbuja o el ordenamiento por inserción, tomará aproximadamente n comparaciones e intercambios para mover este valor hacia el otro extremo del vector. El Shell sort primero mueve los valores usando tamaños de espacio gigantes, de manera que un valor pequeño se moverá bastantes posiciones hacia su posición final, con sólo unas pocas comparaciones e intercambios.

Uno puede visualizar el algoritmo Shell sort de la siguiente manera: coloque la lista en una tabla y ordene las columnas (usando un ordenamiento por inserción). Repita este proceso, cada vez con un número menor de columnas más largas. Al final, la tabla tiene sólo una columna.

Mientras que transformar la lista en una tabla hace más fácil visualizarlo, el algoritmo propiamente hace su ordenamiento en contexto (incrementando el índice por el tamaño de paso, esto es usando i += tamaño_de_paso en vez de i++).

Por ejemplo, considere una lista de números como [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 8, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas. Esto quedaría así:

13 14 94 33 82

25 59 94 65 23

45 27 73 25 39

10

Entonces ordenamos cada columna, lo que nos da:

10 14 73 25 23

13 27 94 33 39

25 59 94 65 82

45

Cuando lo leemos de nuevo como una única lista de números, obtenemos:

 [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]

 Aquí, el 10 que estaba en el extremo final, se ha movido hasta el extremo inicial. Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de 3 posiciones, y después un ordenamiento con un espacio de 1 posición (ordenamiento por inserción simple).

El Shell sort lleva este nombre en honor a su inventor, Donald Shell, que lo publicó en 1959. Algunos libros de texto y referencias antiguas le llaman ordenación "Shell-Metzner" por Marlene Metzner Norton, pero según Metzner, "No tengo nada que ver con el algoritmo de ordenamiento, y mi nombre nunca debe adjuntarse a éste."

A continuación veamos un ejemplo en Pseudo-Código Para el Método de Shell Sort

Ejemplo del Método de Ordenamiento Shell Sort en C# 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace PruebaVector

{

    class PruebaVector

    {

        private int[] vector;

        public void Cargar()

        {

            Console.WriteLine("Metodo de Shell Sort");

            Console.Write("Cuantos longitud del vector:");

            string linea;

            linea = Console.ReadLine();

            int cant;

            cant = int.Parse(linea);

            vector = new int[cant];

            for (int f = 0; f < vector.Length; f++)

            {

                Console.Write("Ingrese elemento "+(f+1)+": ");

                linea = Console.ReadLine();

                vector[f] = int.Parse(linea);

            }

        }

        public void Shell()

        {

            int salto = 0;

            int sw = 0;

            int auxi = 0;

            int e = 0;

            salto = vector.Length / 2;

            while (salto > 0)

            {

                sw = 1;

                while (sw != 0)

                {

                    sw = 0;

                    e = 1;

                    while (e <= (vector.Length - salto))

                    {

                        if (vector[e - 1] > vector[(e - 1) + salto])

                        {

                            auxi = vector[(e - 1) + salto];

                            vector[(e - 1) + salto] = vector[e - 1];

                            vector[(e - 1)] = auxi;

                            sw = 1;

                        }

                        e++;

                    }

                }

                salto = salto / 2;

            }

        }

        public void Imprimir()

        {

            Console.WriteLine("Vector ordenados en forma ascendente");

            for (int f = 0; f < vector.Length; f++)

            {

                Console.Write(vector[f]+"  ");

            }

            Console.ReadKey();

        }

        static void Main(string[] args)

        {

            PruebaVector pv = new PruebaVector();

            pv.Cargar();

            pv.Shell();

            pv.Imprimir();

        }

    }

}

Al ejecutar el código muestra el siguiente resultado