Algorithm VisionMaster Algorithms

El algoritmo de ordenamiento más básico que compara repetidamente elementos adyacentes y los intercambia si están en orden incorrecto. Como burbujas que suben a la superficie, los valores más grandes se mueven gradualmente al final del arreglo. Ideal para conjuntos de datos pequeños o con fines educativos para comprender los fundamentos del ordenamiento.

Encuentra el elemento más pequeño y lo mueve al frente repetidamente. Cada iteración "selecciona" el mínimo de los elementos restantes y lo coloca después de la porción ordenada. Fácil de implementar con uso mínimo de memoria, pero siempre toma tiempo O(n²) independientemente de la entrada.

Un algoritmo de ordenamiento altamente eficiente que selecciona un elemento pivote y particiona el arreglo con valores más pequeños a la izquierda y más grandes a la derecha. Promedia O(n log n) y es el método de ordenamiento más utilizado en la práctica. Forma la base de las funciones de ordenamiento integradas en la mayoría de los lenguajes de programación.

Utiliza una estructura de datos de montículo binario construyendo primero un montículo máximo, luego extrayendo repetidamente el elemento raíz para ordenar. Garantiza complejidad de tiempo O(n log n) en todos los casos sin requerir memoria adicional. También sirve como base para implementaciones de colas de prioridad.

Un algoritmo de ordenamiento sin comparación que cuenta las ocurrencias de cada elemento y usa aritmética para determinar posiciones. Logra complejidad de tiempo O(n+k) donde k es el rango de valores de entrada. Ideal para ordenar enteros dentro de un rango conocido y limitado. Forma la base del ordenamiento radix.

Un algoritmo de ordenamiento sin comparación que procesa elementos dígito por dígito del menos significativo al más significativo. Usa counting sort como subrutina para cada posición de dígito. Logra tiempo O(d(n+k)) donde d es el número de dígitos. Excelente para ordenar enteros o cadenas de longitud fija.

Una optimización del ordenamiento por inserción que permite el intercambio de elementos que están muy separados. Usa una secuencia de brechas que disminuye a 1, permitiendo que el algoritmo mueva elementos más cerca de sus posiciones finales más rápido. Nombrado en honor a Donald Shell, quien lo inventó en 1959.

Un algoritmo de ordenamiento basado en distribución que distribuye elementos en varios cubos. Luego, cada cubo se ordena individualmente usando otro algoritmo de ordenamiento. Funciona mejor cuando la entrada está distribuida uniformemente en un rango. La complejidad de tiempo promedio es O(n+k).

Un algoritmo de divide y vencerás que divide el arreglo por la mitad, ordena cada mitad recursivamente y luego las fusiona nuevamente. Garantiza tiempo O(n log n) y es estable, pero requiere memoria adicional. Particularmente efectivo para conjuntos de datos grandes y ordenamiento de listas enlazadas.

Funciona como ordenar cartas de juego en tus manos: insertando cada elemento uno a la vez en su posición correcta. Se ejecuta en tiempo O(n) para datos ya ordenados, lo que lo hace muy eficiente para arreglos pequeños o conjuntos de datos casi ordenados. Algoritmo simple pero adaptativo.

Mejora del ordenamiento burbuja que elimina valores pequeños cerca del final de la lista (tortugas). Usa una secuencia de brechas decrecientes comenzando con la longitud del arreglo, mejorando la complejidad del peor caso. Práctico para conjuntos de datos de tamaño medio donde se valora la simplicidad de implementación sobre el rendimiento óptimo.

Algoritmo de ordenamiento simple similar al ordenamiento por inserción, nombrado por la forma en que los gnomos de jardín ordenan macetas de flores. Se mueve hacia atrás cuando los elementos están fuera de orden, luego hacia adelante nuevamente. Aunque O(n²) como el ordenamiento burbuja, su simplicidad lo hace útil para enseñar conceptos de ordenamiento y manejar conjuntos de datos pequeños.

Método de búsqueda altamente eficiente que compara el objetivo con el elemento central y reduce repetidamente el espacio de búsqueda a la mitad. Con tiempo O(log n), puede encontrar un elemento en 1 millón de elementos en solo 20 comparaciones. Funciona como buscar palabras en un diccionario.

El método de búsqueda más básico que verifica cada elemento secuencialmente desde el principio hasta el final. Se usa para datos no ordenados o arreglos pequeños donde la simplicidad es importante. La implementación es sencilla, pero se vuelve lenta con conjuntos de datos grandes requiriendo tiempo O(n).

Explora un grafo nivel por nivel, visitando todos los vértices en la profundidad actual antes de avanzar más profundo. Usa una cola y es ideal para encontrar caminos más cortos en grafos no ponderados. Las aplicaciones incluyen resolución de laberintos, análisis de redes sociales y encontrar conexiones entre nodos.

Explora un grafo yendo lo más profundo posible a lo largo de cada camino antes de retroceder. Se implementa usando una pila o recursión, lo que lo hace natural para problemas recursivos. Se usa para búsqueda de caminos, detección de ciclos, ordenamiento topológico y generación de laberintos.

Encuentra los caminos más cortos desde un vértice fuente único a todos los demás vértices en un grafo ponderado. Impulsa sistemas de navegación GPS y protocolos de enrutamiento de redes. Funciona eficientemente con pesos de arista no negativos usando un enfoque codicioso con una cola de prioridad.

Un algoritmo de búsqueda best-first que encuentra el camino más corto usando heurísticas. Combina el algoritmo de Dijkstra y la búsqueda codiciosa best-first usando f(n) = g(n) + h(n). Ampliamente utilizado en juegos, robótica y navegación GPS para búsqueda eficiente de caminos.

Encuentra el Árbol de Expansión Mínima (MST) de un grafo no dirigido ponderado. Usa un enfoque codicioso ordenando aristas por peso y agregándolas si no crean un ciclo. Emplea Union-Find para detección eficiente de ciclos. Esencial para diseño de redes y agrupamiento.

Encuentra el Árbol de Expansión Mínima (MST) haciendo crecer un árbol desde un vértice inicial. Siempre agrega la arista de peso mínimo que conecta un vértice en el árbol con uno fuera. Usa una cola de prioridad para selección eficiente de aristas. Ideal para grafos densos.

Ordena vértices de un Grafo Acíclico Dirigido (DAG) de modo que para cada arista u→v, u viene antes de v. Usa enfoque basado en DFS. Esencial para resolución de dependencias, sistemas de construcción y programación de cursos.

Algoritmo de Google para clasificar páginas web por estructura de enlaces. Calcula puntuaciones de importancia iterativamente.

También conocido como el algoritmo de la 'tortuga y la liebre', esta elegante técnica detecta ciclos en listas enlazadas o secuencias usando espacio O(1). Usa dos punteros que se mueven a diferentes velocidades; si hay un ciclo, eventualmente se encontrarán. Esencial para detectar bucles infinitos, analizar estructuras de grafos y validar la integridad de los datos.

Algoritmo de camino más corto desde un origen único que maneja pesos negativos y detecta ciclos negativos. Relaja todas las aristas V-1 veces para garantizar distancias correctas incluso con pesos negativos. Esencial para detección de arbitraje de divisas, enrutamiento de redes con costos variados y situaciones donde el algoritmo de Dijkstra falla. Intercambia velocidad por flexibilidad.

Algoritmo de caminos más cortos entre todos los pares que calcula distancias entre cada par de vértices en tiempo O(V³). Usa programación dinámica con lógica central elegante de tres líneas. Maneja pesos negativos y proporciona cierre transitivo. Ideal para grafos densos, análisis de redes y cuando se necesitan todas las distancias por pares.

Algoritmo codicioso que construye un árbol de expansión mínima agregando aristas en orden de peso creciente, usando union-find para evitar ciclos. Eficiente para grafos dispersos con complejidad de tiempo O(E log E). Las aplicaciones incluyen diseño de redes, agrupamiento, algoritmos de aproximación y comprensión de pruebas de corrección codiciosa.

Algoritmo codicioso que hace crecer un árbol de expansión mínima agregando repetidamente la arista más barata que conecta el árbol a un nuevo vértice. Usa una cola de prioridad para eficiencia con tiempo O(E log V). Preferido para grafos densos y aplicaciones en tiempo real como difusión de redes y diseño de circuitos.

Algoritmo de Knuth-Morris-Pratt para coincidencia eficiente de patrones en cadenas. Usa una función de falla (arreglo LPS) para saltar comparaciones innecesarias, logrando complejidad de tiempo O(n+m). Esencial para búsqueda de texto, análisis de secuencias de ADN y detección de plagio.

Algoritmo eficiente de búsqueda de cadenas usando heurísticas de carácter malo y sufijo bueno. Compara el patrón de derecha a izquierda, permitiendo grandes saltos en caso de no coincidencia. Logra tiempo sublineal en la práctica, convirtiéndolo en uno de los algoritmos de coincidencia de cadenas más rápidos.

Encuentra la forma óptima de colocar paréntesis en una cadena de matrices para minimizar el número de multiplicaciones escalares. Problema clásico de programación dinámica del Capítulo 15 de CLRS.

Calcula números de Fibonacci eficientemente usando programación dinámica para evitar cálculos redundantes. Demuestra el poder de la memoización al transformar una solución recursiva de tiempo exponencial en un algoritmo de tiempo lineal. Una introducción clásica a los conceptos de programación dinámica.

