Classificação de inserção de Python
Como funciona a classificação da inserção?
O funcionamento da classificação da inserção é discutido em detalhes aqui. Os números são classificados usando o tipo de inserção. Ele coloca repetidamente o elemento não classificado subsequente no local apropriado na lista anteriormente classificada. O conceito fundamental é comparar o segundo membro com o primeiro elemento da matriz que presumivelmente já é classificado. Se o segundo elemento for um valor menor que o primeiro, ele será alterado. Este procedimento é repetido para os restantes elementos da matriz. Os piores e médios casos de inserção têm uma complexidade do tempo O (n2), enquanto o melhor caso tem uma complexidade do tempo O (n).
Exemplo 1:
Tomamos um exemplo linear para entender o conceito de tipo de inserção. O código de referência é fornecido no seguinte:
para n no intervalo (1, len (arr)):
chave = arr [n]
M = N-1
enquanto m> = 0 e chave < arr[m] :
arr [m + 1] = arr [m]
m -= 1
arr [m + 1] = chave
arr = [29, 15, 7, 10, 46]
Insertionsortalgo (arr)
Print ("O resultado da matriz classificada é:", arr)
Como visto neste exemplo, definimos uma função de classificação de inserção na linha 1. Esta implementação leva uma lista de números como entrada e classifica a lista em ordem crescente. Atribuímos a variável "arr" como uma lista neste exemplo. Depois disso, começamos o loop externo que verifica o índice da matriz. O loop "for" é usado aqui. O intervalo começa em 1, que é o segundo número em uma matriz e continua através do loop até o último elemento.
Dentro deste loop, inicializamos uma variável -chave que verifica o valor do índice um por um. Depois disso, criamos uma variável que detém o valor da matriz (n-1). O loop interno agora começa a verificar os valores da matriz. O loop interno começa no índice atual do loop externo e compara o elemento atual com o elemento anterior. Se o elemento anterior for maior, ele será deslocado para a direita e o índice do elemento atual diminuirá. Isso continua até que a posição correta para o elemento atual seja encontrada.
O elemento atual é colocado no local apropriado após o término do loop interno. No final, declaramos e inicializamos a matriz chamada "arr". Usamos essa matriz na função de inserção anteriormente descrita para executar a classificação na matriz. Por fim, fornecemos a matriz na declaração de impressão para exibir o resultado no console.
A saída deste programa de exemplo é fornecida no seguinte:
[7, 10, 15, 29, 46]Exemplo 2:
Também explicaremos a classificação de inserção em Python com a ajuda de outro exemplo. Criamos e executamos este exemplo usando qualquer ferramenta Python, como Pyharm ou Júpiter Notebook. O código de referência para este outro exemplo está anexado no seguinte:
Para I no intervalo (1, Len (Arrayx)):
temp = Arrayx [i]
anteriorElement = i-1
enquanto anteriorlement> = 0 e temp < arrayX[previousElement]:
Arrayx [AnteriorElement+1] = Arrayx [AnteriorElement]
anteriorlement- = 1
Arrayx [AnteriorElement+1] = Temp
Arrayx = [45, 66, 37, 99, 10, 5, 2, 78, 1]
SortArray (Arrayx)
print ("O resultado da matriz classificada é", Arrayx)
Declaramos uma matriz para fins de classificação, definindo a função chamada "SortArray". Usamos um loop para atravessar a matriz e iniciar a pesquisa pelo índice "1". Colocamos o comprimento da matriz e o índice "1" na função de intervalo em que o loop é executado. Colocamos outra variável na qual atualmente armazenamos o valor da iteração do loop "eu" na matriz e atribuímos o valor à variável "Temp". Armazenamos o valor anterior, que provavelmente é o primeiro elemento da matriz da qual comparamos a variável "Temp" para pesquisar se esse valor for maior ou menor que o valor que é armazenado na variável "Temp" e nome AnteriorElement ”.
O loop interno leva o valor presente na variável "AnteriorElement" para verificar se o valor é maior que "0". Em seguida, comparamos as duas variáveis chamadas "Temp" e "AnteriorElement" que são armazenadas na matriz. Este valor é passado até que o loop permaneça final. Se o valor da matriz que é armazenado em "AnteriorElement" for "+1", significa que o valor de mudança de loop é menor que o valor anterior da matriz que é armazenada no índice "0". Em seguida, trocamos essas duas variáveis pelas quais o valor menor é deslocado para o índice "0" e o maior valor é movido no lugar de outra variável.
Aqui, escrevemos a lógica para trocar os elementos da matriz para classificar os elementos. Agora, todos os valores da matriz são verificados um por um. Alterar a posição dos valores é menor e mudou para o início da matriz. Vamos pegar esta matriz para consideração. Iniciamos a matriz com o índice “1”. Isso significa que primeiro tomamos “66”. Em seguida, comparamos o valor de "66" com o valor anterior que é armazenado no índice "0", que é "45". Agora, "45" é menor que "66". Então, trocamos a variável que armazena o valor de "66". Em seguida, atribuímos o valor anterior da matriz na variável "Temp". Agora, armazenamos o valor de "45" na variável "Temp".
Por fim, atribuímos o valor armazenado em "Array [AnteriorElement +1]", onde o próximo valor para o valor anterior é armazenado. Depois disso, armazenamos o próximo valor anterior em Temp para começar a classificar novamente. Dessa forma, trocamos os valores maiores e menores. Então, até que o loop seja válido, os elementos da matriz são armazenados rapidamente, um por um. No final do código, exibimos o resultado dessa matriz no console através da declaração de impressão.
Aqui, a saída desta matriz é exibida no console, pois o resultado da matriz armazenada é
[1,2,5,10,37,45,66,78,99].Conclusão
Concluímos que a classificação de inserção é o tipo mais importante de classificação que é usado para classificar todos os elementos de uma matriz no Python. O tipo de inserção é um algoritmo estável e no local, mas ineficiente, que tem muitos benefícios que discutimos com a ajuda de exemplos. Aqui, dividimos a matriz em duas partes: classificadas e não classificadas. A comparação entre essas duas partes criou a matriz classificada no final.