Ordenación Elemental
Número de ejecuciones de un programa
Para analizar la eficiencia de un algoritmo, es necesario contar el número de veces que se ejecutan las instrucciones.
Para contar cuántas veces se ejecuta una operación, debemos tener en cuenta todos los comandos disponibles.
En el comando \(\skip\) no se ejecuta ninguna operación, por lo que el número de operaciones es 0.
\[ops(\skip) = 0 \]En el caso de \(\for\), debemos tener en cuenta que la siguiente ecuación vale si no hay interés en contar las operaciones que involucran el índice \(k\).
\[ops(\for \; k:= n \; \too \; m \; \do \; C(k) \; \od) = \displaystyle{\sum_{n}^{m} ops(C(k))} \]Para \(\if\) contamos cuantas veces se ejecuta durante la evaluiación de \(b\) y luego cuantas en la ejecución de \(C\) y \(D\) (caso verdadero y falso)
\[ops(\if \; b \; \then \; C \; \else \; D \; \fi) = \begin{cases} ops(b) + ops(C) & \text{si } b \text{ es verdadero} \\ ops(b) + ops(D) & \text{si } b \text{ es falso} \end{cases} \]Para la asignación, debemos considerar el caso de modificación de la variable. Debemos considerar que tal vez, el nuevo valor es la llamada a una función que también tiene un costo.
\[ops(x := e) = \begin{cases} ops(e) + 1 & \text{si } x \text{ es modificada} \\ ops(e) & \text{si } x \text{ no es modificada} \end{cases} \]Para las expresiones, consideramos el caso de contar comparaciones:
\[ops(e<f) = \begin{cases} ops(e) + ops(f) + 1 & \text{si se cuentan comparaciones} \\ ops(e) + ops(f) & \text{caso contrario } \end{cases} \]En el caso de los ciclos (\(\do\)) tenemos que:
\[ops(\do \; b \rightarrow C \; \od) = ops(b) + \displaystyle{\sum_{k=1}^n \; d_k} \]Donde \(n\) es el número de veces que el cuerpo del ciclo se ejecuta, y \(d_k\) s el número de operaciones que se ejecutan en la \(k\)-ésima iteración.
Ordenación por selección (Selection Sort)
Este algoritmo consiste en seleccionar el menor elemento de un arreglo e intercambiarlo por el que está en la primera posición. Luego el menor elemento de los siguientes a la primera posición va en la segunda posición, y asi sucesivamente.
Veamos como aplicar este algoritmo en un arreglo:
El arreglo \(a\) es una permutación del original. A partir del segmento \(a[1, i)\) los elementos menores del arreglo están ordenados (invariante del ciclo).
Si quisieramos escribir este algoritmo en pseudocódigo, primero podemos escribir un procedimiento que recorra el arreglo, llamando una función que nos devuelva la posición del menor elemento a partir de una posición dada. Luego, intercambiamos el elemento de la posición actual con el menor elemento encontrado con un procedimiento.
\[\begin{align} &\{ \; n \geq 0 \land a = A \; \} \\ &\proc \; selection\_sort(\inout \; a : \array [1..n] \; \of \; T) \\ &\quad \var \; i, \; minp: \; \nat \\ &\quad i := 1 \quad\quad\quad\quad\quad\quad \{- \;\; \textnormal{Invariante} \;\; -\} \\ &\quad \while \; i < n \; \do \\ &\quad \quad minp := min\_pos\_from (a,i) \\ &\quad \quad swap(a, i, minp) \\ &\quad \quad i := i+1 \\ &\quad \od \\ &\bfend \; \proc \\ &\{ \; a \; \textnormal{está ordenado y es permutación de} \; A \; \} \\ \end{align} \]El \(swap\) sería:
\[\begin{align} &\{ \; a = A \land 1 \leq i, j \leq n \; \} \\ &\proc \; swap(\inout \; a : \array [1..n] \; \of \; T, \; \bfin \; i, j : \nat) \\ &\quad \var \; tmp : T \\ &\quad tmp := a[i] \\ &\quad a[i] := a[j] \\ &\quad a[j] := tmp \\ &\bfend \; \proc \\ &\{\; a[i] = A[j] \land a[j] = A[i] \land \forall k \not\in \{ i, j \} \implies a[k]=A[k] \; \} \\ \end{align} \]Para hacer \(min\_pos\_from\), podemos seguir la siguiente lógica:
El invariante es igual al anterior, pero ahora incluimos el mínimo del segmento \(a[i, j)\) en la posición \(minp\).
\[\begin{align} &\{ \; 0 < i \leq n \; \} \\ &\fun \; min\_pos\_from(a : \array [1..n] \; \of \; T, \; i : \nat) \; \ret \; minp: \; \nat \\ &\quad \var \; j : \nat \\ &\quad minp := i \\ &\quad j := i+1 \quad\quad\quad\quad\quad\quad \{- \;\; \textnormal{Invariante: } \; a[minp] \; \textnormal{es el mínimo de} \; a[i,j] \;\; -\} \\ &\quad \while \; j \leq n \; \do \\ &\quad \quad \if \; a[j] < a[minp] \; \then \\ &\quad \quad \quad minp := j \\ &\quad \quad \fi \\ &\quad \quad j := j+1 \\ &\quad \od \\ &\bfend \; \fun \\ &\{ \; a[minp] \; \textnormal{es el mínimo de} \; a[i,n] \; \} \\ \end{align} \]Una manera de hacer lo mismo y con menos código es usando \(\for\):
\[\begin{align} &\proc \; selection\_sort(\inout \; a : \array [1..n] \; \of \; T) \\ &\quad \for \; i := 1 \; \too \; n \; \do \\ &\quad \quad minp := min\_pos\_from(a,i) \\ &\quad \quad swap(a, i, minp) \\ &\quad \od \\ &\bfend \; \proc \\ &&\\ &\fun \; min\_pos\_from(a : \array [1..n] \; \of \; T, \; i : \nat) \; \ret \; minp: \; \nat \\ &\quad minp := i \\ &\quad \for \; j := i+1 \; \too \; n \; \do \\ &\quad \quad \if \; a[j] < a[minp] \; \then \\ &\quad \quad \quad minp := j \\ &\quad \quad \fi \\ &\quad \od \\ &\bfend \; \fun \\ \end{align} \]De esta forma, las variables que sirven de índices estan declaradas en el contexto/scope de \(\for\)
Ordenación por inserción (Insertion Sort)
Este algoritmo consiste en insertar un elemento en la posición correcta de un arreglo ordenado. Se comprueba si el elemento es menor al anterior, y si lo es, se intercambian.
Veamos como aplicar este algoritmo en un arreglo:
El arreglo \(a\) es una permutación del original. Un segmento inicial \(a[1,i]\) del arreglo está ordenado, en general, \(a[1,i]\) no contiene los mínimos del arreglo (invariante del ciclo).
Si quisieramos escribir este algoritmo en pseudocódigo, podemos escribir un procedimiento que recorra el arreglo, utilizando un procedimiento que se encargue de insertar un elemento en la posición correcta.
\[\begin{align} &\{ \; n \geq 0 \land a = A \; \} \\ &\proc \; insertion\_sort(\inout \; a : \array [1..n] \; \of \; T) \\ &\quad \for \; i := 2 \; \too \; n \; \do \\ &\quad \quad insert(a, i) \\ &\quad \od \\ &\bfend \; \proc \\ &\{ \; a \; \textnormal{está ordenado y es permutación de} \; A \; \} \\ \end{align} \]Para hacer \(insert\), podemos seguir la siguiente lógica:
Como invariante, tenemos que \(a\) es una permutación de \(A\), el segmento \(a[1,i]\) sin celda \(j\) está ordenado y, \(a[j,i]\) también está ordenado.
\[\begin{align} &\{ \; 0 < i \leq n \land a = A \; \} \\ &\proc \; insert(\inout \; a : \array [1..n] \; \of \; T, \; \bfin \; i : \nat) \\ &\quad \var \; j : \nat \\ &\quad j := i \quad\quad\quad\quad\quad\quad \{- \;\; \textnormal{Invariante mencionado} \;\; -\} \\ &\quad \while \; j > 1 \; \land \; a[j] < a[j-1] \; \do \\ &\quad \quad swap(a, j-1, j) \\ &\quad \quad j := j-1 \\ &\quad \od \\ &\bfend \; \proc \\ &\{ \; a[1,i] \; \textnormal{está ordenado y es permutación de} \; A \; \} \\ \end{align} \](Se utiliza el mismo \(swap\) que en el algoritmo de selección). Tanto este algoritmo como el de selección tienen complejidad cuadrática \(\bigO(n^2)\) (en el peor caso), ya que sería necesario recorrer el arreglo completo en cada iteración.