Classificação por inserção: algoritmo com C, C++, Java, Python Exemplos
Sarah Chen
O que é classificação por inserção?
A classificação por inserção é um dos algoritmos de classificação por comparação usados para classificar elementos, iterando um elemento por vez e colocando o elemento em sua posição correta.
Cada elemento é inserido sequencialmente em uma lista já ordenada. O tamanho da lista já ordenada inicialmente é um. O algoritmo de classificação por inserção garante que os primeiros k elementos sejam classificados após a k-ésima iteração.
Características do algoritmo de classificação por inserção
O Algoritmo para Classificação por Inserção possui as seguintes características importantes:
- É 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.
- A classificação por inserção é adaptativa, o que reduz seu número total de etapas se for parcialmente classificada. Ordem é fornecido como entrada para torná-lo eficiente.
Como Inserir Operatrabalho?
No algoritmo Insertion Sort, a operação de inserção é usada para classificar elementos não classificados. Ajuda inserir um novo elemento em uma lista já classificada.
Pseudocódigo da operação de inserção:
Considere uma lista A de N elementos.
A[N-1] is the element to be inserted in the 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 deve ser inserido em uma lista já ordenada.
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], trocamos novamente as posições de 6 e 8.
Passo 3) Agora compare A[3] e A[2], pois A[2] > A[3] troca a posição de 7 e 6.
Passo 4) Comparamos A[1] e A[2], e como A[1] < A[2], ou seja, o elemento adjacente à esquerda não é mais maior. Agora concluímos que 6 está inserido corretamente e paramos o algoritmo aqui.
Como funciona a classificação por inserção
A operação de inserção discutida acima é a espinha dorsal da classificação por inserção. O procedimento de inserção é executado em cada elemento e, no final, obtemos a lista ordenada.
A figura do exemplo acima demonstra o funcionamento da classificação por inserção na estrutura de dados. Inicialmente, apenas um elemento existe na sublista classificada, ou seja, 4. Após inserir A [1], ou seja, 3, o tamanho da sublista classificada aumenta para 2.
C++ Programa para classificação por inserção
#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ódigo C para classificação por inserçã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
#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 propriedades importantes da classificação por inserção:
- Online: A classificação por inserção pode classificar os elementos à medida que os recebe. Ou seja, se já classificamos uma lista de elementos e acrescentamos mais alguns elementos às listas, não precisamos executar todo o procedimento de classificação novamente. Em vez disso, precisamos iterar apenas nos elementos recém-adicionados.
- No lugar: A complexidade de espaço do algoritmo de classificação por inserção é constante e não requer espaço extra. Este algoritmo classifica os elementos no lugar.
- Estável: Na classificação por inserção, não trocamos os elementos se seus valores forem iguais. Por exemplo, dois elementos, x e y, são iguais e x aparece antes de y em listas não classificadas; então, na lista classificada, x aparecerá antes de y. Isso torna a classificação por inserção estável.
- Adaptável: A algoritmo de classificação é adaptativo se levar menos tempo se os elementos de entrada ou subconjunto de elementos já estiverem classificados. Como discutimos acima, o melhor tempo de execução da classificação por inserção é O(N) e o pior tempo de execução é O(N^2). A classificação por inserção é um dos algoritmos de classificação adaptativa.
Complexidade da classificação de inserção
Complexidade do Espaço
A ordenação por inserção não requer espaço extra para ordenar os elementos, a complexidade do espaço é constante, ou seja, O(1).
Complexidade de tempo
Como a classificação por inserção itera cada elemento simultaneamente, são necessárias N-1 passagens para classificar N elementos. Para cada passagem, ele pode fazer zero trocas se os elementos já estiverem ordenados, ou trocar se os elementos estiverem organizados 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 total máximo de swaps é (1+2+3+4+..+N) i. N(N+1)/2, a pior complexidade de tempo é O(N^2).
Aqui está a importante complexidade de tempo da classificação por inserção:
- Complexidade do pior caso: O (n2): Classificar um array em ordem decrescente quando ele está em ordem crescente é o pior cenário.
- Melhor complexidade do caso: O(n): Melhor Case Complexity ocorre quando o array já está ordenado, o loop externo é executado por n número de vezes enquanto o loop interno não é executado. Há apenas n número de comparações. Então, neste caso, a complexidade é linear.
- Complexidade média do caso: O (n2): Acontece quando os elementos de um array ocorrem em ordem confusa, que não é crescente nem decrescente.
Resumo
- A classificação por inserção é um método de algoritmo de classificação baseado na comparação.
- É uma técnica de classificação estável, portanto não altera a ordem relativa de elementos iguais.
- Em cada elemento, a operação de inserção é usada para inserir o elemento na sublista classificada.
- A classificação por inserção é um algoritmo de classificação local.
- A pior e média complexidade de tempo da ordenação por inserção é quadrática, ou seja, O(N^2).
- A classificação por inserção não requer nenhum espaço auxiliar.
