Algoritmo Insertion Sort em Java: Exemplo Claro e Guia Passo a Passo

O que é o Algoritmo Insertion Sort?

Insertion sort é uma técnica de ordenação direta ideal para conjuntos de dados pequenos ou quase ordenados. Em cada iteração, o algoritmo remove um elemento, compara com os elementos precedentes e o coloca em sua posição adequada.

Insertion sort opera em tempo O(n²) nos piores e casos médios, mas atinge desempenho linear quando o array já está ordenado. É uma ordenação in-place, estável, que requer apenas espaço extra constante.

Processo do Algoritmo Insertion Sort

Aqui está uma representação visual do fluxo de trabalho do insertion sort:

Processo do Algoritmo Insertion Sort

Exemplo de Programa Java para Ordenar Array usando Insertion Sort:

package com.guru99;
public class InsertionSortExample {
    public static void main(String a[]) {
        int[] myArray = {860,8,200,9};
        System.out.println("Antes do Insertion Sort");
        printArray(myArray);
        insertionSort(myArray);//ordenando array usando insertion sort
        System.out.println("Depois do Insertion Sort");
        printArray(myArray);
    }

    public static void insertionSort(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            System.out.println("Passagem de Ordenação Número "+(i));
            int key = arr[i];
            int j = i-1;
            while ( (j > -1) && ( arr [j] > key ) ) {
                System.out.println("Comparando "+ key + " e " + arr [j]);
                arr [j+1] = arr [j];
                j--;
            }
            arr[j+1] = key;
            System.out.println("Trocando Elementos: Novo Array Após Troca");
            printArray(arr);
        }
    }

    static void printArray(int[] array){
        for(int i=0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

Saída do Código:

Antes do Insertion Sort
860 8 200 9
Passagem de Ordenação Número 1
Comparando 8 e 860
Trocando Elementos: Novo Array Após Troca
8 860 200 9
Passagem de Ordenação Número 2
Comparando 200 e 860
Trocando Elementos: Novo Array Após Troca
8 200 860 9
Passagem de Ordenação Número 3
Comparando 9 e 860
Comparando 9 e 200
Trocando Elementos: Novo Array Após Troca
8 9 200 860
Depois do Insertion Sort
8 9 200 860