Uma introdução ao algoritmo de classificação por inserção
A classificação por inserção é uma técnica que funciona utilizando uma sublista classificada e continuamente adicionando um valor a ela da lista não classificada até que toda a lista seja classificada.
O algoritmo começa com o primeiro item da lista como a sublista classificada. Em seguida, ele compara o próximo número com o primeiro. Se for maior, então é inserido no primeiro índice. Caso contrário, é deixado em seu índice.
O terceiro valor é então comparado com os outros dois e, em seguida, inserido no índice correto. Esse processo continua até que toda a lista seja classificada.
Uma análise mais detalhada da classificação por inserção
A descrição acima pode não ter feito sentido para você. Um exemplo deve ajudá-lo a entender muito melhor.
Suponha que você tenha uma lista: [39, 6, 2, 51, 30, 42, 7].
O algoritmo identifica 39 como o primeiro valor da sublista classificada. A avaliação então passa para a segunda posição.
6 é então comparado com 39. Como 6 é menor que 39, 6 é inserido na primeira posição e 39 na segunda. A nova ordem da lista é após a primeira passagem é agora:
[6, 39, 2, 51, 30, 42, 7]
A avaliação agora muda para a terceira posição. 2 é comparado com os dois últimos números e, em seguida, inserido na posição correta. A nova ordem da lista é após a segunda passagem é agora:
[2, 6, 39, 51, 30, 42, 7]
Para a terceira passagem, a ordem da lista é:
[2, 6, 39, 51, 30, 42, 7]
O processo se repete até que toda a lista seja classificada.
Veja o diagrama abaixo que resume essas operações:
Análise de algoritmo
A complexidade de tempo da classificação por inserção é O (n 2 ), assim como a classificação por bolha . O número de comparações no pior cenário é a soma de todos os inteiros de 1 a (n-1), dando uma soma quadrática.
Implementação de Código
O código Python e Java abaixo mostra como você pode implementar o método Insertion Sort.
Pitão:
def insertionSort(mylist):
for step in range(1, len(mylist)):
current_element = mylist[step]
position = step
while position > 0 and mylist[position - 1] > current_element:
mylist[position] = mylist[position - 1]
position = position - 1
mylist[position] = current_elementJava:
void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x < n; x++) {
int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
}Melhor codificação com pseudocódigo
Os exemplos de código acima foram fornecidos sem nenhum pseudocódigo ao qual você possa fazer referência para escrever este algoritmo em outras linguagens. A maioria dos programadores (incluindo o autor) gosta de correr para seus teclados depois de ouvir "sussurros" sobre como um programa funciona.
Infelizmente, essa abordagem está sujeita a erros à medida que a lógica do programa fica mais complicada. Você gostaria de aumentar o nível do seu jogo de programação, aprendendo a usar o pseudocódigo?
