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 (n²). 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(n^2/3) para la mayoría de las secuencias de salto.

Como ordenar arrays en Java. Método Arrays.sort()

Arrays.Sort() - Collections.reverseOrder()

Para ordenar arrays de cualquier tipo Java dispone del método sort de la clase Arrays.

Para utilizarlo es necesario incluir el import:

import java.util.Arrays;

Por ejemplo, dado el siguiente array de Strings:

String [] nombres = {"juan", "pedro", "ana", "maria", "felipe", "luis", "eduardo"};

para ordenarlo de forma ascendente escribiremos la instrucción:

Arrays.sort(nombres);

Si mostramos el array por pantalla, comprobaremos que está ordenado de forma ascendente:

for(String s : nombres)
    System.out.println(s);

Arrays.sort ordena de forma ascendente (de menor a mayor). Para ordenar un array de forma descendente (de mayor a menor) hay que indicarlo utilizando el método reverseOrder() de la clase Collections.

Para utilizar reverseOrder es necesario incluir el import:

import java.util.Collections;

Por ejemplo, para ordenar el array nombres de forma descendente escribimos la instrucción Arrays.sort de la siguiente forma:

Arrays.sort(nombres, Collections.reverseOrder());

También tenemos la opción de ordenar solo una parte del array, indicando la posición del elemento inicial y la del elemento final (que no se incluye en la ordenación).

Por ejemplo, para ordenar solo los elementos 1, 2 y 3 ("pedro", "ana", "maria") del array nombres escribimos la instrucción de esta forma:

Arrays.sort(nombres, 1, 4);

El 1 indica la posición del elemento donde comienza la ordenación y el 4 indica la posición del primer elemento que no entra en la ordenación.

El contenido del array después de esta ordenación es el siguiente:

juan

ana

maria

pedro

felipe

luis

eduardo

vemos que solo se han ordenado los elementos 1, 2 y 3. El resto quedan igual:

También podemos ordenar solo una parte del array en orden inverso. Por ejemplo, para ordenar solo los elementos 1, 2 y 3 en orden inverso:

Arrays.sort(nombres, 1,4, Collections.reverseOrder());

El contenido del array es ahora:

juan

pedro

maria

ana

felipe

luis

eduardo

Con Arrays.sort podemos ordenar arrays de cualquier tipo de datos. Por ejemplo, para ordenar un array de enteros:

int [] numeros = {3, 5, 1, 2, 1, 7, 0, -1};
Arrays.sort(numeros);                                                                                             
//mostrarlo ordenado
for (int n : numeros) {
     System.out.println(n);                                                                                       
}

Collections.reverOrder() solo funciona para arrays de objetos. Por este motivo si queremos ordenar de forma descendente arrays de tipos de datos simples debemos utilizar la clase envolvente equivalente al tipo de dato básico. Puedes ver las clases envolventes que corresponden a cada tipo de dato en esta entrada.

Por ejemplo, para ordenar un array de enteros forma descendente hay que declararlo de tipo Integer en lugar de int.

Integer [] numeros = {3, 5, 1, 2, 1, 7, 0, -1};
Arrays.sort(numeros, Collections.reverseOrder());                                                                 
for (int n : numeros) {
       System.out.println(n);                                                                                     
}