Classificação por inserção em Java

Classificar arrays é uma das operações mais comuns que um iniciante em Java deve saber fazer. Embora as matrizes nem sempre sejam a maneira mais conveniente de organizar os dados e isso se aplica principalmente a números pequenos, o conceito por trás da classificação de matrizes tem inúmeras aplicações em software complexo e ciência de dados. Neste post, veremos mais de perto o que é classificação por inserção. Incluímos alguns exemplos e problemas práticos para ajudá-lo a entender totalmente esse conceito.

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

Basicamente, a classificação por inserção é um algoritmo que os desenvolvedores usam para organizar sequências de números pequenos. Ele divide todos os valores em duas pilhas - uma classificada e outra não classificada. Um a um, os números da pilha “não classificada” são escolhidos e colocados na ordem certa. Vamos dar uma olhada mais de perto na entrada e na saída da ordenação por inserção:

• Entrada: uma matriz A com elementos numéricos não classificados: A[0,1, n, n-2...].
• Saída: uma matriz contendo os mesmos números, mas totalmente classificados. Este é normalmente referido como B: B[0]B[1]...B[n-1].

Existem várias maneiras de usar a classificação por inserção - aqui estão as mais populares:

• Classificação numérica (ordem crescente): [1, 2, 3, 4, 5]
• Classificação numérica (ordem decrescente): [5, 4, 3, 2, 1]
• Ordenação alfabética: [a, b, c, d]

Observação: se você tiver uma matriz vazia ou um singleton, eles serão considerados classificados por padrão.

Compreendendo a teoria da classificação por inserção

Antes de explorar o código por trás da classificação por inserção, vamos detalhar o algoritmo usando linguagem não técnica. Como mostraremos o código de classificação em ordem crescente, faz sentido explicar o algoritmo passo a passo neste post. Etapa 1. Iterando entre arr[1]e arr[n]onde né um valor numérico geralmente menor que 10. Etapa 2. Compare o elemento escolhido (conhecido como key) com o número anterior na sequência usando o sort()método. Passo 3. Se todos os elementos forem menores que seus sucessores, repita a comparação até encontrar um valor maior. Etapa 4. Troque um valor maior uma posição além do menor para criar uma sequência ordenada. Etapa 5. Repita o processo até obter uma sequência de caracteres classificada

Classificando matrizes primitivas

Como o algoritmo é uma das operações Java mais diretas, mesmo os iniciantes completos não devem ter muitos problemas para implementá-lo. Aqui está um guia passo a passo para classificar uma matriz

1. Declare uma matriz para a classificação

Para começar, vamos criar uma string de valores que posteriormente exibiremos usando Java. Para usar a ordenação por inserção, você precisa criar um array. Para isso, useint[]

int[] arrayA = {10, 14, 20, 30};

2. Use sort_arr para implementar o algoritmo

O método sort_arr é uma das formas mais comuns de implementar a classificação por inserção. Na prática, fica assim:

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. Crie um loop e um iterador

Ao usar um loop no algoritmo de classificação por inserção, os desenvolvedores não precisam repetir a lógica para cada elemento. Embora a criação de loops pareça complexa, é bastante simples - aqui está um exemplo:

for(int i=0; i< sort_arr.length; ++i){

Agora que você tem um loop funcionando, é hora de criar um iterador que classificará todos os elementos na ordem desejada. De agora em diante, nos referiremos ao iterador como " j".

        int j = i;

4. Criando um "loop while"

Quando se trata de classificação por inserção, um loop "while" é essencial para uma nova matriz classificada. Para configurá-lo para uma classificação de inserção de ordem crescente, um desenvolvedor precisa cumprir duas condições:

• O valor atribuído a j tem que ser maior que 0
• O valor atribuído a j-1precisa ser maior que o jíndice

Assim que ambas as condições no loop while forem verdadeiras, o valor da chave do array será igual ao jíndice.

5. Classificando a matriz

Depois de configurar o loop while, os valores je j-1serão trocados até que uma ou ambas as condições no loop while falhem. Da mesma forma, a classificação será repetida para cada valor no loop for até que as condições do loop for também falhem. Veja como o processo de ordenação por inserção funciona na prática:

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

Classificando uma ArrayList

Embora seja importante entender a matemática por trás da classificação por inserção, quando se trata de desenvolvimento de software na vida real, você classificará ArrayLists muito mais do que sequências em matrizes primitivas. Aqui está um guia passo a passo para classificar um ArrayList:

1. Crie uma nova Elementclasse para os itens que pertencem à coleção.

   
   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }
   

2. Dentro de uma coleção, existe um compareTo()método - usaremos isso para comparar os ids de dois elementos.

   
       public int compareTo(Element element) {
           int res = 0;
           if (this.id < element.getId()) {
               res = -1;
           }
           if (this.id > element.getId()) {
               res = 1;
           }
           return res;
       }
   }
   

3. Aplique o algoritmo e crie alguns loops para classificar os objetos ArrayListem vez de compará-los.

   
   public static void insertionSortArrayList(List<element> list) {
       for (int j = 1; j < list.size(); j++) {
           Element current = list.get(j);
           int i = j-1;
           while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
               list.set(i+1, list.get(i));
               i--;
           }
           list.set(i+1, current);
       }
   }
   

4. ArrayListVocê também pode adicionar mais elementos , conforme mostrado abaixo:

   
   List<element> list = new ArrayList<>();
   
   // Create elements w/ IDs 0-24
   for (int i = 0; i < 25; i++) {
       list.add(new Element(i));
   }
   
   // To use insertion sort, shuffle the values
   Collections.shuffle(list);
   

5. Agora é hora de classificar:

   
   // This helps print values before sorting
   list.forEach(e -> System.out.print(e.getId() + ", "));
   
   // Sort the list
   insertionSortArrayList(list);
   
   System.out.println();
   
   // Display a sorted array 
   list.forEach(e -> System.out.print(e.getId() + ", "));
   

6. Agora vamos comparar a entrada e a saída para garantir que não cometemos erros. Aqui está a comparação da string que usamos como exemplo.

   
   4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
   

Problemas práticos de ordenação por inserção

Agora que você já domina esse algoritmo de classificação, é hora de testar suas habilidades teóricas e práticas. Teste teórico nº 1 Você recebeu uma matriz [1, 4, 6, 8] e está adicionando um novo elemento n = 7 a ela. Qual é o número de comparações que você precisará fazer para obter uma sequência ordenada de números? Indique o valor final do índice n na matriz. Teste teórico nº 2 Em uma entrevista de emprego, um líder de equipe pede que você prove que a inserção de classificação é um método ineficiente. Dada uma sequência numérica de [0, 3, 6, 8, 9], qual deve ser a ordem de sua sequência de entrada para maximizar o tempo de execução necessário para a classificação? Problema prático Classifique a matriz [0, 1, 4, 5, 2, 3, 7, 9, 8] em sua ordem crescente usando a classificação por inserção para Java.

Conclusão

O maior desafio em compreender a classificação por inserção é entender como o processo funciona. Depois de pegar o jeito, transformar o modelo em código é moleza. Contanto que você pratique e revise problemas práticos relevantes ao longo do tempo, você melhorará rapidamente sua velocidade de classificação por inserção.