Estructura de datos y ordenación por inserción de algoritmos

Este es un algoritmo de clasificación basado en comparación en el lugar. Aquí, se mantiene una sublista que siempre está ordenada. Por ejemplo, la parte inferior de una matriz se mantiene para ser ordenada. Un elemento que se va a 'insertar' en esta sublista ordenada, debe encontrar su lugar apropiado y luego debe insertarse allí. De ahí el nombre,insertion sort.

La matriz se busca secuencialmente y los elementos no clasificados se mueven e insertan en la sublista ordenada (en la misma matriz). Este algoritmo no es adecuado para grandes conjuntos de datos ya que su complejidad promedio y en el peor de los casos son de Ο (n ² ), donden es el número de elementos.

¿Cómo funciona el ordenamiento por inserción?

Tomamos una matriz sin clasificar para nuestro ejemplo.

La ordenación por inserción compara los dos primeros elementos.

Encuentra que tanto el 14 como el 33 ya están en orden ascendente. Por ahora, 14 está en una sublista ordenada.

La ordenación por inserción avanza y compara 33 con 27.

Y encuentra que 33 no está en la posición correcta.

Cambia 33 por 27. También verifica con todos los elementos de la sublista ordenada. Aquí vemos que la sublista ordenada tiene solo un elemento 14, y 27 es mayor que 14. Por lo tanto, la sublista ordenada permanece ordenada después del intercambio.

Ahora tenemos 14 y 27 en la sublista ordenada. A continuación, compara 33 con 10.

Estos valores no están ordenados.

Entonces los intercambiamos.

Sin embargo, el intercambio hace que 27 y 10 no estén clasificados.

Por lo tanto, también los intercambiamos.

Nuevamente encontramos 14 y 10 en un orden no clasificado.

Los cambiamos de nuevo. Al final de la tercera iteración, tenemos una sublista ordenada de 4 elementos.

Este proceso continúa hasta que todos los valores no clasificados se cubren en una sublista ordenada. Ahora veremos algunos aspectos de programación del ordenamiento por inserción.

Algoritmo

Ahora tenemos una imagen más amplia de cómo funciona esta técnica de clasificación, por lo que podemos derivar pasos simples mediante los cuales podemos lograr la clasificación por inserción.

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

Pseudocó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 conocer la implementación del ordenamiento por inserción en el lenguaje de programación C, haga clic aquí .