Insertion Sort

O Insertion Sort tem como rotina base a inserção ordenada. A ideia é executar várias vezes essa rotina para ordenar um array.

Um array com N elementos no qual os N−1 primeiros elementos estão ordenados, mas o último elemento não está no seu lugar. Isto é, precisamos encaixar o último elemento de forma que a sequência fique ordenada.

O Insertion Sort aplica várias vezes a inserção ordenada para ordenar uma sequência.

Como tudo funciona

Mãos a obra:


    import java.util.ArrayList;
    import java.util.Random;
    import java.util.Scanner;

    public class InsertionSort {

        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);
            }

            insertionSort(lista);

            for (Integer integer : lista) {
                System.out.print(integer + ", ");
                if (cont % 20 == 0) {
                    System.out.println();
                }
                cont++;
            }
        }

        /* ---------------------- Algoritimo De Ordenação ---------------------- */
        
        public static void insertionSort(ArrayList lista) {
            int j, i;
            Integer aux;

            for (i = 1; i < lista.size(); i++) {
                aux = lista.get(i);
                for (j = i - 1; (j >= 0) && (lista.get(j) > aux); j--) {
                    lista.set(j + 1, lista.get(j));
                }
                lista.set(j + 1, aux);
            }

        }
    }

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

Selection Sort	1.000	10.000	500.000	1.000.000
Bom	0.0004833	0.004389	0.0390283	0.1933607
Médio	0.0349028	0.1515631	1409.825029	4072.0237792
Ruim	0.0534072	0.2236758	538.7942957	2188.9588711

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