Algoritmo de classificação por inserção em Java com exemplo de programa

Por: James Hartmann James Hartmann
Hours Atualização do

⚡ Resumo Inteligente

Ordenação por inserção em Java Constrói uma seção ordenada de uma matriz um elemento de cada vez, deslocando os valores maiores para a direita até que cada chave ocupe sua posição correta, tornando-a ideal para conjuntos de dados pequenos.

  • 🔘 Definição: O algoritmo de ordenação por inserção remove um elemento e o insere em seu lugar correto dentro da porção ordenada.
  • ☑️ Processo: A cada iteração, a chave é comparada com os valores anteriores e os valores maiores são deslocados uma posição para a direita.
  • ✅ Programa: O Java O exemplo ordena {860, 8, 200, 9} e imprime cada comparação e troca.
  • 🧪 Complexidade: O melhor caso tem um tempo de execução O(n), enquanto os casos médio e pior atingem O(n²).
  • 🛠️ Memória: A ordenação ocorre no mesmo local, portanto o espaço auxiliar permanece em O(1) para qualquer tamanho de matriz.
  • 📊 Comportamento: O algoritmo é estável e adaptativo, de modo que arrays quase ordenados terminam após pouquíssimas alterações.
Saiba Mais

Algoritmo de classificação por inserção em Java

O que é algoritmo de classificação por inserção?

A classificação por inserção é um algoritmo de classificação simples adequado para pequenos conjuntos de dados. Durante cada iteração, o algoritmo:

  • Remove um elemento de uma matriz.
  • Compara-o com o maior valor do ordem.
  • Move o elemento para seu local correto.

O comportamento espelha a maneira como um jogador de cartas organiza sua mão: cada nova carta é selecionada e empurrada para a esquerda, passando por todas as cartas maiores, até ficar na posição correta. Como todos os deslocamentos ocorrem dentro do array original, o algoritmo de ordenação por inserção é tanto in-place quanto estável.

Pertence à mesma família de jogos fáceis para iniciantes. Java rotinas de classificação como Tipo de bolha, no entanto, normalmente realiza muito menos gravações em dados que já estão parcialmente ordenados.

Processo de algoritmo de classificação por inserção

Aqui está como o processo do algoritmo de classificação por inserção funciona graficamente:

Animado trace do algoritmo de ordenação por inserção reordenando uma lista não ordenada
Processo de algoritmo de classificação por inserção

A animação repete os mesmos três passos. Java O programa abaixo executa a seguinte ação: Tabela de teste traces esses passos no array de exemplo {860, 8, 200, 9}, exatamente como o programa os imprime em tempo de execução.

Passar Elemento chave Comparações realizadas Matriz após a passagem
1 8 8 contra 860 8 860 200 9
2 200 200 contra 860 8 200 860 9
3 9 9 contra 860, depois 9 contra 200 8 9 200 860

Observe que a passagem 3 requer duas comparações porque a chave 9 precisa passar por dois valores maiores. O número de comparações, portanto, aumenta com o quão fora de ordem cada elemento começa.

Java Exemplo de programa para classificar um array usando o algoritmo de classificação por inserção:

O programa abaixo ordena o array {860, 8, 200, 9} e imprime um comentário em tempo real, de forma que cada comparação e cada deslocamento sejam visíveis. Salve-o como InsertionSortExample.java e compile-o com qualquer versão do JDK 8 ou posterior.

package com.guru99;
 
public class InsertionSortExample {
 
	
    public static void main(String a[])
    {    
        int[] myArray  = {860,8,200,9};  
        
        System.out.println("Before Insertion Sort");  
        
        printArray(myArray);
            
        insertionSort(myArray);//sorting array using insertion sort    
           
        System.out.println("After Insertion Sort");  
        
        printArray(myArray);   
    }    
 public static void insertionSort(int arr[]) 
	{  
        int n = arr.length;  
        
        for (int i = 1; i < n; i++)
        {   System.out.println("Sort Pass Number "+(i));
            int key = arr[i];  
            int j = i-1;  
            
            while ( (j > -1) && ( arr [j] > key ) ) 
            {  
            System.out.println("Comparing "+ key  + " and " + arr [j]); 
                arr [j+1] = arr [j];  
                j--;  
            }  
            arr[j+1] = key; 
            System.out.println("Swapping Elements: New Array After Swap");
            printArray(arr);
        }  
    }
 static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
}

Executar a classe produz o trace mostrado aqui. Cada um Número de Passe de Classificação A linha marca uma iteração do loop externo, e a linha impressa após cada troca mostra o array como ele está naquele momento.

Code Saída:

Before Insertion Sort
860 8 200 9 
Sort Pass Number 1
Comparing 8 and 860
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 200 860 9 
Sort Pass Number 3
Comparing 9 and 860
Comparing 9 and 200
Swapping Elements: New Array After Swap
8 9 200 860 
After Insertion Sort
8 9 200 860

ARTIGOS RELACIONADOS

Complexidade de tempo e espaço da ordenação por inserção

O desempenho do Insertion Sort depende muito do grau de ordenação inicial da entrada, razão pela qual o melhor e o pior caso diferem em uma ordem de grandeza de crescimento.

Casos Condição de entrada Complexidade do tempo
melhor O array já está ordenado, então o loop while interno nunca é executado. O (n)
Média Os elementos chegam em ordem aleatória. O (n²)
o pior O array está ordenado em ordem inversa, então cada chave vai para o início. O (n²)

