Algoritmos de Ordenación
En esta sección, exploraremos varios algoritmos de ordenación comunes y sus características.
Algoritmo de la Burbuja
En el algoritmo de la burbuja, recorremos todo el array desde las primeras posiciones y vamos comparando el primer elemento con el siguiente. Si es mayor, los intercambiamos; si es menor, lo dejamos como está y pasamos al siguiente elemento, realizando las mismas comparaciones. En cada iteración, el elemento más «pesado» queda ordenado. El número de veces que se repiten los bucles es independiente de los datos, pero el número de veces que se ejecuta la operación de intercambio sí que depende del valor de los datos.
Algoritmo de Selección
En el algoritmo de selección, primero recorremos todos los elementos del array buscando el más pequeño y lo intercambiamos con el que esté en la primera posición. Después, volvemos a buscar el elemento más pequeño y lo volvemos a intercambiar con el que esté en la segunda posición, y así sucesivamente hasta que el array quede ordenado.
Algoritmo de Inserción
En el algoritmo de inserción, se divide el array en dos partes: la parte que está ordenada y la que no. Para ello, cogemos el primer elemento y lo comparamos con el de su izquierda. Al ser el primero, no tiene ninguno a su izquierda, entonces ya está ordenado. Cogemos el segundo elemento, si es menor que el de su izquierda, lo intercambiamos, y estos dos ya están ordenados. Volvemos a comparar con el de la izquierda y, como no tiene, cogemos el siguiente. Si realizamos esto sucesivamente, vemos cómo los valores van quedando ordenados en el lado izquierdo del array y desordenados en el lado derecho hasta que llegamos al final.
La diferencia entre estos tres algoritmos sería la forma en la que se altera el orden del array.
Algoritmo Merge Sort
El algoritmo Merge Sort sigue los tres pasos de la estrategia «divide y vencerás»:
- Dividir: El array se parte en dos subarrays del mismo tamaño aproximadamente.
- Conquistar: Ordena los elementos de cada subarray.
- Combinar: Mezcla los elementos de los subarrays ordenados para obtener un array ordenado.
Algoritmo Quick Sort
El algoritmo Quick Sort también sigue la estrategia «divide y vencerás», pero se diferencia de Merge Sort en que no divide el array por el medio, sino que usa un splitter para hacer la división. No necesita un array temporal para hacer las ordenaciones y realiza el trabajo principal durante la etapa de división, mientras que Merge Sort lo utiliza en la etapa de conquista.
Existen dos diferencias principales entre los tres primeros algoritmos descritos y los dos últimos. La primera es que los tres primeros algoritmos son menos eficientes, ya que siguen la estrategia de comparación por pares de elementos y los intercambian cuando no mantienen el orden, mientras que Merge Sort y Quick Sort siguen la estrategia de comparar y distribuir los elementos en grupos ordenados, pero donde los elementos individuales no tienen por qué estar ordenados. La otra diferencia es que los tres primeros utilizan un bucle que va iterando sobre los elementos, mientras que los dos últimos utilizan la estrategia de «divide y vencerás».
Árbol de Expansión Mínima
Un árbol de expansión mínima (o árbol generador mínimo) es un árbol que utiliza todos los nodos del grafo, de tal manera que el coste total de sumar las aristas del grafo es mínimo. Esto es, la suma del coste de todas las aristas ha de ser mínima. El algoritmo de Prim es el encargado de generar ese árbol de expansión mínima.
Árbol Balanceado
Un árbol balanceado es un árbol ordenado, donde para todos los nodos, la diferencia en altura entre la rama izquierda y la derecha es +1, 0 o -1. Sirve, por ejemplo, para representar un vector o array de números desordenados como un árbol balanceado, el cual primero ordenamos usando alguno de los métodos de ordenación y luego vamos dividiendo más o menos por la mitad y vamos representando los nodos del vector.
Cola de Prioridad
Una cola de prioridad es aquella en la que cada elemento tiene una prioridad asociada, siendo el elemento con mayor prioridad el que sale primero de la cola. Normalmente, se considera que tiene mayor prioridad el elemento con un valor de prioridad más pequeño y, por ello, se suele usar un min-heap para implementar las colas de prioridad. Es decir, el elemento con mayor prioridad es el que está en la raíz del min-heap. Por ejemplo, en una cola de supermercado, en una cola de embarque de un aeropuerto o en el servicio de urgencias de un hospital.
Espacio de Soluciones
Los algoritmos de backtracking determinan las soluciones del problema buscando sistemáticamente en el espacio de soluciones del problema. Esta búsqueda se puede representar en el árbol de soluciones asociado al conjunto de soluciones del problema. En dicho árbol, el espacio de soluciones viene definido por todos los caminos desde el nodo raíz a un nodo hoja.
Comprobación Previa para Aplicar el Algoritmo de Dijkstra
Lo primero sería comprobar que el grafo es conexo, esto quiere decir que todos los nodos tienen aristas y están conectados. Habría que recorrer toda la lista de nodos y comprobar cuántas aristas tienen de entrada, de modo que el objeto nodo tiene una serie de atributos, entre ellos las aristas de entrada y las aristas de salida. Si tuviéramos nodos inconexos, habría que eliminarlos o bien aplicar el algoritmo de Dijkstra en el subgrafo que sí es conexo.
Grafos Densos y Grafos Dispersos
Un grafo denso es un grafo en el que el número de aristas es cercano al número máximo de aristas posibles, es decir, a las que tendría si el grafo fuera completo (número de aristas a es cercano a n(n-1)/2). Al contrario, un grafo disperso es un grafo con un número de aristas muy bajo, es decir, cercano al que tendría si fuera un grafo vacío (en este caso a es próximo a n). Viendo esto con los algoritmos vistos en clase, tenemos que para grafos densos el orden de complejidad del algoritmo de Kruskal es O(n2*logn), peor que la complejidad O(n2) de Prim, y en los grafos dispersos, el algoritmo de Kruskal es de orden O(nlogn), comportándose, probablemente, de forma más eficiente que el de Prim.