Você está aqui: Java ::: Dicas & Truques ::: Ordenação e Pesquisa (Busca) | 
           
               Java Insertion Sort - Como ordenar um vetor de inteiros usando a ordenação Insertion Sort (Ordenação por Inserção)Quantidade de visualizações: 4923 vezes | 
           
| 
      A ordenação Insertion Sort, Insertion-Sort, ou Ordenação por Inserção, possui uma complexidade de tempo de execução igual à ordenação Bubble Sort (Ordenação da Bolha), ou seja, O(n2). Embora mais rápido que o Bubble Sort, e ser um algorítmo de ordenação quadrática, a ordenação Insertion Sort é bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente entre os algoritmos desta ordem de classificação, porém, nunca recomendada para um grande conjunto de dados. A forma mais comum para o entendimento da ordenação Insertion Sort é compará-la com a forma pela qual algumas pessoas organizam um baralho num jogo de cartas. Imagine que você está jogando cartas. Você está com as cartas na mão e elas estão ordenadas. Você recebe uma nova carta e deve colocá-la na posição correta da sua mão de cartas, de forma que as cartas obedeçam à ordenação. A cada nova carta adicionada à sua mão de cartas, a nova carta pode ser menor que algumas das cartas que você já tem na mão ou maior, e assim, você começa a comparar a nova carta com todas as cartas na sua mão até encontrar sua posição correta. Você insere a nova carta na posição correta, e, novamente, a sua mão é composta de cartas totalmente ordenadas. Então, você recebe outra carta e repete o mesmo procedimento. Então outra carta, e outra, e assim por diante, até não receber mais cartas. Esta é a ideia por trás da ordenação por inserção. Percorra as posições do vetor (array), começando com o índice 1 (um). Cada nova posição é como a nova carta que você recebeu, e você precisa inseri-la no lugar correto no sub-vetor ordenado à esquerda daquela posição. Vamos ver a implementação na linguagem Java agora? Observe o seguinte código, no qual temos um vetor de inteiros com os elementos {4, 6, 2, 8, 1, 9, 3, 0, 11}: ----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------
package arquivodecodigos;
 
public class Estudos{
  // método que permite ordenar o vetor de inteiros
  // usando a ordenação Insertion Sort
  public static void insertionSort(int[] vetor){
    // percorre todos os elementos do vetor começando
    // pelo segundo elemento
    for(int i = 1; i < vetor.length; i++){
      int atual = vetor[i]; // o valor atual a ser inserido
      // começa a comparar com a célula à esquerda de i
      int j = i - 1;
      
      // enquanto vetor[j] estiver fora de ordem em relação
      // a atual
      while((j >= 0) && (vetor[j] > atual)){
        // movemos vetor[j] para a direita e decrementamos j
        vetor[j + 1] = vetor[j];
        j--;
      }
      
      // colocamos atual em seu devido lugar
      vetor[j + 1] = atual;
    }
  }  
    
  public static void main(String args[]){
    // vamos criar um vetor com 9 elementos
    int valores[] = {4, 6, 2, 8, 1, 9, 3, 0, 11};
    
    // exibimos o vetor na ordem original
    System.out.println("Ordem original:\n");
    for(int i = 0; i < valores.length; i++){
      System.out.print(valores[i] + "  ");  
    }
    
    // vamos ordenar o vetor agora
    insertionSort(valores);
    
    // exibimos o vetor ordenado
    System.out.println("\n\nOrdenado:\n");
    for(int i = 0; i < valores.length; i++){
      System.out.print(valores[i] + "  ");  
    }
  }
}
Ao executar este código Java nós teremos o seguinte resultado: Sem ordenação: 4 6 2 8 1 9 3 0 11 Ordenada usando Insertion Sort: 0 1 2 3 4 6 8 9 11  | 
                
| 
                   | 
                
Desafios, Exercícios e Algoritmos Resolvidos de Java  | 
           
Veja mais Dicas e truques de Java  | 
           
Dicas e truques de outras linguagens  | 
           
E-Books em PDF  | 
           ||||
               
               
  | 
           ||||
               
               
  | 
           ||||
Linguagens Mais Populares  | 
           ||||
|     
                
			   1º lugar: Java  | 
           







