Saltar al contenido

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

octubre 16, 2021
unsorted array

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, tipo de inserción.

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 Ο (n2), dónde norte es el número de elementos.

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

Tomamos una matriz sin clasificar para nuestro ejemplo.

Matriz sin clasificar

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

Tipo de inserción

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

Tipo de inserción

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

Tipo de inserción

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

Tipo de inserción

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.

Tipo de inserción

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

Tipo de inserción

Estos valores no están ordenados.

Tipo de inserción

Entonces los intercambiamos.

Tipo de inserción

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

Tipo de inserción

Por lo tanto, también los intercambiamos.

Tipo de inserción

Nuevamente encontramos 14 y 10 en un orden no clasificado.

Tipo de inserción

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

Tipo de inserción

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í.

close