Estrutura de dados e classificação de inserção de algoritmos

Este é um algoritmo de classificação baseado em comparação no local. Aqui, uma sub-lista é mantida, que está sempre classificada. Por exemplo, a parte inferior de uma matriz é mantida para ser classificada. Um elemento que deve ser 'inserido' nesta sub-lista ordenada, tem que encontrar seu lugar apropriado e então tem que ser inserido lá. Daí o nome,insertion sort.

A matriz é pesquisada sequencialmente e os itens não classificados são movidos e inseridos na sub-lista classificada (na mesma matriz). Este algoritmo não é adequado para grandes conjuntos de dados, pois sua complexidade média e de pior caso são de Ο (n ² ), onden é o número de itens.

Como funciona a classificação por inserção?

Pegamos uma matriz não classificada como exemplo.

A classificação por inserção compara os dois primeiros elementos.

Ele descobre que 14 e 33 já estão em ordem crescente. Por enquanto, 14 está na sub-lista classificada.

A classificação por inserção avança e compara 33 com 27.

E descobre que 33 não está na posição correta.

Ele troca 33 por 27. Ele também verifica todos os elementos da sub-lista classificada. Aqui, vemos que a sub-lista classificada tem apenas um elemento 14 e 27 é maior que 14. Portanto, a sub-lista classificada permanece classificada após a troca.

Agora temos 14 e 27 na sub-lista classificada. Em seguida, compara 33 com 10.

Esses valores não estão em uma ordem de classificação.

Então, nós os trocamos.

No entanto, a troca torna 27 e 10 não classificados.

Portanto, nós os trocamos também.

Novamente encontramos 14 e 10 em uma ordem não classificada.

Nós os trocamos novamente. No final da terceira iteração, temos uma sub-lista classificada de 4 itens.

Esse processo continua até que todos os valores não classificados sejam incluídos em uma sub-lista classificada. Agora veremos alguns aspectos de programação da classificação por inserção.

Algoritmo

Agora temos uma visão maior de como essa técnica de classificação funciona, para que possamos derivar etapas simples pelas quais podemos alcançar a classificação por inserção.

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Pseudo-código

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
	
   for i = 1 to length(A) inclusive do:
	
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
		
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
		
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
	
end procedure

Para saber sobre a implementação de classificação por inserção na linguagem de programação C, clique aqui .