Encuentra la subsecuencia más larga presente en dos secuencias en el mismo orden. Usa programación dinámica para construir una tabla de soluciones. Las aplicaciones incluyen alineación de secuencias de ADN, herramientas de diferencia de archivos (diff) y detección de plagio.

Algoritmo de programación dinámica que calcula el número mínimo de ediciones de un solo carácter (inserciones, eliminaciones, sustituciones) requeridas para transformar una cadena en otra. Fundamental en corrección ortográfica, alineación de secuencias de ADN y procesamiento de lenguaje natural.

Problema clásico de programación dinámica donde debes seleccionar elementos con pesos y valores dados para maximizar el valor total mientras te mantienes dentro de una capacidad de peso. Cada elemento solo se puede tomar una vez (0/1). Las aplicaciones incluyen asignación de recursos, optimización de cartera y carga de mercancías.

Encuentra la subsecuencia más larga donde todos los elementos están en orden creciente. Problema clásico de programación dinámica.

Elegante algoritmo de programación dinámica que encuentra el subarreglo contiguo con suma máxima en tiempo O(n). Combina principios codiciosos y de programación dinámica al decidir en cada paso si extender el subarreglo actual o comenzar uno nuevo. Esencial para optimización de beneficios en bolsa, procesamiento de señales y comprensión de técnicas de optimización de programación dinámica.

Problema clásico de programación dinámica que encuentra el número mínimo de monedas necesarias para hacer una cantidad objetivo. Demuestra subestructura óptima donde la solución depende de soluciones a cantidades más pequeñas. Ampliamente aplicado en sistemas financieros, máquinas expendedoras y optimización de asignación de recursos.

Problema de programación dinámica que encuentra el número mínimo de cortes necesarios para particionar una cadena en subcadenas palindrómicas. Usa programación dinámica para precalcular qué subcadenas son palíndromos, luego encuentra los cortes óptimos. Las aplicaciones incluyen segmentación de texto, análisis de secuencias de ADN y problemas de optimización de cadenas.

Colocar N reinas de ajedrez en un tablero de ajedrez N×N de modo que ninguna reina amenace a otra. Un algoritmo clásico de retroceso.

Encuentra todos los números primos hasta n marcando iterativamente los compuestos. Nombrado en honor a Eratóstenes de Cirene (c. 276-194 a.C.).

Arreglo triangular de coeficientes binomiales donde cada número es la suma de los dos números directamente encima de él. Nombrado en honor a Blaise Pascal (1623-1662), aunque conocido por matemáticos siglos antes. Demuestra hermosos patrones matemáticos incluyendo expansión binomial, combinatoria y conexiones con los números de Fibonacci.

Algoritmo antiguo de alrededor del 300 a.C. que calcula eficientemente el máximo común divisor de dos enteros. Basado en el principio de que MCD(a, b) = MCD(b, a mod b). Uno de los algoritmos más antiguos en uso continuo, formando la base de la teoría de números, criptografía y simplificación de fracciones.

Extiende el algoritmo euclídeo para encontrar enteros x e y que satisfacen la identidad de Bézout: ax + by = MCD(a, b). No solo calcula el MCD sino que también encuentra los coeficientes de combinaciones lineales. Fundamental para aritmética modular, criptografía RSA y resolución de ecuaciones diofánticas lineales.

Algoritmo fundamental de aprendizaje automático no supervisado para particionar datos en k grupos. Asigna iterativamente puntos a los centroides más cercanos y actualiza las posiciones de los centroides. Ampliamente utilizado en segmentación de clientes, compresión de imágenes y análisis exploratorio de datos.

Estructura de datos basada en árboles que almacena cadenas eficientemente compartiendo prefijos comunes. Cada camino desde la raíz hasta una hoja representa una palabra o clave. Sobresale en autocompletado, corrección ortográfica, tablas de enrutamiento IP e implementaciones de diccionarios con operaciones O(m) donde m es la longitud de la clave.

Encuentra el nodo más profundo que es ancestro de dos nodos dados en un árbol. Operación fundamental en consultas de árboles con aplicaciones en biología computacional (evolución de especies), enrutamiento de redes y sistemas de control de versiones. Varios algoritmos ofrecen diferentes compensaciones entre tiempo y espacio.

Primer árbol de búsqueda binaria auto-balanceado inventado en 1962 por Adelson-Velsky y Landis. Mantiene el equilibrio de altura mediante rotaciones, garantizando operaciones O(log n). El equilibrio más estricto que los árboles rojo-negro lo hace ideal para aplicaciones con muchas búsquedas como bases de datos y sistemas de archivos.

Selecciona el número máximo de actividades no superpuestas. Algoritmo codicioso clásico que siempre elige la actividad que termina más temprano.