O aproveitamento do espaço é muito mais simples. Apenas as bancadas i, j, n e key são criados e a matriz é reorganizada no local, portanto o espaço auxiliar é O(1) não importa o quão grande a entrada se torne.

Como o laço interno para assim que encontra um valor menor, o algoritmo de ordenação por inserção é descrito como adaptativo: quanto mais próxima a entrada estiver da ordem de classificação, mais o tempo de execução se aproxima da linearidade.

Vantagens e desvantagens da ordenação por inserção

O algoritmo de ordenação por inserção (insertion sort) sobrevive em bibliotecas de produção apesar de seu caso médio ser quadrático, porque seus fatores constantes são minúsculos e seu comportamento é previsível.

Vantagens

  • Simples de escrever e fácil de trace à mão, o que a torna adequada para o ensino e para entrevistas.
  • Estável, de forma que os registros que compartilham uma chave mantenham sua ordem relativa original.
  • In-place, necessitando apenas de O(1) de memória extra além do array de entrada.
  • Adaptativo, atingindo O(n) em dados que já estão quase ordenados.
  • Online, o que significa que pode classificar uma lista enquanto novos elementos ainda estão chegando.

Desvantagens

  • O tempo de processamento quadrático em entradas aleatórias ou em ordem inversa torna esse método inadequado para grandes matrizes.
  • Cada operação de deslocamento escreve no array, portanto, move mais dados do que a ordenação por seleção.
  • Os algoritmos de ordenação por intercalação (merge sort) e ordenação rápida (quicksort) superam-no com folga quando a entrada ultrapassa algumas dezenas de elementos.

Uma regra prática é recorrer ao algoritmo de ordenação por inserção quando o array é pequeno, quando os dados estão quase em ordem ou quando uma ordenação por divisão e conquista reduziu uma partição a um pequeno número de elementos.

Ordenação por Inserção vs. Bubble Sort vs Selection Sort

Os três algoritmos são algoritmos de ordenação por comparação quadrática, mas diferem em estabilidade, na forma como reagem a entradas ordenadas e no número de escritas que realizam.

Critérios Ordem de inserção Bubble Classificar Ordem de Seleção
Melhor caso O (n) O(n) com um sinalizador de saída antecipada O (n²)
Caso médio e pior caso O (n²) O (n²) O (n²)
Espaço extra O (1) O (1) O (1)
Estável Sim Sim Não, na versão de matriz padrão.
Adaptativo Sim Sim, quando a otimização de sinalizadores é usada. Não
Escreve no array Muitas mudanças, poucas em dados ordenados Muitas trocas Exatamente n-1 trocas

O Selection Sort vence quando uma operação de escrita é custosa, pois realiza o menor número de trocas. O Insertion Sort vence em quase todos os outros casos nessa escala, especialmente em dados parcialmente ordenados, razão pela qual existem algoritmos de ordenação de biblioteca como o que está por trás do algoritmo. comum Java exercícios e os mecanismos internos do JDK alternam para ele em partições muito pequenas.

Perguntas Frequentes

O primeiro elemento, por si só, já é um subvetor ordenado de comprimento um. Começar no índice 1 significa que o loop sempre tem algo com que comparar, então a chave na posição i é inserida no bloco ordenado à sua esquerda.

Assistentes de IA podem narrar uma simulação linha por linha, gerar matrizes de teste adicionais e estimar o crescimento da notação Big O a partir do código-fonte. Considere a explicação como um auxílio de estudo e confirme as afirmações sobre a complexidade consultando um livro didático antes de citá-las.

Sim. Travas deslizantes portáteis Copiloto do GitHub Executa uma ordenação por inserção padrão a partir da assinatura ou comentário de um método. RevVeja você mesmo as condições de contorno, pois os loops gerados às vezes usam j >= 0 ou j > -1 de forma inconsistente com o código ao redor.

A ordenação por inserção binária localiza o ponto de inserção com uma busca binária em vez de uma varredura linear, reduzindo as comparações por elemento de O(n) para O(log n). O trabalho de deslocamento permanece inalterado, portanto a complexidade de tempo geral permanece O(n²).

Sim. Uma versão recursiva ordena os primeiros n-1 elementos e, em seguida, insere o último elemento nesse prefixo ordenado. Ela tem a mesma complexidade de tempo da versão iterativa, mas adiciona espaço de pilha O(n), portanto, a versão com laço é preferida na prática.

Em parte. O algoritmo Quicksort de pivô duplo, usado para tipos primitivos, recorre a uma ordenação por inserção em partições muito pequenas, e o TimSort, usado para objetos, ordena sequências curtas com ordenação por inserção binária antes de mesclá-las.

Os erros frequentes são iniciar o loop externo em 0, escrever arr[j] = key em vez de arr[j+1] = key e omitir a verificação j > -1, que lança ArrayIndexOutOfBoundsException quando a chave pertence à posição zero.

Sim. Substitua o teste "maior que" por `compareTo` para um tipo `Comparable`, ou por uma chamada a `Comparator`. A lógica de deslocamento permanece inalterada e a estabilidade é preservada, o que é importante quando os objetos compartilham a mesma chave de classificação.

Resuma esta postagem com: