सरल छंटाई एल्गोरिदम

Capítulo 9: Algoritmos de ordenamiento simples

Introducción

• Capítulo sobre algoritmos de ordenamiento elementales.
• Fáciles de implementar para entender los conceptos.
• No eficientes para grandes conjuntos de datos.
• Útiles para conjuntos de datos pequeños o como bloques para algoritmos más complejos.

Bubble sort (ordenamiento de burbuja)

• Funciona pasando repetidamente por la lista, comparando elementos adyacentes.
• Intercambia los elementos si están en el orden incorrecto.
• El elemento más grande "burbujea" a su posición correcta al final de cada pase.
• Algoritmo:
  • Comenzar con el primer elemento de la lista.
  • Comparar el elemento actual con el siguiente.
  • Si el elemento actual es mayor que el siguiente, intercambiarlos.
  • Moverse al siguiente elemento y repetir hasta el final de la lista.
  • Repetir el proceso para n-1 pases, donde n es el número de elementos.

Pseudocódigo

for (i = 0; i < n-1; i++) {
    for (j = 0; j < n-i-1; j++) {
        if (arr[j] > arr[j+1]) {
            swap(arr[j], arr[j+1]);
        }
    }
}

• Ejemplo: [5, 1, 4, 2, 8]
  • Primer pase:
    • (5 1 4 2 8) -> (1 5 4 2 8)
    • (1 5 4 2 8) -> (1 4 5 2 8)
    • (1 4 5 2 8) -> (1 4 2 5 8)
    • (1 4 2 5 8) -> (1 4 2 5 8)
  • Segundo pase:
    • (1 4 2 5 8) -> (1 4 2 5 8)
    • (1 4 2 5 8) -> (1 2 4 5 8)
    • (1 2 4 5 8) -> (1 2 4 5 8)
  • Tercer pase:
    • (1 2 4 5 8) -> (1 2 4 5 8)
    • (1 2 4 5 8) -> (1 2 4 5 8)
• Propiedades:
  • Complejidad temporal:
    • $O(n^2)$ en el caso promedio y peor.
    • $O(n)$ en el mejor de los casos (si ya está ordenado).
  • Complejidad espacial: $O(1)$
  • Estable: Sí.

Selection sort (ordenamiento por selección)

• Realiza solo un intercambio por cada pase en la lista.
• Encuentra repetidamente el elemento mínimo del parte desordenada y lo coloca al principio.
• Algoritmo:
  • Encontrar el valor mínimo en la lista.
  • Intercambiar con el valor en la primera posición.
  • Repetir para el resto de la lista (comenzando en la segunda posición).

Pseudocódigo

for (i = 0; i < n-1; i++) {
    int min_idx = i;
    for (j = i+1; j < n; j++) {
        if (arr[j] < arr[min_idx]) {
            min_idx = j;
        }
    }
    swap(arr[i], arr[min_idx]);
}

• Ejemplo: [64, 25, 12, 22, 11]
  • Primer pase:
    • [64, 25, 12, 22, 11] -> [11, 25, 12, 22, 64]
  • Segundo pase:
    • [11, 25, 12, 22, 64] -> [11, 12, 25, 22, 64]
  • Tercer pase:
    • [11, 12, 25, 22, 64] -> [11, 12, 22, 25, 64]
• Propiedades:
  • Complejidad temporal: $O(n^2)$ en todos los casos.
  • Complejidad espacial: $O(1)$
  • Inestable: Sí.

Insertion sort (ordenamiento por inserción)

• Construye la lista ordenada final un elemento a la vez.
• Mucho menos eficiente que algoritmos más avanzados para listas grandes.
• Algoritmo:
  • Iterar desde arr[1] a arr[n].
  • Comparar el elemento actual (clave) con su predecesor.
  • Si el elemento clave es menor que su predecesor, comparar con los elementos anteriores.
  • Mover los elementos mayores una posición arriba para hacer espacio para el elemento intercambiado.

Pseudocódigo

for (i = 1; i < n; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
        arr[j+1] = arr[j];
        j = j - 1;
    }
    arr[j+1] = key;
}

• Ejemplo: [12, 11, 13, 5, 6]
  • Primer pase:
    • 12 11 13 5 6 -> 11 12 13 5 6
  • Segundo pase:
    • 11 12 13 5 6 -> 11 12 13 5 6
  • Tercer pase:
    • 11 12 13 5 6 -> 11 12 5 13 6 -> 11 5 12 13 6 -> 5 11 12 13 6
  • Cuarto pase:
    • 5 11 12 13 6 -> 5 11 12 6 13 -> 5 11 6 12 13 -> 5 6 11 12 13
