Larback - Retornando conhecimento

Oitenta por cento do exame final que você prestará, será baseado na única aula que você perdeu.

Ordenando vetores com Insertion Sort em Java

Insertion Sort, ou ordenação por inserção, é o algoritmo de ordenação que, dado uma estrutura (array, lista) constrói uma matriz final com um elemento de cada vez, uma inserção por vez. Assim como algoritmos de ordenação quadrática, é bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente entre os algoritmos desta ordem de classificação.

Podemos fazer uma comparação do Insertion Sort com o modo de como 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 a ordenação.

A cada nova carta adicionada a 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, 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é você não receber mais cartas.

Esta é a ideia por trás da ordenação por inserção. Percorra as posições do 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 subarray ordenado à esquerda daquela posição.
 public static void insertionSort(int []a){
        int el,j;
        for (int i=1;i<a.length;i++){
            el = a;
            j=i-1;
            while (j>=0 && el < a[j]){
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = el;
        }
              
    }
Agora, para os mais preguiçosos, uma classe completa para testes:
/**
 *
 * @author larback
 */
import java.util.Random;

public class InsertionSort {
    public static void gerar(int [] a, int limite){
        Random gerador = new Random();
        for (int i=0; i<a.length; i++){
            a = gerador.nextInt(limite);
        }
    }    
    public static void mostrar(int [] a){
        for (int i=0; i<a.length; i++)
            System.out.print (a+ " ");
        System.out.println("");
    }
    public static void insertionSort(int []a){
        int el,j;
        for (int i=1;i<a.length;i++){
            el = a;
            j=i-1;
            while (j>=0 && el < a[j]){
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = el;
        }
              
    }
    
    public static void main(String[] args){
        int []v = new int[10];
        gerar(v,100);
        System.out.println("Vetor original");
        mostrar(v);
        insertionSort(v);
        System.out.println("Vetor ordenado");
        mostrar(v);

    }

}