Algoritmos de ordenación

En el A. De la burbuja, recorremos todo el array desde las primeras posiciones y vamos comparando el primer elemento con el siguiente de al lado si es mayor los intercambiamos si es menor lo dejamos como está y pasamos al siguiente elemento y hacemos 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 si que dependen del valor de los datos.

En el A. D 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.

 En el A. D 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 como 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.

El A. Merge_sort sigue los tres pasos de la estrategia Divide y conquista:

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.

El A. Quicksort también sigue la estrategia Divide y conquista pero se diferencia con merge_sort en que no divide el array por el medio si no que usa un splitter para hacer la división, no ncesita 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 intercambia cuando no mantienen el orden mientras que merge_sort y Quicksort 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 conquista”.

Á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 ene l 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.

¿Cuál sería la comprobación previa para aplicar el algoritmo de Dijstrka?

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 cuantas 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 Dijstrka 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º 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(n²*logn), peor que la complejidad O(n²) 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.