Larback - Retornando conhecimento

Sigam-me os bons - @larback

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

    }

}