Considere os seguintes números:
50 60 30 10 80 70 20 40
Se esta lista for classificada em ordem crescente, seria:
10 20 30 40 50 60 70 80
Se estiver ordenado em ordem decrescente, seria:
80 70 60 50 40 30 20 10
A classificação por inserção é um algoritmo de classificação usado para classificar a lista em ordem crescente ou decrescente. Este artigo trata apenas da classificação em ordem crescente. A classificação em ordem decrescente segue a mesma lógica apresentada neste documento. O objetivo deste artigo é explicar a ordenação por inserção. A programação é feita no exemplo a seguir em C. A ordenação por inserção é explicada aqui usando um array.
Algoritmo para Ordenação por Inserção
Uma lista não classificada é fornecida. O objetivo é ordenar a lista em ordem crescente usando a mesma lista. Classificar um array não classificado usando o mesmo array é chamado de ordenação no local. A indexação baseada em zero é usada aqui. Os passos são os seguintes:
-
- A lista é verificada desde o início.
- Enquanto a varredura está em andamento, qualquer número menor que seu antecessor é trocado por seu antecessor.
- Essa troca continua ao longo da lista, até que não seja mais possível trocar.
- Quando a digitalização chega ao fim, a classificação está concluída.
Ilustração de classificação por inserção
Ao lidar com complexidade de tempo, é o pior caso que normalmente é levado em consideração. O pior arranjo para a lista anterior é:
80 70 60 50 40 30 20 10
São oito elementos com índices de zero a 7.
No índice zero, a varredura vai para 80. Este é um movimento. Este movimento é uma operação. Há um total de uma operação até agora (um movimento, sem comparação e sem troca). O resultado é:
| 80 70 60 50 40 30 20 10
No índice um, há um movimento para 70. 70 é comparado com 80. 70 e 80 são trocados. Um movimento é uma operação. Uma comparação é também uma operação. Uma troca também é uma operação. Esta seção fornece três operações. Há um total de quatro operações até agora (1 + 3 = 4). O resultado é o seguinte:
70 | 80 60 50 40 30 20 10
No índice dois, há um movimento para 60. 60 é comparado com 80, então 60 e 80 são trocados. 60 é comparado com 70, então 60 e 70 são trocados. Um movimento é uma operação. Duas comparações são duas operações. Dois swaps são duas operações. Esta seção fornece cinco operações. Há um total de nove operações até agora (4 + 5 = 9). O resultado é o seguinte:
60 70 | 80 50 40 30 20 10
No índice três, há um movimento para 50. 50 é comparado com 80, então 50 e 80 são trocados. 50 é comparado com 70, então 50 e 70 são trocados. 50 é comparado com 60, então 50 e 60 são trocados. Um movimento é uma operação. Três comparações são três operações. Três swaps são três operações. Esta seção fornece sete operações. Há um total de dezesseis operações até agora (9 + 7 = 16). O resultado é o seguinte:
50 60 70 | 80 40 30 20 10
No índice quatro, há um movimento para 40. 40 é comparado com 80, então 40 e 80 são trocados. 40 é comparado com 70, então 40 e 70 são trocados. 40 é comparado com 60, então 40 e 60 são trocados. 40 é comparado com 50, então 40 e 50 são trocados. Um movimento é uma operação. Quatro comparações são quatro operações. Quatro swaps são quatro operações. Esta seção fornece nove operações. Há um total de vinte e cinco operações até agora (16 + 9 = 25). O resultado é o seguinte:
40 50 60 70 80 | 30 20 10
No índice cinco, há um movimento para 30. 30 é comparado com 80, então 30 e 80 são trocados. 30 é comparado com 70, então 30 e 70 são trocados. 30 é comparado com 60, então 30 e 60 são trocados. 30 é comparado com 50, então 30 e 50 são trocados. 30 é comparado com 40, então 30 e 40 são trocados. Um movimento é uma operação. Cinco comparações são cinco operações. Cinco swaps são cinco operações. Esta seção fornece onze operações. Há um total de trinta e seis operações até agora (25 + 11 = 36). O resultado é o seguinte:
30 40 50 60 70 80 | 20 10
No índice seis, há um movimento para 20. 20 é comparado com 80, então 20 e 80 são trocados. 20 é comparado com 70, então 20 e 70 são trocados. 20 é comparado com 60, então 20 e 60 são trocados. 20 é comparado com 50, então 20 e 50 são trocados. 20 é comparado com 40, então 20 e 40 são trocados. 20 é comparado com 30, então 20 e 30 são trocados. Um movimento é uma operação. Seis comparações são seis operações. Seis swaps são seis operações. Esta seção fornece treze operações. Há um total de quarenta e nove operações até agora (36 + 13 = 49). O resultado é o seguinte:
20 30 40 50 60 70 80 | 10
No índice sete, há um movimento para 10. 10 é comparado com 80, então 10 e 80 são trocados. 10 é comparado com 70, então 10 e 70 são trocados. 10 é comparado com 60, então 10 e 60 são trocados. 10 é comparado com 50, então 10 e 50 são trocados. 10 é comparado com 30, então 10 e 40 são trocados. 10 é comparado com 30, então 10 e 30 são trocados. 10 é comparado com 20, então 10 e 20 são trocados. Um movimento é uma operação. Sete comparações são sete operações. Sete swaps são sete operações. Esta seção fornece quinze operações. Há um total de sessenta e quatro operações até agora (49 + 15 = 64). O resultado é o seguinte:
10 20 30 40 50 60 70 80 10 |
O trabalho está feito! 64 operações foram envolvidas.
64 = 8 x 8 = 8 dois
Complexidade de tempo para classificação por inserção
Se houver n elementos para ordenar com o Insertion Sort, o número máximo de operações possíveis seria n2, conforme demonstrado anteriormente. A complexidade do tempo de classificação de inserção é:
Sobre dois )
Isso usa a notação Big-O. A notação Big-O começa com O em maiúscula, seguido por parênteses. Dentro dos parênteses está a expressão para o número máximo possível de operações.
Codificação em C
No início da varredura, o primeiro elemento não pode mudar sua posição. O programa é basicamente o seguinte:
#includevoid insertOrdenar ( int A [ ] , int N ) {
por ( int eu = 0 ; eu < N; i++ ) {
int j = i;
enquanto ( UMA [ j ] < UMA [ j- 1 ] && j- 1 > = 0 ) {
int temp = A [ j ] ; UMA [ j ] = A [ j- 1 ] ; UMA [ j- 1 ] = temperatura; // troca
j--;
}
}
}
A definição da função insertSort() usa o algoritmo conforme descrito. Observe as condições para o loop while. Uma função principal C adequada para este programa é:
{
int n = 8 ;
int A [ ] = { cinquenta , 60 , 30 , 10 , 80 , 70 , vinte , 40 } ;
inserçãoClassificar ( Um ) ;
por ( int eu = 0 ; eu < n; i++ ) {
printf ( '%eu ' , UMA [ eu ] ) ;
}
printf ( ' \n ' ) ;
Retorna 0 ;
}
Conclusão
A complexidade de tempo para a ordenação por inserção é dada como:
Sobre dois )
O leitor pode ter ouvido falar de complexidade de tempo de pior caso, complexidade de tempo de caso médio e complexidade de tempo de melhor caso. Essas variações da complexidade de tempo de classificação de inserção são discutidas no próximo artigo em nosso site.