Comento una pequeña duda que me surgió al analizar la complejidad del algoritmo de Insertion Sort
Pseudocódigo:
\( Function \ Insertion_Sort(\ in/out \ A: \ array( \ \alpha_< \ )) \)
N \( \leftarrow \) Length(A)
i \( \leftarrow \) 1
\( while \ i \ < \ N-1 \ do: \) //
\( j \leftarrow \) i - 1, e \( \leftarrow A[i] \)
\( while \ j \ ≥ \ 0 \ \) ∧L \( \ A[j] \ > \ e \ do: \)
\( if \ A[j+1] \ \leftarrow \ A[j] \ then \)
\( j \ \leftarrow \ j-1 \)
\( \ end \ if \)
\( \ end \ while \)
A[j+1] \( \leftarrow \) e
\( \ end \ while \)
\( \ end \ Function \)
Lo que me interesa es analizar los índices, en particular el j
entonces de forma rápida me doy cuenta que
tengo dos sucesiones de índices:
\( i_{0} = 1 \)
\( i_{k} = i_{k-1} + 1 \), al desplegar la fórmula recurrente obtengo
\( i_{k} = i_{0} + (k-1)*1 + 1 = i_{0} + k = 1 + k \)
Ahora con \( i_{k} \) voy a definir j
\( j_{0} \) = \( i_{k} - 1 \)
\( j_{k} \) = \( j_{k-1} - 1 \)
Devuelta implemento lo anterior
\( j_{k} = j_{0} -(k-1) - 1 = j_{0} - k = j_{k} - 1, pero j_{k} = 1 + k \)
entonces
\( j_{k} = (1+k)-k = 1 \)
La pregunta es, donde esta fallando porque esto no representa los sucesivos valores que toma j e i
\( i_{0} = 1, i_{1} = 2, i_{2} = 3 ... i_{N-1} = N \)
\( j_{0} = 1 - 1, j_{1} = 2 - 1, j_{2} = 3 - 1 ... j_{N-1} = N-1 \)
Porque no hay una simetría??
la sucesión \( i_{k} \) representa la toma de valores de i
pero la sucesión \( j_{k} \) no lo hace para con j y siempre es 1 sea cual sea el valor de k.
Donde N es la longitud del array