Inserção Classificação de tempo complexidade

Considere os seguintes números:

50 60 30 10 10 80 70 20 40

Se esta lista for classificada em ordem crescente, seria:

10 20 30 40 40 60 70 80

Se for resolvido em ordem decrescente, seria:

80 70 60 50 40 30 20 10

O tipo de inserção é um algoritmo de classificação que é usado para classificar a lista em ordem ascendente ou em ordem decrescente. Este artigo lida apenas com a classificação em ordem crescente. A classificação em ordem decrescente segue a mesma lógica dada neste documento. O objetivo deste artigo é explicar o tipo de inserção. A programação é feita no exemplo a seguir em C. O tipo de inserção é explicado aqui usando uma matriz.

Algoritmo para Classificação de Inserção

Uma lista não classificada é dada. O objetivo é classificar a lista em ordem crescente usando a mesma lista. Classificando uma matriz não classificada usando a mesma matriz, está classificando no local. A indexação baseada em zero é usada aqui. As etapas são as seguintes:

• • A lista é digitalizada desde o início.
  • Enquanto a digitalização está acontecendo, qualquer número menor que o 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á completa.

Ilustração de classificação de inserção

Ao lidar com a complexidade do 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

Existem 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 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 estavam envolvidas.

64 = 8 x 8 = 8²

Complexidade do tempo para classificação de inserção

Se houver n elementos a serem classificados com o tipo de inserção, o número máximo de operações possíveis seria N2, como demonstrado anteriormente. A complexidade do tempo de classificação da inserção é:

Sobre²)

Isso usa a notação Big-O. A notação Big-O começa com O na maçaneta, seguida de parênteses. Dentro dos parênteses está a expressão para o máximo número 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 é essencialmente o seguinte:

#incluir
INSERÇÕES VOID (INT A [], int n)
para (int i = 0; iint j = i;
enquanto (a [j] < A[j-1] && j-1 >= 0)
int temp = a [j]; A [j] = a [j-1]; A [j-1] = temp; //trocar
J--;

A definição de função insertSort () usa o algoritmo conforme descrito. Observe as condições para o loop de enquanto. Uma função principal C adequada para este programa é:

int main (int argc, char ** argv)

int n = 8;
int a [] = 50, 60, 30, 10, 80, 70, 20, 40;
insertionsort (a, n);
para (int i = 0; iprintf ("%i", a [i]);

printf ("\ n");
retornar 0;

Conclusão

A complexidade do tempo para o tipo de inserção é dada como:

Sobre²)

O leitor pode ter ouvido falar de uma complexidade do tempo pior, complexidade do tempo médio e melhor complexidade do tempo. Essas variações da complexidade do tempo de classificação de inserção são discutidas no próximo artigo em nosso site.