Descripción general
La clasificación por inserción es un algoritmo de clasificación simple que funciona insertando cada elemento de una matriz en su posición correcta en la matriz. Comienza con una matriz ordenada vacía y luego itera a través de la matriz de entrada, insertando cada elemento en su posición correcta en la matriz ordenada. Este proceso se repite hasta que se ordena toda la matriz de entrada.
Pasos del algoritmo
Aquí está el algoritmo paso a paso para la ordenación por inserción:
1. Comience con una matriz ordenada vacía.
2. Iterar a través de la matriz de entrada.
3. Para cada elemento de la matriz de entrada, insértelo en su posición correcta en la matriz ordenada.
4. Para insertar un elemento, compárelo con cada elemento de la matriz ordenada, comenzando con el primer elemento.
5. Si el elemento es menor que el elemento actual en la matriz ordenada, insértelo antes del elemento actual.
6. Si el elemento es mayor que el elemento actual en la matriz ordenada, continúe comparando con el siguiente elemento de la matriz ordenada.
7. Repita los pasos 4 a 6 hasta que el elemento se haya insertado en su posición correcta en la matriz ordenada.
8. Repita los pasos 2 a 7 para cada elemento de la matriz de entrada.
Ejemplo
Consideremos la siguiente matriz de entrada:
```
[5, 2, 8, 3, 1]
```
Los siguientes pasos muestran cómo el algoritmo de ordenación por inserción ordenaría esta matriz:
1. Comience con una matriz ordenada vacía.
```
[]
```
2. Iterar a través de la matriz de entrada.
```
[5]
```
3. Para cada elemento de la matriz de entrada, insértelo en su posición correcta en la matriz ordenada.
```
[5]
```
4. Para insertar el elemento 2, compárelo con cada elemento de la matriz ordenada, comenzando con el primer elemento.
```
[5, 2]
```
5. Dado que 2 es menor que 5, insértelo antes del elemento actual.
```
[2, 5]
```
6. Iterar a través de la matriz de entrada.
```
[2, 5, 8]
```
7. Para cada elemento de la matriz de entrada, insértelo en su posición correcta en la matriz ordenada.
```
[2, 5, 8]
```
8. Para insertar el elemento 3, compárelo con cada elemento de la matriz ordenada, comenzando con el primer elemento.
```
[2, 3, 5, 8]
```
9. Dado que 3 es menor que 5, insértelo antes del elemento actual.
```
[2, 3, 5, 8]
```
10. Iterar a través de la matriz de entrada.
```
[2, 3, 5, 8, 1]
```
11. Para cada elemento de la matriz de entrada, insértelo en su posición correcta en la matriz ordenada.
```
[1, 2, 3, 5, 8]
```
12. Para insertar el elemento 1, compárelo con cada elemento de la matriz ordenada, comenzando con el primer elemento.
```
[1, 2, 3, 5, 8]
```
13. Dado que 1 es menor que 2, insértelo antes del elemento actual.
```
[1, 2, 3, 5, 8]
```
14. La matriz ordenada ya está completa.
```
[1, 2, 3, 5, 8]
```
Complejidad del tiempo
La complejidad temporal de la ordenación por inserción es O (n^2), donde n es la longitud de la matriz de entrada. Esto significa que el tiempo de ejecución de la ordenación por inserción aumenta cuadráticamente a medida que aumenta el tamaño de la matriz de entrada. La ordenación por inserción funciona mejor cuando la matriz de entrada ya está casi ordenada, en cuyo caso su complejidad temporal es O(n).
Complejidad espacial
La ordenación por inserción requiere espacio auxiliar O(1), ya que solo necesita almacenar una única variable (el elemento actual que se inserta) además de la matriz de entrada.
Ventajas y Desventajas
La clasificación por inserción tiene algunas ventajas y desventajas:
Ventajas:
* Sencillo de implementar
* Eficiente para arreglos pequeños o arreglos casi ordenados
* Algoritmo de clasificación estable (mantiene el orden relativo de elementos iguales)
Desventajas:
* No es eficiente para matrices grandes
* Complejidad del tiempo cuadrático (O(n^2))
* No es un algoritmo de clasificación local (requiere espacio adicional)
Conclusión
La clasificación por inserción es un algoritmo de clasificación simple y eficiente que funciona bien para matrices pequeñas o casi ordenadas. Su simplicidad y estabilidad lo convierten en un algoritmo útil para fines educativos y para aplicaciones especializadas. Sin embargo, no es el algoritmo de clasificación más eficiente para matrices grandes, donde se deberían utilizar algoritmos más eficientes como la clasificación rápida o la clasificación por combinación.