Método Shell de Ordenación

El método de ordenación Shell debe su nombre a su inventor, Donald Shell, y fue uno de los primeros algoritmos de ordenamiento en romper la barrera del tiempo cuadrático.
Es una mejora del método de inserción directa, utilizado cuando el array tiene un gran número de elementos.
Cualquier algoritmo de ordenación que intercambia elementos adyacentes (como los algoritmos burbuja, selección o inserción) tiene un tiempo promedio de ejecución de orden cuadrático (n2). El método Shell mejora este tiempo comparando cada elemento con el que está a un cierto número de posiciones llamado salto, en lugar de compararlo con el el que está justo a su lado. Este salto es constante, y su valor inicial es N/2 (siendo N el número de elementos, y siendo división entera).
Se van dando pasadas con el mismo salto hasta que en una pasada no se intercambie ningún elemento de sitio. Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1.
El método Shell de ordenación en Java para ordenar un array A de enteros es el siguiente:
public static void shell(int A[]) {

        int salto, aux, i;
        boolean cambios;
  
        for (salto = A.length / 2; salto != 0; salto /= 2) {
            cambios = true;
            while (cambios) {   // Mientras se intercambie algún elemento                                         
                cambios = false;
                for (i = salto; i < A.length; i++)   // se da una pasada
                {
                    if (A[i - salto] > A[i]) {       // y si están desordenados
                        aux = A[i];                  // se reordenan
                        A[i] = A[i - salto];
                        A[i - salto] = aux;
                        cambios = true;              // y se marca como cambio.                                   
                    }
                }
            }
        }
}
Ejemplo de ejecución:

Con sólo 6 intercambios se ha ordenado el array, cuando por inserción se necesitaban muchos más. El rendimiento del método Shell de ordenación es bastante aceptable, aún para el caso de un número de elementos muy grande. Se ha comprobado que el tiempo de ejecución promedio es de O(n2/3) para la mayoría de las secuencias de salto.

10 comentarios:

  1. Cómo muestro la información del ordenado en consola?

    ResponderEliminar
    Respuestas
    1. static void Impresion (int[] numeros){
      for (int i = 0; i < numeros.length; i++) {
      System.out.println("["+numeros[i]+"]");
      }
      }

      Eliminar
  2. Utiliza otro for

    for(int i=0;i<A.lenght;i++){
    sout(A[i]);
    }

    ResponderEliminar
  3. disculpa como lo arias de modo gráfico me puede ayudar?

    ResponderEliminar
    Respuestas
    1. yo lo hice de forma grafica

      Eliminar
    2. public void shell() {
      int salto, aux, i; //variables
      it=transformar(); //it se convierte en el metodo transformar
      Imprimir();
      boolean cambios;
      //bucle for para poder leer los datos ingresados
      for (salto = it.length / 2; salto>0;salto=salto==2 ? 1 : (int)(salto / 2.2));{
      //bucle para poder
      for (salto = it.length / 2; salto != 0; salto /= 2) {
      cambios = true;
      while (cambios) { // Mientras se intercambie algún elemento
      cambios = false;
      for (i = salto; i < it.length; i++) // se da una pasada
      {
      if (it[i - salto] > it[i]) { // y si están desordenados
      aux = it[i]; // se reordenan
      it[i] = it[i - salto];
      it[i - salto] = aux;
      cambios = true; // y se marca como cambio.
      Imprimir();
      }
      }
      }
      }
      }
      }

      Eliminar
  4. Como se cuantos intercambio y comparaciones han echo?

    ResponderEliminar
  5. me pueden ayudar con este programa... Un array contiene los elementos indicados más abajo. Utilizando el algoritmo de

    ordenación Shell, encuentre las pasadas y los intercambios que se realizan para su

    ordenación.
    8 43 17 6 40 16 18 97 11 7

    ResponderEliminar