Algoritmo de ordenação por inserção com C, C++, Java, Python Exemplos

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

O Insertion Sort é um dos algoritmos de ordenação por comparação usado para ordenar elementos, iterando sobre um elemento de cada vez e colocando-o em sua posição correta dentro de uma região já ordenada.

Cada elemento é inserido sequencialmente em uma lista já ordenada. O tamanho inicial da lista ordenada é um. O algoritmo Insertion Sort garante que os primeiros k elementos estejam ordenados após a k-ésima iteração do laço externo.

Como o Insertion Sort constrói o resultado incrementalmente, é intuitivo de ensinar, fácil de depurar e uma base sólida para entradas muito pequenas, onde algoritmos mais complexos adicionariam sobrecarga sem ganhos mensuráveis.

Características do algoritmo de classificação por inserção

O algoritmo Insertion Sort possui as seguintes características importantes que explicam seu comportamento em cargas de trabalho reais:

• É uma técnica de classificação estável, portanto não altera a ordem relativa de elementos iguais.
• É eficiente para conjuntos de dados menores, mas não é eficaz para listas maiores, onde o crescimento quadrático predomina.
• O Insertion Sort é adaptativo, o que significa que reduz o número total de etapas se a entrada estiver parcialmente ordenada. Ordem é fornecido como entrada para torná-lo eficiente, pois o acesso aleatório permite deslocamentos em tempo constante durante o loop interno.
• Trata-se de um algoritmo in-place, portanto não requer armazenamento auxiliar proporcional ao tamanho da entrada.

Com essas características em mente, a próxima seção explica a operação de inserção principal que alimenta cada iteração do algoritmo.

Como Inserir Operatrabalho?

No algoritmo de ordenação por inserção, a operação de inserção é usada para ordenar elementos não ordenados. Ela permite inserir um novo elemento em uma lista já ordenada, preservando a ordem existente na região já ordenada.

Pseudocódigo da operação de inserção:

Considere uma lista A de N elementos.

// Insert A[N-1] into sorted sublist A[0..N-2]
for i = N-1 to 1:
    if A[i] < A[i-1], then swap A[i] and A[i-1]
    else stop

No exemplo acima, um novo elemento 6 é inserido em uma lista já ordenada. Os passos seguintes são descritos a seguir. trace o laço interno à medida que o novo elemento migra para a esquerda em direção à sua posição correta.

Passo 1) Comparado com o elemento adjacente esquerdo de A[5], 9 > 6, trocamos a posição de 9 e 6. Agora o elemento 6 é movido para A[4].

Passo 2) Agora, comparamos A[4] e A[3], e descobrimos que A[3] > A[4], então trocamos novamente a posição de 6 e 8.

Passo 3) Agora compare A[3] e A[2]. Como A[2] > A[3], trocamos a posição de 7 e 6.

Passo 4) Comparamos A[1] e A[2]. Como A[1] < A[2], o elemento adjacente à esquerda não é mais maior. Concluímos que 6 foi inserido corretamente e interrompemos o loop interno aqui.

Como funciona a classificação por inserção

A operação de inserção discutida acima é a espinha dorsal do Insertion Sort. O procedimento de inserção é executado em cada elemento e, ao final, obtemos a lista ordenada, pois a região ordenada aumenta em um elemento a cada iteração externa.

A figura acima demonstra o funcionamento do Insertion Sort em uma estrutura de dados. Inicialmente, apenas um elemento está na sublista ordenada, ou seja, 4. Após a inserção de A[1], ou seja, 3, o tamanho da sublista ordenada aumenta para 2, e o algoritmo continua esse padrão até que todos os elementos tenham sido inseridos.

Com o fluxo conceitual definido, as seções seguintes mostram implementações concretas em C++, C, e Python Assim, você pode comparar estruturas de loop entre diferentes linguagens.

C++ Programa para classificação por inserção

