Implementar y analizar algoritmos de ordenamiento de arreglos con costo óptimo en el peor caso, así como algoritmos adaptativos a la entrada para caracterizar su desempeño bajo un enfoque experimental para la solución efectiva de problemas informáticos.
En este tema se aborda el ordenamiento basado en comparación, esto es, existe un operador \(<\) que es capaz de distinguir si un elemento \(a\) es menor que un elemento \(b\).
El operador cumple con las siguientes propiedades:
Usar un operador como \(<\) es suficiente para crear algoritmos correctos y eficientes, sin embargo, en la práctica y en una computadora real, también es válido utilizar operadores como \(=\) o \(\leq\), o intercambiar por \(>\) y \(\geq\) según convenga. No hay impacto en la eficiencia.
Sin perdida de generalidad, podemos planter el problema de ordenamiento sin permitir repeticiones como sigue: dado un arreglo \(A[1, n] = a_1, a_2, \cdots, a_n\); un algoritmo de ordenamiento obtiene la permutación \(\pi\) tal que \(a_{\pi(1)} < a_{\pi(2)} < \cdots < a_{\pi(n)}\).
Cuando se permiten elementos repetidos, se le llama ordenamiento estable i se asegura que en el arreglo ordenado se preserven el orden original posicional cuando \(a = b\). Esta propiedad es importante cuando hay datos satélitales asociados a la llave de comparación.
En términos prácticos, la idea es reorganizar \(A\), mediante el cálculo implicito de la permutación \(\pi\), de tal forma que después de terminar el proceso de ordenamiento se obtenga que \(A\) esta ordenado, i.e., \(a_i \leq a_{i+1}\). En sistemas reales, el alojar memoria para realizar el ordenamiento implica costos adicionales, y es por esto muchas veces se busca modificar directamente \(A\).
Utilizar \(\pi\) solo es necesario cuando no es posible modificar \(A\). También es muy común utilizar datos satélite asociados con los valores a comparar, de esta manera es posible ordenar diversos tipos de datos. Un ejemplo de esto es ordenar un dataframe, pero también estructuras de datos donde existe un campo especial y el resto de los datos asociados es de importancia para una aplicación.
Para una entrada de tamaño \(n\) existen \(n!\) permutaciones posibles; cada una de estas permutaciones es una instancia del problema de ordenamiento de tamaño \(n\).
Existe una permutación objetivo \(\pi^*\), i.e., que cumple con la definición de que esta ordenada; ahora pensemos en un grafo donde cada \(\pi_i\) esta conectada con todas las permutaciones en las que se puede transformar haciendo una única operación, e.g., intercambiando un elemento. El algoritmo forma ese grafo con sus posibles decisiones, por lo que el camino más largo i.e., ruta sin ciclos, entre cualquier \(\pi_i\) y la permutación \(\pi^*\) es el costo de peor caso del algoritmo.
Ahora, cada operación que realicemos en un algoritmo nos acercará más a \(\pi^*\), descartando una cierta cantidad de instancias posibles pero no viables; si nuestra función de transición en el grafo viene dada con respecto a colocar cada par de elementos en su orden relativo, entonces, la mitad de las permutaciones se han descartado, ya que ese par no puede estar en el orden contrario. Por tanto, el costo de cualquier algoritmo que realice comparaciones y descarte la mitad del espacio de búsqueda, es \(\log_2(n!)\), que usando la aproximación de Stirling,1 lo podemos reescribir como sigue:
\[\log_2(n!) = n \log_2 n - n \log_2 e + O(\log_2 n)\]
Esto se puede simplemente escribir como \(O(n \log n)\).
Existen muchos algoritmos que pueden resolver el problema de ordenamiento, es común contar el número de comparaciones ya que produce la información necesaria para la navegación en el grafo de instancias; también es común contar las operación de intercambiar elementos. Las pruebas y la navegación en el grafo determina el costo del algoritmo. Es necesario mencionar que mover datos entre diferentes zonas de memoria puede llegar a ser más costoso que solo acceder a esas zonas por lo que hay una asimetría en el costo de estas dos operaciones.
Note que algunos de los algoritmos más simples pueden tener un comportamiento oportunistas y que son capaces de obtener ventaja en instancias sencillas, por lo que no debería saltarse esas secciones si solo conoce su comportamiento en peor caso.
El algoritmo de ordenamiento de burbuja o bubble sort realiza una gran cantidad de comparaciones, como puede verse en Listado 4.1, el algoritmo usa dos ciclos anidados para realizar una comparación y una posible transposición, formando un triángulo, i.e., \[ \sum_{i=1}^{n-1} \sum_{j=1}^{n-i} O(1);\] por lo tanto su costo esta dominado por el triangulo formado, i.e., \(\sim n^2/2\) lo que puede escribirse simplemente como \(O(n^2)\).
function bubble_sort!(A)
n = length(A)
for i in 1:n-1
for j in 1:n-i
if A[j] > A[j+1]
A[j], A[j+1] = A[j+1], A[j]
end
end
end
A
end
bubble_sort!([8, 4, 3, 1, 6, 5, 2, 7])8-element Vector{Int64}:
1
2
3
4
5
6
7
8El algoritmo mostrado en Listado 4.1 es un algoritmo de peor caso, ya que sin importar la complejidad de la instancia (i.e., que tal alejada esta \(\pi_i\) de \(\pi^*\)), se comporta igual.
Es relativamente fácil hacer un bubble sort que tenga en cuenta la complejidad de la instancia, medida como el número de intercambios necesarios.
function adaptive_bubble_sort!(A)
n = length(A)
for i in 1:n-1
s = 0
for j in 1:n-i
if A[j] > A[j+1]
s += 1
A[j], A[j+1] = A[j+1], A[j]
end
end
s == 0 && break
end
A
end
adaptive_bubble_sort!([7, 8, 4, 3, 1, 6, 5, 2])8-element Vector{Int64}:
1
2
3
4
5
6
7
8En la forma Listado 4.2, bubble sort es capaz de términar en \(n-1\) comparaciones si el arreglo esta ordenado; sacando provecho de casos simples en términos de instancias casi ordenadas.
El algoritmo de ordenamiento por inserción o insertion sort es un algoritmo simple que al igual que bubble sort tiene un mal peor caso y puede aprovechar casos simples
function insertion_sort!(A)
n = length(A)
for i in 2:n
key = A[i]
j = i - 1
while j >= 1 && A[j] > key
A[j + 1] = A[j]
j -= 1
end
A[j + 1] = key
end
A
end
insertion_sort!([5, 1, 4, 8, 2, 6, 3, 7])8-element Vector{Int64}:
1
2
3
4
5
6
7
8Para analizar Listado 4.3, es importante notar que el ciclo más externo termina con el subarreglo \(A[1..i]\) ordenado; por lo que cuando se comienza el ciclo, si key se prueba estar en su posición correcta, entonces ya no es necesario revisar el resto del subarreglo, esto determina que un arreglo ordenado tendrá un costo de \(O(n)\) comparaciones; si esta casi ordenado en términos del número de intercambios necesarios, entonces, el algoritmo se adaptará sacando provecho de la instancia.
En el peor caso de insertion sort, el algoritmo no puede parar de manera prematura, e.g., un arreglo en orden reverso, el ciclo for se ejecutara \(n-1\) veces, mientras que el ciclo while deberá revisar el subarreglo completo en cada iteración, sumando un costo de \(i\) operaciones en cada iteración, i.e., \(\sum_{i=1}^n i\), esta forma produce un triángulo, resultando en un costo \(O(n^2)\).
Quick sort (ver Cormen et al. 2022, cap. 7) es un algoritmo tipo dividir para vencer; esto es, un algoritmo que divide un problema grande en instancias pequeñas más sencillas. Es uno de los algoritmos más veloces en la práctica por su buen manejo de memoria, aun cuando tiene un peor caso cuadrático, en promedio el costo es \(O(n \log n)\).
using Random
function qsort!(A, low=1, high=length(A))
if low < high
piv = part!(A, low, high)
qsort!(A, low, piv - 1)
qsort!(A, piv + 1, high)
end
A
end
function part!(A, low, high)
ipiv = rand(low:high)
A[ipiv], A[high] = A[high], A[ipiv]
piv = A[high]
i = low - 1 # uno antes porque se accede después de un i+1
for j in low:high - 1
if A[j] < piv
i += 1
A[i], A[j] = A[j], A[i]
end
end
ipiv = i + 1
A[ipiv], A[high] = A[high], A[ipiv]
ipiv
end
qsort!([6, 8, 3, 7, 4, 1, 2, 5])8-element Vector{Int64}:
1
2
3
4
5
6
7
8El código Listado 4.4 es relativamente simple, usa recurrencias sobre qsort! sobre dos partes extremas divididas por un pivote; estos tres elementos son encontrados en part!. La función part! es muy eficiente en términos de memoria, lo que puede hacer la diferencia en la práctica. La correcta selección del pivote es muy importante para evitar casos malos, i.e., costo cuadrático; en esta implementación se realiza una selección aleatoría de pivote que funcionará en la mayoría de los casos.
El peor de los casos en qsort! es debido a una mala selección del pivote, de tal forma que \[|A[low:piv-1]| \ll |A[piv+1:high]|,\] o lo contrario en toda selección, en el extremo una de los subarreglos puede verse como de tamaño constante o cero, i.e., selección de pivote como el minimo o el máximo. Esta estrategía reduce a qsort! a un costo \(O(n^2)\).
Si se realiza un particionado donde \[|A[low:piv-1]| \approx |A[piv+1:high]|,\] entonces tenemos un algoritmo \(O(n \log n)\); ya que hace una división en dos partes casi iguales en cada recurrencia a qsort!, y esto solo puede profundizar a \(\log n\) veces, y en cada nivel part! tiene un costo lineal.
Una skip list (Pugh 1990) es una lista ligada con capacidades de búsqueda eficiente con garantías probabilísticas, esto es que se cumplen con alta probabilidad. Para esto, la idea es que cada dato tiene asociado un arreglo de punteros o referencias hacia nodos sucesores, i.e., los nodos a nivel \(i\) se conectan con el siguiente nodo a nivel \(i\). En el nivel más bajo, la skip list es una simple lista ligada, mientras que sube, se vuelve más dispersa dando saltos más largos.
A diferencia de los algoritmos vistos anteriormente, en este caso, ya se tiene una estructura de datos, que conlleva un costo en memoría explícito por nodo. Figura 4.1 ilustra la estructura.
La altura de cada nodo es calculada de manera probabilística, dada la probababilidad \(p\). Un valor común de \(p=0.5\). La altura de cada nodo se calcula como sigue:
function levels(p)
i = 1
while rand() < p
i += 1
end
i
endlevels (generic function with 1 method)Si tenemos \(n\) evaluaciones de levels, Los niveles pequeños son relativamente probables, mientras que niveles grandes son relativamente poco probables. De hecho, los niveles \(\log_{1/p} n\) son cercanos a una constante, \(\log_{1/p}{n} - 1\) son \(1/p\) veces la constante, \(\log_{1/p}{n} - 2\) son \(1/p^2\) veces la constante, etc.
A diferencia de los algoritmos anteriores, una skip list comienza vacia, y se va poblando insertando elementos a la lista. Se va colocando en la posición que no viola el orden; generando el nodo correspondiente con nivel calculado. Los nodos especiales head y tail siempre tienen el nivel máximo posible. La inserción de un valor encapsulado en el nodo \(u\) comienza por visitar el máximo nivel en head e ir bajando hasta determinar \(u.dato > head[level].dato\); en ese momento se debe avanzar al nodo apuntado por \(head[level]\) y repetir el algoritmo hasta que \(level=1\), en cuyo caso encontramos el lugar de inserción del nuevo dato. Se procede a reasignar los punteros de los sucesores y ajustar los punteros hacia los nodos sucesores a los niveles que tiene \(u\).
Cada inserción tiene un costo \(O(\log_{1/p} n)\), garantía probabilística; por lo que insertar \(n\) elementos tiene un costo: \[ \sum_{i=1}^n O(\log_{1/p} i) = O(\log_{1/p} \prod_{i=1}^n i) = O(\log_{1/p} {n!}) = O(n \log n); \] usando la aproximación de Stirling.
A diferencia de la versión basada en arreglos, una skip list es capaz de aceptar nuevos elementos y mantener el orden de manera eficiente.
Las lecturas de este tema corresponden al capítulo 5 de (Knuth 1998), en específico 5.2 Internal sorting. También se recomienda leer y comprender la parte II de (Cormen et al. 2022), que corresponde a Sorting and order statistics, en partícular Cap. 6 y 7, así como el Cap. 8.1. El artículo de wikipedia https://en.wikipedia.org/wiki/Sorting_algorithm también puede ser consultado con la idea de encontrar una explicación rápida de los algoritmos.
En la práctica, pocos algoritmos son mejores que quicksort. En (Loeser 1974) se detalla una serie de experimentos donde se compara quicksort contra otros algoritmos relacionados; por lo que es una lectura recomendable.
La parte adaptable, esto es para algoritmos oportunistas que toman ventaja de instancias simples, esta cubierta por el artículo (Estivill-Castro y Wood 1992). En especial, es muy necesario comprender las secciones 1.1 y 1.2, el resto del artículo debe ser leído aunque no invierta mucho tiempo en comprender las pruebas expuestas si no le son claras. En especial, en las secciones indicadas se establecen las medidas de desorden contra las cuales se mide la complejidad. En (Cook y Kim 1980) realiza una comparación del desempeño de varios algoritmos para ordenamiento de listas casi ordenadas, esto es, en cierto sentido donde los algoritmos adaptables tienen sentido. Este artículo es anterior a (Estivill-Castro y Wood 1992) pero tiene experimentos que simplifican el entendimiento de los temas.
Aproximación de Stirling https://en.wikipedia.org/wiki/Stirling%27s_approximation.↩︎