Insertion Sort

Neste algoritmo de ordenação, a partir do segundo elemento do vetor, temos que observar se o elemento em questão é menor do que o(s) elemento(s) anterior(es) e posicioná-lo de acordo com o seu valor. Se for verificado que o elemento é menor do que um elemento que já está ordenado no vetor, todos os elementos a partir deste deverão ser deslocados uma posição à direita para a inclusão deste novo elemento. Este procedimento é realizado até a verificação de todos os elementos.

A troca pode ser feita utilizando um vetor auxiliar, o que aumenta o uso de memória, ou no próprio vetor.

import java.io.*;

import java.util.*;

class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {

       Main processando = new Main();

       processando.processa();

     

       System.exit(0);

    }

   

    static int leitor(BufferedReader br) throws NumberFormatException, IOException {

       int n;

       int resp = 0;

       int sinal = 1;

       while (true) {

           n = br.read();

           if (n >= '0' && n <= '9') break;

           if (n == '-') sinal = -1;

           if (n == '+') sinal = 1;

       }

       while (true) {

           resp = resp*10 + n-'0';

           n = br.read();

           if (n < '0' || n > '9') break;

       }

       return resp*sinal;

    }

   

    void processa() throws NumberFormatException, IOException {

       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

     

       int qteNumeros = leitor(br);

     

       int[] vetor = new int[qteNumeros];

       for (int i = 0; i < qteNumeros; i++) {

           vetor[i] = leitor(br);

       }

     

       for (int i = 0; i < qteNumeros; i++) {

           int valor = vetor[i];

           for (int j = i-1; j >= 0; j--) {

               if (valor < vetor[j]) {

                   vetor[j+1] = vetor[j];

                   vetor[j] = valor;

               }

               else {

                   break;

               }

           }

       }

             

       for (int i = 0; i < qteNumeros; i++) {

           System.out.print(vetor[i] + " ");

       }

       System.out.println();

       return;

    }

}