O C++ A implementação abaixo utiliza dois loops aninhados: o loop externo seleciona o próximo elemento não ordenado e o loop interno o desloca para a esquerda até que a posição correta seja encontrada.

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    return 0;
}

Saída:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

C Code para ordenação por inserção

A mesma lógica se aplica diretamente à linguagem C. O padrão printf As chamadas substituem a saída do fluxo, mas o padrão de troca dentro do loop interno é idêntico ao do C++ versão.

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

Saída:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Python Programa para classificação por inserção

Python suporta troca de tuplasping em uma única expressão, portanto o loop interno é mais compacto do que seu C e C++ contrapartes, mantendo o mesmo comportamento algorítmico.

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

Saída:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Propriedades da classificação por inserção

Aqui estão algumas propriedades importantes do Insertion Sort que ajudam você a decidir quando ele é a ferramenta certa:

• Online: O Insertion Sort pode ordenar os elementos à medida que os recebe. Se já tivermos ordenado uma lista de elementos e adicionarmos mais elementos à lista, não precisamos executar todo o procedimento de ordenação novamente. Em vez disso, iteramos apenas sobre os elementos recém-adicionados.
• No lugar: A complexidade espacial do algoritmo Insertion Sort é constante e não requer espaço adicional. Este algoritmo ordena os elementos no próprio local.
• Estável: Na ordenação por inserção, não trocamos elementos se seus valores forem iguais. Por exemplo, se dois elementos, x e y, são iguais e x aparece antes de y na lista não ordenada, então, na lista ordenada, x ainda aparecerá antes de y. Isso torna a ordenação por inserção estável.
• Adaptável: A algoritmo de classificação Um algoritmo é adaptativo se levar menos tempo quando os elementos de entrada, ou um subconjunto deles, já estiverem ordenados. Como discutimos anteriormente, o melhor tempo de execução do Insertion Sort é O(N) e o pior é O(N²). O Insertion Sort é um dos algoritmos de ordenação adaptativos.

Complexidade da classificação de inserção

A discussão sobre complexidade abaixo abrange tanto o uso de memória quanto o tempo de execução, para que você possa comparar o Insertion Sort com alternativas como... Bubble Classificar e Ordenação rápida.

Complexidade do Espaço

O Insertion Sort não requer espaço extra para ordenar os elementos. A complexidade de espaço é constante, ou seja, O(1), porque apenas algumas variáveis ​​temporárias são usadas, independentemente do tamanho da entrada.

Complexidade de tempo

Como o Insertion Sort itera um elemento por vez, ele requer N-1 passagens para ordenar N elementos. Em cada passagem, ele pode não realizar nenhuma troca se os elementos já estiverem ordenados, ou pode precisar de muitas trocas se os elementos estiverem em ordem decrescente.

• Para a passagem 1, os swaps mínimos exigidos são zero e os swaps máximos exigidos são 1.
• Para a passagem 2, os swaps mínimos exigidos são zero e os swaps máximos exigidos são 2.
• Para a passagem N, a troca mínima exigida é zero e as trocas máximas exigidas são N.
• A troca mínima é zero, então a melhor complexidade de tempo é O(N) para iterar N passagens.
• O número máximo total de trocas é (1+2+3+4+…+N), ou seja, N(N+1)/2, portanto, a complexidade de tempo mais difícil é O(N^2).

Aqui está a complexidade temporal importante do Insertion Sort:

• Complexidade do pior caso: O(n^2): Ordenar um array em ordem decrescente quando ele deveria estar em ordem crescente é o pior cenário possível.
• Melhor complexidade do caso: O(n): O melhor caso ocorre quando o array já está ordenado; o loop externo é executado n vezes, enquanto o loop interno não é executado nenhuma vez. Existem apenas n comparações, portanto a complexidade é linear.
• Complexidade média do caso: O(n^2): Isso acontece quando os elementos da matriz aparecem em uma ordem aleatória que não é nem crescente nem decrescente.

Perguntas Frequentes