package equipo;
public class ShellSort
{
private long[] data;
private int len;
public ShellSort(int max) {
data = new long[max];
len = 0;
}
public void insert(long value)
{
data[len] = value;
len++;
}
public void display()
{
System.out.print("Datos:");
for (int j = 0; j < len; j++)
System.out.print(data[j] + " ");
System.out.println("");
}
public void shellSort()
{
int inner, outer;
long temp;
//find initial value of h
int h = 1;
while (h <= len / 3)
h = h * 3 + 1; // (1, 4, 13, 40, 121, ...)
while (h > 0) // decreasing h, until h=1
{
// h-sort the file
for (outer = h; outer < len; outer++)
{
temp = data[outer];
inner = outer;
// one subpass (eg 0, 4, 8)
while (inner > h - 1 && data[inner - h] >= temp)
{
data[inner] = data[inner - h];
inner -= h;
}
data[inner] = temp;
}
h = (h - 1) / 3; // decrease h
}
}
public static void main(String[] args)
{
int maxSize = 10;
ShellSort arr = new ShellSort(maxSize);
for (int j = 0; j < maxSize; j++)
{
long n = (int) (java.lang.Math.random() * 99);
arr.insert(n);
}
System.out.println("Datos no Ordenados");
arr.display();
arr.shellSort();
arr.display();
}
}
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 de selección directa o el de inserción directa.
Aunque a menudo, es un algoritmo un tanto olvidado por dos motivos: en primer lugar, en los cursos básicos de programación se suele pasar por alto o se pasa "de puntillas" por este algoritmo, dado que su comprensión requiere un cierto esfuerzo y algo de tiempo, y se suele centrar la atención en los tres algoritmos más básicos (burbuja, selección e inserción); y en segundo lugar, el algoritmo QuickSort, desarrollado por Hoare en 1962 puede dar mejores resultados aún que éste, con lo cual, le suele hacer bastante sombra en los temarios de los cursos de programación básicos.
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 algortimo 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.
Video de como funciona Shell Sort...
