**Tipo de inserción** –
También podemos decirlo como * algoritmo del profesor *.
Supongamos que está en su escuela, esperando la asamblea de oración en la mañana. El maestro viene y les pide a todos que se paren en la fila. Te pondrás en la fila con tu amigo, ¿verdad? Entonces, como se esperaba, todos se ponen en la fila con sus respectivos amigos. Ahora, se convierte en una tarea tediosa para el profesor, ¿por qué? Ella tiene que arreglarte en orden creciente de altura para que los pequeños no se escondan detrás. ¿Qué hará ella? Ella comienza a comparar. Ella se lleva a dos personas, digamos que primero selecciona a las delanteras.
- ¿Por qué la notación O grande es más común si la notación theta grande nos da más información?
- ¿Puede un gráfico ser un circuito de Euler y una ruta al mismo tiempo?
- ¿Cuál es el concepto de la función recursiva en matemáticas?
- ¿Cuál es el mejor algoritmo?
- ¿Puedo volverme competente en estructuras de datos y algoritmos sin leer el libro CLRS?
Digamos que solo hay cuatro niños. Rohit, Mohit, Ram, Shyam y la altura están en orden para que Rohit sea el más bajo, Mohit es el segundo más bajo, Ram es el segundo último más alto, Shyam es el más alto.
Pero están en el orden Shyam (primer niño), Ram (segundo niño), Mohit (tercer niño), Rohit (cuarto niño)
Iteración 1-
SubIteración1- Ella compara a los dos primeros niños (Shyam, Ram), se intercambian de acuerdo con su altura. El niño más alto es enviado a la posición dos, el niño más bajo a la una. Ahora, los primeros dos niños están ordenados (pero solo entre ellos). Entonces el resultado es – Ram-> Shyam.
Ahora Ram es el primer niño, Shyam es el segundo niño. Mohit tercero. Rohit cuarto.
Iteración 2-
SubIteración1- Ahora, ella selecciona al tercer niño (Mohit). Ella compara al tercer niño con el segundo. Supongamos que es más bajo que el segundo niño.
SubIteración2- Entonces, ella lo compara con el primer hijo ahora. Supongamos que también es más bajo que el primer niño. Ella esta es la posición que tiene que soportar. Lo colocan en la primera posición, sin interferir en las posiciones de los otros dos niños.
Ahora, los primeros tres niños se clasifican entre ellos. Entonces el resultado es – Mohit-> Ram-> Shyam. Ahora, Mohit es primero, Ram segundo, Shyam tercero, Rohit cuarto.
Iteración 3-
SubIteración1- Luego viene el cuarto niño (Rohit). El cuarto niño se compara con el tercer niño; es más bajo que el tercero.
SubIteración2- Entonces ella se compara de nuevo con el segundo niño. Él es más bajo que el segundo también. Luego se compara con el primer niño. De nuevo, él es más bajo que él también.
SubIteración3- Entonces, el cuarto niño se coloca en la primera posición ahora sin interferir con los otros tres niños.
Entonces el resultado es – Rohit-> Mohit-> Ram-> Shyam
Este fue el peor caso de inserción, donde todos
los niños que se supone que deben pararse en orden creciente de altura están parados en orden decreciente. ¿Cuántas iteraciones usamos? Tres. ¿Cuántas subiteraciones usamos?
En iteración1, uno.
En la iteración2, dos.
En la iteración 3, tres.
¿Notas algún patrón? Número de iteraciones = número de niños-1
Número de subiteraciones = Número de iteraciones
Número total de iteraciones generales =
1 + 2 + 3 = 6
podemos generalizar, n es el número de elementos, entonces, iteraciones generales = 1 + 2 + 2 +…. + (n-1) que no es más que la suma de números naturales, (n ^ (n-1)) / 2, o O (N ^ 2)
