Gnome Sort

Algoritmo similiar ao Insertion sort com a diferença que o Gnome sort leva um elemento para sua posição correta, com uma seqüencia grande de trocas assim como o Bubble sort

algoritmo percorre o vetor comparando seus elementos dois a dois, assim que ele encontra um elemento que está na posição incorreta, ou seja, um número maior antes de um menor, ele troca a posição dos elementos, e volta com este elemento até que encontre o seu respectivo lugar.

Como tudo funciona

Mãos a obra:


    import java.util.ArrayList;
    import java.util.Random;
    import java.util.Scanner;
    
    public class GnomeSort {
    
        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);
            }
    
            gnomeSort(lista, lista.size());
    
            for (Integer integer : lista) {
                System.out.print(integer + ", ");
                if (cont % 20 == 0) {
                    System.out.println();
                }
                cont++;
            }
        }
    
        /* ---------------------- Algoritimo De Ordenação ---------------------- */
        static void gnomeSort(ArrayList lista, int size) {
            int index = 0;
    
            while (index < size) {
                if (index == 0) {
                    index++;
                }
                if (lista.get(index) >= lista.get(index - 1)) {
                    index++;
                } else {
                    int temp = 0;
                    temp = lista.get(index);
                    lista.set(index, lista.get(index - 1));
                    lista.set(index - 1, temp);
                    index--;
                }
            }
        }
    }

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

Gnome Sort	1.000	10.000	500.000	1.000.000
Bom	0.0002855	0.0033286	0.0349889	0.0491664
Médio	0.0557882	1.7405212	3230.6410174	22408.106589
Ruim	0.0461259	2.2670075	3103.5219037	13875.323045

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