2022-05-09

El problema del ordenamiento

$\text{Ordenar} : \text{arreglo}[\alpha] \to \text{arreglo}[\alpha]$, donde $\alpha$ es un tipo tal que está definida la relación $<_{\alpha}$.

Estabilidad

Un algoritmo de ordenamiento es estable si dos registros $i$ y $j$ con claves de ordenamiento iguales mantienen su orden relativo una vez ordenado el arreglo.

De forma coloquial, si la posición $i$ y $j$ guardan el mismo valor, luego de aplicarle al arreglo un algoritmo de ordenamiento estable podríamos estar seguros de que $i$ y $j$ seguirían manteniendo sus posiciones relativas.

En cambio, de aplicarle un algoritmo de ordenamiento inestable no podríamos asegurarnos de esto.

Algoritmos de Ordenamiento

Selection Sort

Algoritmo:

Repetir para las posiciones sucesivas $i$ del arreglo:

• Seleccionar el mínimo elemento que se encuetra entre la posición actual y el final.
• Ubicarlo en la posición $i$, intercambiándolo con el ocupante original de esa posición.

Invariante:

• Los elementos entre la posición $0$ y la posición $i$ son los $i + 1$ elementos más pequeños del arreglo original.
• Los elementos entre la posición $0$ y la posición $i$ se encuentran ordenados
• El arreglo es una permutación del arreglo original

Complejidad:

Contamos con $n - 1$ ejecuciones del ciclo principal, y en la $i$-ésima iteración debemos encontrar el mínimo de entre $n - 1$ elementos y por lo tanto necesitamos $n - i - 1$ comparaciones.

$$ T(n) = \sum_{i=0}^{n-2}(n-i-1) = \sum_{i=1}^{n-1}i = \frac{n\cdot (n-1)}{2} \in O(n^2) $$

Notemos que el costo no depende el eventual ordenamiento parcial o total del arreglo. Es decir, la complejidad del peor y mejor caso es la misma.

Estabilidad: Inestable.

Insertion Sort

Algoritmo:

Repetir para las posiciones sucesivas $i$ del arreglo:

• Insertar el $i$-ésimo elemento en la posición que le corresponde del arreglo entre las posiciones $0$ e $i$.

Invariante:

• Los elementos entre la posición $0$ y la posición $i$ son los elementos que ocupaban las posiciones $0$ a $i$ del arreglo original
• Los elementos entre la posición $0$ y la posición $i$ se encuentran ordenados
• El arreglo es una permutación del arreglo original