Shell Sort

Criado por Donald Shell em 1959,publicado pela Universidade de Cincinnati, Shell sort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta.

O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles.

Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção. Implementações do algoritmo.

Como tudo funciona

Mãos a obra:


    import java.util.ArrayList;
    import java.util.Random;
    import java.util.Scanner;
    
    public class ShellSort {
    
        public static void main(String[] args) {
            Scanner leia = new Scanner(System.in);
            ArrayList lista = new ArrayList<>();
            int cont = 1;
    
            for (int i = 0; i < 1000; i++) {
                Random rand = new Random();
                int n = rand.nextInt(1000);
                lista.add(n);
            }
    
            shellSort(lista);
    
            for (Integer integer : lista) {
                System.out.print(integer + ", ");
                if (cont % 20 == 0) {
                    System.out.println();
                }
                cont++;
            }
        }
    
        /* ---------------------- Algoritimo De Ordenação ---------------------- */
        private static void shellSort(ArrayList lista) {
            int i, j, h = 1, aux;
    
            do {
                h = 3 * h + 1;
            } while (h < lista.size());
            do {
                h = h / 3;
                for (i = h; i < lista.size(); i++) {
                    aux = lista.get(i);
                    j = i - h;
                    while (j >= 0 && aux < lista.get(j)) {
                        lista.set(j + h, lista.get(j));
                        j = j - h;
                    }
                    lista.set(j + h, aux);
                }
            } while (h > 1);
        }
    }

Tempo de execução(em segundos) VS Qtd de nº no Array:

Shell Sort	1.000	10.000	500.000	1.000.000
Bom	0.002998	0.0406803	0.2290975	0.3457995
Médio	0.0059424	0.0371491	0.6072589	1.1689568
Ruim	0.0037655	0.0034402	0.2805287	0.2654818

*A tabela representa a quantidade de numros utilizadas e o tempo de execução o processo de ordenação