13.09.2022

¿Cómo sabemos que el algoritmo de ordenaniento por inserción es correcto?

Se usan los "invariantes de ciclo" para ayudarnos a entender
por qué un algoritmo es correcto. Se necesitan mostrar tres cosas
sobre un invariante de ciclo:
  a) Inicialización
  b) Mantenimiento
  c) Terminación

a) Debe ser verdad antes de la primera iteración del ciclo.
 Si tenemos un solo elemento en el arreglo, este ya está ordenado.
 Entonces la inicialización es correcta.

b) Debe ser verdad antes de la terminación del ciclo y permanece
  verdadero antes de la siguiente iteración.
  En lo que se basa este algoritmo es que en el arreglo, el subarreglo
  A[1..j-1] ya está ordenado, y el subarreglo
  A[j..n] aún no está ordenado

c) Cuando el ciclo termina, el invariante nos da una propiedad útil
  que nos ayuda a mostrar que el algoritmo es correcto.
 Cuando el ciclo termina, con j=6 todo el subarraglo A[1..n] ya está
 ordenado y es lo que queremos, por lo tanto es verdad.