• Propiedades:
  • Complejidad temporal:
    • $O(n^2)$ en los casos promedio y peor.
    • $O(n)$ en el mejor caso (si ya está ordenado).
  • Complejidad espacial: $O(1)$
  • Estable: Sí.

Conclusión

• Se exploraron Bubble Sort, Selection Sort e Insertion Sort.
• Fáciles de entender e implementar, pero no eficientes para grandes conjuntos de datos debido a $O(n^2)$.
• Los siguientes capítulos cubrirán algoritmos más avanzados.

Química Orgánica

Nomenclatura IUPAC

Alcanos

• Identificar la cadena continua más larga de átomos de carbono: Define el nombre base del alcano.
• Numerar la cadena principal: Comenzar en el extremo que le dé a los sustituyentes el número localizador más bajo posible.
• Nombrar y numerar los sustituyentes: Usar di-, tri-, tetra-, etc., si hay dos o más sustituyentes idénticos.
• Combinar nombres y números de los sustituyentes con el nombre base: Ordenar sustituyentes alfabéticamente.

Alquenos y Alquinos

• Identificar la cadena continua más larga que contenga el doble o triple enlace: Define el nombre base del alqueno o alquino.
• Numerar la cadena principal: Comenzar en el extremo que le dé al doble o triple enlace el número localizador más bajo posible.
• Nombrar y numerar los sustituyentes: Usar di-, tri-, tetra-, etc., si hay dos o más sustituyentes idénticos.
• Combinar los nombres y números de los sustituyentes con el nombre base del alqueno o alquino: Ordenar los sustituyentes alfabéticamente.

Grupos funcionales comunes

Isomería

• Isómeros estructurales: Misma fórmula molecular, diferente conectividad.
• Estereoisómeros: Misma fórmula molecular y conectividad, diferente disposición espacial.
  • Enantiómeros: Imágenes especulares no superponibles.
  • Diastereoisómeros: Estereoisómeros que no son enantiómeros.

Algoritmos Greedy (glotones)

• Se basan en tomar la opción localmente óptima en cada paso.
• Buscan un óptimo global.
• No garantizan una solución óptima.
• Pueden producir soluciones localmente óptimas que se aproximan a una solución óptima global en tiempo razonable.

Diseño de un algoritmo Greedy

1. El problema de optimización debe ser expresable como una secuencia de decisiones.
2. Debe existir una elección greedy, que sea localmente óptima. La elección debe permitir alcanzar la solución óptima global
3. Se debe probar que la elección greedy en cada paso permite obtener una solución óptima global.

Ejemplo: Problema de la mochila fraccionaria (Knapsack Problem)

• ladrón con una mochila de capacidad $W$.
• $n$ objetos en la tienda, objeto $i$ vale $v_i$ $ y pesa $w_i$ kg.
• El ladrón puede tomar fracciones de objetos.
• Maximizar el valor total de los objetos en la mochila

Algoritmo greedy

1. Calcular la razón de valor por kg de cada objeto: $v_i/w_i$.
2. Ordenar objetos en orden decreciente de valor por kg.
3. Añadir objetos a la mochila en orden hasta que esté llena.

Demostración

• Si la solución óptima no contiene el objeto con el mayor valor por kg.
• Se puede reemplazar una parte de los objetos en la solución óptima por el objeto con el mayor valor por kg.
• Esto aumenta el valor total en la mochila, contradiciendo la optimalidad de la solución inicial.

Complejidad

• $O(n \log n)$ para ordenar los objetos por valor por kg.

Ejemplo: Problema de cobertura de conjuntos (Set Cover)

• Dado un conjunto de elementos $U$ y subconjuntos $S = {S_1, S_2,..., S_n}$ de $U$.
• Encontrar un subconjunto de $S$ de tamaño mínimo cuya unión sea igual a $U$.

Algoritmo greedy

1. Seleccionar el subconjunto $S_i$ que contiene el mayor número de elementos no cubiertos.
2. Añadir $S_i$ a la solución.
3. Repetir hasta que todos los elementos estén cubiertos.

Demostración

• Algoritmo greedy para cobertura de conjuntos es un algoritmo de aproximación.
• No garantiza solución óptima, pero garantiza que la solución esté a un factor $H(n)$ de la solución óptima (n-ésimo número armónico).

Complejidad

• $O(n \sum_{S_i \in S} |S_i|)$, donde $n$ es el número de subconjuntos en $S$ y $|S_i|$ es el tamaño del subconjunto $S_i$.