Algoritmos fundamentales

Arturo García Flores

Universidad Autónoma Metropolitana–Iztapalapa
Durante el desarrollo de un programa de computadora se implementa algún método ideado de
forma previa con el objetivo de resolver un problema. Este método es independiente del lenguaje
de programación que se emplea y quien determina los pasos a seguir para resolver el problema,
incluso más que el programa de computadora en sí mismo. En computación, el término algoritmo
se refiere a un método finito y eficaz de resolución de problemas. Por ello, en este escrito presento
7 de mayo de 2022
a los algoritmos como el objeto central de estudio de la informática.

1. Introducción 2. Pseudocódigo

La palabra algoritmo se refiere a un método paso a paso pa- Antes de desarrollar un programa para resolver un pro-
ra resolver un problema en lenguaje natural o escribiendo un blema en particular, se debe contar con una comprensión
programa de computadora que implemente el procedimien- completa del problema y un enfoque de solución cuidadosa-
to [1]. Por ejemplo, el algoritmo de Euclides es un método mente planificado. Para ello sirve un pseudocódigo.
para encontrar el máximo común divisor de dos números A El pseudocódigo es un lenguaje artificial e informal con
y B (figura 1a). Este algoritmo se puede transcribir en un len- el cual se representa a un algoritmo. Es similar al español u
guaje de programación para ser ejecutado en un ordenador otro idioma: conveniente y fácil de usar, aunque no es un
(figura 1b) [2, 3]. lenguaje de programación. Por lo general, posee una sinta-
La idea de un algoritmo informático se atribuye a Ada xis propia para representar a un algoritmo [6, 7]. Algunas
Augusta, quien amplió los estudios de Babbage sobre cómo reglas semánticas y sintácticas se pueden discernir a partir
funcionaría una «máquina analítica», reconociendo que su del pseudocódigo del algoritmo de Euclides (figura 2):
importancia radica en la posibilidad de utilizar una secuencia
1. Está limitado por las etiquetas INICIO y FIN, las ins-
dada de instrucciones de forma repetida, siendo el número de
trucciones se escriben en mayúsculas, las variables en
veces preasignado o dependiente de los resultados del cálculo
minúsculas y los mensajes en forma de oración
[4]. Esta es la esencia de un algoritmo informático.
La mayoría de los algoritmos de interés involucran la or- 2. La lectura de datos se representa con la etiqueta LEER;
ganización de los datos involucrados durante el cómputo. la escritura de datos, con la etiqueta ESCRIBIR.
Tal organización conduce a estructuras de datos que surgen
3. La declaración de variables la define un identificador (a
como productos finales de los algoritmos y que, por tanto,
y b) seguido de dos puntos y el tipo de dato (ENTERO).
debemos estudiar para comprender los algoritmos [5].
Cabe mencionar que los algoritmos no son una herramien- 4. La declaración de una función (FUNC) se constituye de
ta exclusiva de las matemáticas o de la computación. Nuestra un identificador que corresponde con el nombre de la
vida cotidiana se rodea de diversos casos de algoritmos, co- fuinción (mcd()).
mo los pasos a seguir para preparar un guisado, armar un
mueble o llenar un formulario. 5. Las estructuras de control de flujo se declaran de dis-
tintas formas según sea el caso. El pseudocófigo de la
figura 2 emplea una estructura de control condicional
Calcula el máximo común divisor de dos
SI-DE LO CONTRARIO.
enteros no negativos A y B de la forma
siguiente:
Si B es 0, la respuesta es A. Si no, divide
INICIO
A entre B y toma el resto R. La
ESCRIBIR "Ingresa los valores de A y B"
respuesta es el máximo común divisor de
LEER a, b: ENTERO
B y R.
FUNC mcd()
(a) Algoritmo de Euclides en lenguaje natural (español) SI b == 0 ENTONCES
ESCRIBIR "El MCD es:" a
int mcd(int a, int b){
FIN SI
if (b == 0)
DE LO CONTRARIO
return a;
r == a % b
int r = a % b;
ESCRIBIR "El MCD es:" mcd(b,r)
return mcd(b,r);
FIN DE LO CONTRARIO
}
FIN FUNC
(b) Algoritmo de Euclides en lenguaje de programación (C++) FIN
Figura 1: El algoritmo de Euclides es un conjunto de instrucciones Figura 2: De acuerdo con el pseudocódigo, si la expresión lógica se
definidas, ordenadas y acotadas para resolver un problema: hallar cumple, se ejecutan las instrucciones del bloque SI; si no se cumple,
el máximo común divisor entre dos números enteros positivos. se ejecutan las instrucciones del bloque DE LO CONTRARIO.

Página 1
3. Algoritmos 1. Escribe una función para buscar un elemento x dado
en un arreglo arr[] de n elementos.
Los algoritmos nos brindan el potencial de obtener gran-
des ahorros, incluso hasta el punto de permitirnos realizar 2. Inicia la búsqueda desde el extremo izquierdo del arre-
tareas que de otro modo serían imposibles. Por esta razón, glo arr[] y compara x con cada elemento de arr[].
el diseño cuidadoso del algoritmo es una parte en extremo
efectiva del proceso de resolución de un gran problema [8]. 3. Devuelve el índice, si x coincide con un elemento.
La elección del mejor algoritmo puede ser un proceso com-
4. Devuelve -1, si x no coincide con un elemento.
plicado que quizás implique un análisis matemático sofisti-
cado. Por otro lado, no debemos usar un algoritmo sin tener
El algoritmo anterior se muestra en lenguaje de programa-
idea de qué recursos podría consumir. Por ello, repasaremos
ción en la figura 3.
los algoritmos más importantes en informática: algoritmos
de búsqueda, de ordenamiento y voraces [9].
int buscar(int arr[], int n, int x){
int i;
3.1. Algoritmos de búsqueda for (i = 0; i < n; i++)
El desarrollo de la tecnología, en particular de la informá- if (arr[i] == x)
return i;
tica moderna, han hecho accesible una gran cantidad de
return -1;
información. Esto implica que la capacidad de buscar de for-
}
ma eficiente a través de esta información sea fundamental
para procesarla. int main(void){
Los algoritmos de búsqueda han demostrado ser efecti- int arr[] = {2,4,6,8,10};
vos en numerosas aplicaciones durante décadas. Sin este int x = 2;
tipo de algoritmos, el desarrollo científico y tecnológico que int n = sizeof(arr) / sizeof(arr[0]);
disfrutamos cada día no sería posible [10, 11].
int r = buscar(arr, n, x);
(r == -1)
3.1.1. Tablas de símbolos ? cout << x << " no se encuentra en
El término tabla de símbolos se emplea para describir un el arreglo."
mecanismo donde se almacena información (un valor) que : cout << x << " se encuentra en el
lugar " << r << " del arreglo.";
luego se puede buscar y recuperar especificando una clave.
return 0;
La naturaleza de las claves y los valores depende de la apli-
}
cación. Existe una gran cantidad de claves y de información,
(a) Algoritmo de búsqueda lineal en lenguaje de programación (C++)
por lo que implementar una tabla de símbolos eficiente es
un desafío computacional significativo [12, 13]. 2 se encuentra en el lugar 0 del arreglo.
La búsqueda es muy importante en la mayor parte de las
(b) Mensaje de salida
aplicaciones informáticas, por lo que las tablas de símbo-
los están disponibles como abstracciones de alto nivel en Figura 3: La búsqueda lineal es un algoritmo de búsqueda secuen-
muchos entornos de programación. La tabla 1 proporcio- cial donde se inicia desde un extremo y se verifica cada elemento
de un conjunto hasta encontrar el elemento deseado.
na algunos ejemplos de claves y valores que se emplean en
aplicaciones típicas.
La búsqueda lineal rara vez se usa en la práctica, debido a
que otros algoritmos de búsqueda, como el algoritmo de bús-
3.1.2. Búsqueda lineal
queda binaria, permiten una comparación de búsqueda más
Una búsqueda lineal es el método más simple de buscar rápida. Sin embargo, la búsqueda lineal tiene la ventaja de
un conjunto de datos. Desde el inicio, cada elemento de este que funcionará con cualquier conjunto de datos (ordenado
conjunto se examina hasta que se hace una coincidencia. o desordenado).
Una vez que se encuentra el elemento, la búsqueda finaliza.
No podemos discutir formas eficientes de encontrar un
3.1.3. Búsqueda binaria
elemento en un conjunto sin considerar cómo se insertaron
los elementos en la lista. Por tanto, la discusión sobre los La búsqueda binaria es un algoritmo de búsqueda que se
algoritmos de búsqueda está relacionada con el tema de usa en arreglos ordenados, dividiendo de forma rápida el
la operación de inserción del conjunto. Supongamos que intervalo de búsqueda por la mitad [17].
queremos insertar elementos lo más rápido posible y no nos Si un conjunto de datos se ordena y almacena secuencial-
preocupa tanto el tiempo que lleva encontrarlos. Pondríamos mente en un arreglo, podemos usar una búsqueda binaria.
el elemento en el último espacio de un conjunto basado en El algoritmo de búsqueda binaria mejora la eficiencia de la
arreglos y en el primer espacio de un conjunto enlazado. búsqueda al limitar la búsqueda al área donde podría estar
El conjunto resultante se ordena según el momento de la el elemento. El algoritmo de búsqueda binaria recorta con-
inserción, no según el valor de la clave [14–16]. tinuamente el área de búsqueda hasta que se encuentra el
Un algoritmo escrito para una búsqueda lineal puede ser elemento o el área de búsqueda desaparece (el elemento no
el siguiente: está en la lista) [18, 19].
Página 2
Tabla 1: Una tabla de símbolos es una estructura de datos para pares clave-valor que admite dos operaciones: insertar (poner) un nuevo par
en la tabla y buscar (obtener) el valor asociado con una clave determinada.

Aplicación Propósito de la búsqueda Clave Valor

diccionario buscar definición palabra definición
índice de libros encontrar páginas relevantes término lista de números de página
compartir archivos buscar canciones para descargar nombre de la canción ID de la computadora
administración de cuentas procesar transacciones número de cuenta detalles de la transacción
búsqueda web encontrar páginas web relevantes palabra clave lista de nombres de páginas
compilador buscar tipo y valor nombre de variable tipo y valor

Un algoritmo escrito para una búsqueda lineal puede ser Cabe mencionar que no se garantiza que la búsqueda bi-
el siguiente: naria sea más rápida para buscar en listas muy pequeñas. Se
debe tener en cuenta que aunque la búsqueda binaria, por lo
1. Compara x con el elemento del medio. general, requiere menos comparaciones, cada comparación
implica más evaluaciones.
2. Devuelve el índice medio, si x coincide con el elemento
medio.
3.2. Algoritmos de ordenamiento
3. De lo contrario, si x es mayor que el elemento medio, El ordenamiento es el proceso de reorganizar una secuen-
entonces x solo puede estar a la derecha del elemento cia de objetos para ponerlos en algún orden lógico. La ubi-
medio. Entonces recurrimos a la mitad derecha. cuidad del uso de la computadora nos ha inundado de datos
y, a menudo, el primer paso para organizar los datos es orde-
4. De lo contrario (si x es menor que el elemento medio)
narlos. Todos los sistemas informáticos tienen implementa-
se repite para la mitad izquierda.
ciones de algoritmos de ordenamiento, para uso del sistema
y de los usuarios. Por ejemplo, un teléfono móvil muestra
El algoritmo anterior se muestra en lenguaje de programa-
los mensajes de texto ordenados por fecha; es probable que
ción en la figura 4.
un algoritmo de ordenamiento los haya puesto en ese orden
[20–22].
int buscar(int arr[], int l, int n, int x){ Los algoritmos de ordenamiento juegan un papel impor-
if (n >= l) { tante en el procesamiento de datos comerciales y en el
int mid = l + (n - l) / 2; cómputo científico de alto rendimiento. De hecho, un algo-
if (arr[mid] == x) ritmo de ordenamiento (quicksort) fue catalogado como uno
return mid; de los diez mejores algoritmos para la ciencia y la tecnología
if (arr[mid] > x)
del siglo XX [23].
return buscar(arr, l, mid - 1, x);
return buscar(arr, mid + 1, n, x);
} 3.2.1. Algoritmos de burbuja
return -1; Los algoritmos de burbuja son un algoritmo de clasifica-
} ción simple y lento que recorre un conjunto de objetos en
distintas ocasiones, compara cada par de elementos adya-
int main(void){ centes y los intercambia si están en el orden incorrecto [24].
int arr[] = {2,4,6,8,10}; La idea básica de un algoritmo de burbuja se describe a
int x = 2; continuación: [25–27]
int n = sizeof(arr) / sizeof(arr[0]);
int r = buscar(arr, 0, n - 1, x); 1. Los elementos de datos se agrupan en dos secciones:
(r == -1) una sección ordenada y una sección no ordenada.
? cout << x << " no se encuentra en
el arreglo." 2. Se revisa cada elemento en la sección no ordenada y
: cout << x << " se encuentra en el se reorganiza su posición con su vecino para colocar el
lugar " << r << " del arreglo."; elemento con mayor orden en la posición más alta.
return 0;
} 3. El elemento con el orden más alto estará en la parte
(a) Algoritmo de búsqueda binaria en lenguaje de programación (C++) superior de la sección no ordenada y se moverá al final
de la sección ordenada.
2 se encuentra en el lugar 0 del arreglo.
(b) Mensaje de salida
4. Se repite el paso 2 hasta que no queden más elementos
en la sección sin clasificar.
Figura 4: La búsqueda binaria funciona de manera eficiente en listas
ordenadas. Por lo tanto, para buscar un elemento en algún conjunto Un algoritmo escrito para un ordenamiento de burbuja
con esta técnica, se debe asegurar que la lista esté ordenada. puede ser el siguiente:
Página 3
 Paso 1: El algoritmo compara los dos primeros elementos Como se observa, en un algoritmo de burbuja el movi-
de un conjunto de números e inicia el ordenamiento. miento de los elementos con órdenes más altos, son como
burbujas en el agua, flotando de m¿forma lenta de abajo
(51428) → (15428) × Intercambia desde 5 > 1 hacia arriba.
(15428) → (14528) × Intercambia desde 5 > 4
(14528) → (14258) × Intercambia desde 5 > 2 3.2.2. Algoritmos por inserción
(14258) → (14285)  El algoritmo que se usa a menudo para clasificar las manos
del bridge es considerar las cartas una por una, insertando
Paso 2: Dado que estos elementos (5 y 1) ya están en orden cada una en un lugar adecuado entre las ya consideradas
(8 > 5), el algoritmo no los intercambia y vuelve a iniciar con (manteniéndolas ordenadas). En una implementación por
los dos primeros elementos siguientes. computadora, necesitamos hacer espacio para insertar el
elemento actual moviendo los elementos más grandes una
(14258) → (14258)  posición hacia la derecha, antes de insertar el elemento ac-
(14258) → (12458) × Intercambia desde 4 > 2 tual en la posición vacante. Este proceso se conoce como
algoritmo por inserción [28].
(12458) → (12458) 
En este tipo de algoritmos, los elementos a la izquierda
(12458) → (12458)  de un conjunto de elementos están ordenados, pero no se
encuentran en su posición final, ya que es posible que deban
Paso 3: El conjunto de números ya está ordenado; sin em- moverse para dejar espacio a los elementos más pequeños
bargo, el algoritmo, lleva a cabo un pase completo sin inter- que se encuentren más adelante. Sin embargo, el conjun-
cambios para verificar que el conjunto está ordenado. to está ordenado por completo cuando el índice alcanza el
extremo derecho.
(12458) → (12458) 
La idea básica de un algoritmo de ordenamiento por inser-
(12458) → (12458)  ción se describe a continuación: [29, 30]
(12458) → (12458)  1. Los elementos de datos se agrupan en dos secciones:
(12458) → (12458)  una sección ordenada y una sección no ordenada.
2. Se toma un elemento de la sección sin clasificar.
El algoritmo anterior se muestra en lenguaje de programa-
ción en la figura 5. 3. Se inserta el elemento en la sección ordenada en la po-
sición correcta según la propiedad comparable.
void burbuja(int arr[], int n){ 4. Los pasos 2 y 3 se repiten hasta que no queden más
int i, j; elementos en la sección sin clasificar.
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - i - 1; j++) Un algoritmo escrito para un ordenamiento por inserción
if (arr[j] > arr[j + 1]) puede ser el siguiente:
swap(arr[j], arr[j + 1]);
Paso 1: Compara el segundo elemento de un conjunto
}
con su predecesor. Si es más pequeño que su predecesor,
void imprimir(int arr[], int size){ desplázalo hacia su izquierda.
int i; Paso 2: Compara el elemento siguiente con sus predece-
for (i = 0; i < size; i++) sores. Si es más pequeño que su predecesores, desplázalo
cout << arr[i] << " ";
hacia la izquierda de su sucesor.
cout << endl;
} 4 3 2 10 12 1 5 6 ×
El 3 se desplaza a la izquierda del 4
int main(){
3 4 2 10 12 1 5 6 ×
int arr[] = {5,1,4,2,8};
El 2 se desplaza a la izquierda del 3
int n = sizeof(arr) / sizeof(arr[0]);
burbuja(arr, n); 2 3 4 10 12 1 5 6 
cout << "Ordenamiento de burbuja: "; 2 3 4 10 12 1 5 6 
imprimir(arr, n);
2 3 4 10 12 1 5 6 ×
return 0;
El 1 se desplaza a la izquierda del 2
}
1 2 3 4 10 12 5 6 ×
(a) Algoritmo de burbuja en lenguaje de programación (C++)
El 5 se desplaza a la izquierda del 10
Ordenamiento de burbuja: 1 2 4 5 8 1 2 3 4 5 10 12 6 ×
(b) Mensaje de salida El 6 se desplaza a la izquierda del 10
Figura 5: El ordenamiento de burbuja pone un conjunto de elemen- 1 2 3 4 5 6 10 12 
tos en orden creciente comparando de manera sucesiva elementos El algoritmo anterior se muestra en lenguaje de programa-
adyacentes e intercambiándolos si están en orden incorrecto. ción en la figura 6.
Página 4
void insercion(int arr[], int n){ 7
int i, elemento, j;
for (i = 1; i < n; i++){
elemento = arr[i];
j = i - 1; 3 12

while (j >= 0 && arr[j] > elemento){

arr[j + 1] = arr[j];
j = j - 1; 99 8 5 6
}
arr[j + 1] = elemento; (a) Opción inadecuada
}
} 7

void imprimir(int arr[], int n){

int i;
for (i = 0; i < n; i++) 3 12
cout << arr[i] << " ";
cout << endl;
}
99 8 5 6
int main(){
int arr[] = {4,3,2,10,12,1,5,6}; (b) Opción adecuada
int n = sizeof(arr) / sizeof(arr[0]);
Figura 7: Con el objetivo de alcanzar la suma más grande, en cada
insercion(arr, n); paso, el algoritmo elige lo que parece ser la opción inmediata óp-
cout << "Ordenamiento por inserción: "; tima, por lo que elegirá 12 en lugar de 3 en el segundo paso y no
imprimir(arr, n); llegará a la mejor solución, que contiene 99.

return 0;
} Por otro lado, si las propiedades a continuación son ver-
daderas, se puede usar un algoritmo voraz para resolver el
(a) Algoritmo de burbuja en lenguaje de programación (C++)
problema [33].
Ordenamiento por inserción: 1 2 3 4 5 6 10 12
1. Elección voraz. Se puede alcanzar una solución óptima
(b) Mensaje de salida
global eligiendo la opción óptima en cada paso.
Figura 6: El ordenamiento por inserción es un algoritmo de clasi-
ficación simple, aunque no es el más eficiente. Para ordenar una 2. Subestructura óptima. Un problema tiene una subes-
lista con n elementos, el ordenamiento por inserción inicia con el tructura óptima si una solución óptima para todo el
segundo elemento. problema contiene las soluciones óptimas para los sub-
problemas.
La idea de los algoritmos por inserción proviene de nues- En otras palabras, los algoritmos voraces trabajan en pro-
tras experiencias de la vida diaria. Por ejemplo, cuando juga- blemas para los que es cierto que, en cada paso, hay una
mos cartas, insertaremos la carta siguiente que elijamos en elección que es óptima para el problema hasta ese paso, y
las cartas que ya están ordenadas en nuestra mano. después del último paso, el algoritmo produce la solución
óptima del problema completo.
3.3. Algoritmos voraces
3.3.1. Algoritmo de Huffman
Un algoritmo voraz es un proceso simple e intuitivo. Se
utiliza en problemas de optimización. El algoritmo hace la El algoritmo de Huffman es un ejemplo donde el enfoque
elección óptima en cada paso mientras intenta encontrar la voraz tiene éxito. Este algoritmo analiza un mensaje y, depen-
forma óptima general de resolver todo el problema. Los algo- diendo de las frecuencias de los caracteres utilizados en el
ritmos voraces tienen bastante éxito en algunos problemas, mensaje, asigna una codificación de longitud variable para
como la codificación de Huffman, que se usa para compri- cada objeto. Un objeto de uso más común tendrá una codi-
mir datos, o el algoritmo de Dijkstra, que se usa para hallar ficación más corta, mientras que un objeto raro tendrá una
el camino más corto a través de un gráfico [31, 32]. codificación más larga [34].
En muchos problemas, una estrategia voraz no produce El algoritmo de codificación de Huffman toma informa-
una solución óptima. Por ejemplo, en la figura 7, el algoritmo ción sobre las frecuencias o probabilidades de que ocurra
busca el camino con la suma más grande, seleccionando el un objeto en particular. Comienza a construir el árbol de
mayor número disponible en cada paso. Sin embargo, no prefijos de abajo hacia arriba, comenzando con los dos obje-
logra encontrar la suma más grande porque toma decisiones tos menos probables de la lista. Toma esos objetos y forma
basadas solo en la información que tiene en cualquier paso, un subárbol que los contiene, y luego elimina los objetos
sin tener en cuenta el problema general. individuales de la lista. El algoritmo suma las probabilidades
Página 5
de los elementos en un subárbol y agrega el subárbol y su Carácter f NI
probabilidad a la lista. A continuación, el algoritmo busca en Frecuencia 45 55
la lista y selecciona los dos objetos o subárboles con las pro-
babilidades más bajas. Los usa para crear un nuevo subárbol, Extrae dos nodos de frecuencia mínima y agrega un nuevo
elimina los subárboles/objetos originales de la lista y lue- nodo interno con frecuencia 45 + 55 = 100 (figura 8e).
go agrega el nuevo subárbol y su probabilidad combinada
a la lista. Esto se repite hasta que haya un árbol y se hayan Carácter NI
agregado todos los elementos. En cada subárbol, se crea la Frecuencia 100
codificación óptima para cada objeto y juntos componen la
codificación óptima general [35, 36]. Dado que la pila contiene solo un nodo, el algoritmo se
Un algoritmo voraz para un construir un «árbol de Huff- detiene aquí (figura 8).
man» puede ser el siguiente:
14
1. Crea un nodo de hoja para cada carácter único y una
pila mínima de todos los nodos de hoja 1 .
a|5 b|9
2. Extrae dos nodos con la frecuencia mínima de la pila
mínima. (a) La pila mínima contiene cinco nodos, donde cuatro nodos son raíces de
árboles con un solo elemento cada uno, y un nodo de pila es la raíz del árbol
con tres elementos.
3. Crea un nuevo nodo interno con una frecuencia igual a
la suma de las frecuencias de los dos nodos. Haz que el 25
primer nodo extraído sea su hijo izquierdo y que el otro
nodo extraído sea su hijo derecho. Agrega este nodo a la
c | 12 d | 13
pila mínima.
(b) La pila mínima contiene cuatro nodos, donde dos nodos son raíces de
4. Repite los pasos 2 y 3 hasta que la pila contenga solo árboles con un solo elemento cada uno, y dos nodos de pila son raíces de
un nodo. El nodo restante es el nodo raíz y el árbol está árboles con más de un nodo.
completo. 30

Estudiemos el algoritmo con un ejemplo. Crea una pila mí-

nima que contenga seis nodos, donde cada nodo represente 14 e | 16
la raíz de un árbol con un solo nodo.
a|5 b|9
Carácter a b c d e f
Frecuencia 5 9 12 13 16 45 (c) La pila mínima contiene tres nodos.

55
Extrae dos nodos de frecuencia mínima de la pila mínima
y agrega un nuevo nodo interno (NI) con frecuencia 5+9 = 14
(figura 8a). 30

Carácter c d NI e f
25 14 e | 16
Frecuencia 12 13 14 16 45

Extrae dos nodos de frecuencia mínima y agrega un nuevo c | 12 d | 13 a|5 b|9

nodo interno con frecuencia 12 + 13 = 25 (figura 8b).

(d) La pila mínima contiene dos nodos.

Carácter NI e NI f 100

Frecuencia 14 16 25 45
f | 45 55
Extrae dos nodos de frecuencia mínima y agrega un nuevo
nodo interno con frecuencia 14 + 16 = 30 (figura 8c).
30

Carácter NI NI f
Frecuencia 25 30 45 25 14 e | 16

Extrae dos nodos de frecuencia mínima y agrega un nuevo

c | 12 d | 13 a|5 b|9
nodo interno con frecuencia 25 + 30 = 55 (figura 8d).
(e) La pila mínima contiene un solo nodo.

1 La pila mínima se usa como una cola de prioridad. El valor del campo de
Figura 8: Dada una tabla de probabilidades, se puede construir un
«árbol de Huffman» para codificar cada objeto. Los pasos 2 y 3 del
frecuencia se usa para comparar dos nodos en la pila mínima. Inicialmente,
el carácter menos frecuente está en raíz. algoritmo se repiten hasta que todos los objetos estén combinados.

Página 6
 El algoritmo de Huffman crea un árbol binario a partir Casa → B → D → F → Escuela.
de los dos objetos con las probabilidades más bajas que se
seleccionaron al inicio. Para ello, se etiqueta una rama con Un algoritmo voraz para hallar el camino más corto entre
un «1» y la otra con un «0» (figura 9). No importa de qué lado dos puntos puede ser el siguiente: [39, 40]
se marque, siempre que el etiquetado sea consistente a lo
largo del problema; es decir, el lado izquierdo siempre debe 1. Crea un conjunto de árboles que realice un seguimiento
ser 1 y el lado derecho siempre debe ser 0, o viceversa. de los vértices incluidos en el árbol de ruta más corta, es
decir, cuya distancia mínima desde la fuente se calcula
y finaliza.
100
0 1 2. Asigna un valor de distancia a todos los vértices en el
gráfico de entrada. Inicializa todos los valores de distan-
f | 45 55
1
cia como infinitos. Asigna el valor de distancia como 0
0 para el vértice de origen para que se elija primero.
30
0 1 3. Mientras que el conjunto de árboles no incluya todos
los vértices:
25 14 e | 16
0 1 0 1 Elige un vértice (u) que no esté en el conjunto y
tenga un valor de distancia mínimo.
c | 12 d | 13 a|5 b|9
Incluye a u en el conjunto.
Figura 9: En un árbol binario de Huffman los nodos tienen como
Actualiza el valor de la distancia de todos los vérti-
máximo dos hijos. Se puede distinguir entre ellos usando la direc-
ces adyacentes de u, iterando a través de todos los
ción izquierda o derecha.
vértices adyacentes. Para cada vértice adyacente
v, si la suma del valor de la distancia de u (desde
Por tanto, las codificaciones que se obtienen a partir del
la fuente) y el peso del borde u − v es menor que
árbol son:
el valor de la distancia de v, actualiza el valor de la
Carácter f c d a b e distancia de v.
Palabra de código 0 100 101 1100 1101 111
Estudiemos el algoritmo con un ejemplo. Construyamos
un gráfico ponderado (figura 11), elijamos un vértice inicial
y asignemos valores de ruta infinitos al resto de los nodos.
3.3.2. Algoritmo de Dijkstra La distancia desde el nodo de origen a sí mismo siempre
Un algoritmo para hallar la ruta más corta desde un nodo es 0 (figura 11a).
inicial hasta un nodo objetivo en un gráfico ponderado es
La distancia desde el nodo de origen al resto de los no-
el algoritmo de Dijkstra. El algoritmo crea un árbol de rutas
dos aún no se ha determinado. Esto se representa con
más cortas desde el vértice inicial, la fuente, hasta hasta el
el símbolo de infinito (∞).
resto de los puntos del gráfico [37, 38].
Supongamos que un estudiante quiere ir de su casa a la
escuela de la manera más corta posible. Sabe que algunas Nodo 0 1 2 3 4 5 6
carreteras están muy congestionadas y son difíciles de usar. Distancia 0 ∞ ∞ ∞ ∞ ∞ ∞
En el algoritmo de Dijkstra, esto significa que el borde tiene
un gran peso: el árbol de ruta más corto que encuentre el al- Necesitamos seleccionar el nodo más cercano al nodo
goritmo intentará evitar los bordes con pesos más grandes. Si de origen en función de las distancias conocidas, marcarlo
el estudiante busca direcciones usando un servicio de mapas, como visitado () e incluirlo a la ruta.
es probable que use el algoritmo de Dijkstra (figura 10). Si revisamos la lista de distancias, podemos ver que el
nodo 1 tiene la distancia más corta al nodo de origen (una
5
Casa C distancia de 2), por lo que lo agregamos a la ruta (figura 11b).
2 2 Además, lo marcamos en la lista para indicar que ha sido
6
3 B E visitado y que hallamos el camino más corto a este nodo.
1 1

A D F 4 Nodo 0 1 2 3 4 5 6
3 4
Distancia 0 2 ∞ ∞ ∞ ∞ ∞
2
Escuela


Figura 10: Gráfico ponderado que representa todos los caminos El nodo 2 y el nodo 3 son adyacentes a los nodos que ya
que existen entre la casa y la escuela. están en la ruta, porque están conectados de forma directa
al nodo 0 y al nodo 1, respectivamente. Estos son los nodos
El camino más corto de la figura 10, que se puede encon- que analizaremos.
trar usando el algoritmo de Dijkstra, es:
Página 7
 1 5 Lo primero que haremos será elegir qué nodo se agregará
a la ruta. Debemos seleccionar el nodo no visitado con la dis-
2 5 15 6
tancia más corta (actualmente conocida) al nodo de origen.
0 3 6 6
De la lista de distancias, podemos detectar de inmediato que
6 8 10 2 este es el nodo 2 con la distancia 6 (figura 11c). Por tanto,
2 4 marcamos el nodo 2 como visitado.

(a) El nodo de origen será el nodo 0, pero puede ser cualquier nodo. Nodo 0 1 2 3 4 5 6
Distancia 0 2 6 ∞ ∞ ∞ ∞
1 5
 
2 5 15 6

0 3 6 6
Para encontrar la distancia desde el nodo de origen a otro
6 8 10 2 nodo (en este caso, el nodo 3), sumamos las longitudes de
2 4 todas las aristas que forman el camino más corto para llegar
a ese nodo.
(b) El nodo 1 tiene la distancia más corta al nodo de origen.

1 5 Para el nodo 3:
2 5 15 6 La distancia total es 7 porque sumamos las longitudes
0 3 6 6 de las aristas que forman el camino 0 → 1 → 3 (2 para la
6 8 10 2 arista 0 → 1 y 5 para la arista 1 → 3).
2 4 Además de la ruta 0 → 1 → 3, el camino 0 → 2 → 3 es
otra opción que puede ser viable.
(c) El nodo 2 tiene la segunda distancia más corta al nodo de origen.

1 5
Veamos cómo decidir cuál de ellas es la ruta más corta. Si
elegimos seguir el camino 0 → 2 → 3, necesitaríamos seguir
2 5 15 6
dos aristas: 0 → 2 y 2 → 3 con longitudes 6 y 8, respectiva-
0 3 6 6 mente, lo que representa una distancia total de 14.
6 8 10 2 Es claro que la primera distancia es más corta (7 frente
2 4 a 14), por lo que elegiremos mantener la ruta 0 → 1 → 3
(figura 11d). Por tanto, marcamos el nodo 3 como visitado.
(d) La ruta 0 → 1 → 3 es la más corta entre los nodos 0 y 3.
Nodo 0 1 2 3 4 5 6
1 5
Distancia 0 2 6 7 ∞ ∞ ∞
2 5 15 6
  
0 3 6 6

6 8 10 2 Ahora, necesitamos verificar los nuevos nodos adyacentes.

2 4 Esta vez, son el nodo 4 y el nodo 5 ya que son adyacentes al
nodo 3. Actualizamos las distancias de estos nodos al nodo de
(e) La ruta 0 → 1 → 3 → 4 es la más corta entre los nodos 0 y 4. origen, siempre intentando encontrar el camino más corto:
1 5
Para el nodo 4:
2 5 15 6

0 3 6 6 La distancia es 2 + 5 + 10 = 17 desde 0 → 1 → 3 → 4.
6 8 10 2
Para el nodo 5:
2 4
La distancia es 2 + 5 + 15 = 22 desde 0 → 1 → 3 → 5.
(f ) La ruta 0 → 1 → 3 → 4 → 6 es la más corta entre los nodos 0 y 6.
Necesitamos elegir qué nodo no visitado se marcará como
1 5
visitado. En este caso, es el nodo 4 porque tiene la distancia
2 5 15 6
más corta en la lista de distancias (figura 11e).
0 3 6 6

6 8 10 2
Nodo 0 1 2 3 4 5 6
Distancia 0 2 6 7 17 22 ∞
2 4
   
(g) La ruta 0 → 1 → 3 → 5 es la más corta entre los nodos 0 y 5.
A continuación, comprobamos los nodos adyacentes: no-
Figura 11: El algoritmo de Dijkstra encuentra el camino más corto
do 5 y nodo 6.
entre un nodo dado, que se denomina «nodo de origen», y el resto
de los nodos en un gráfico.

Página 8
 Para el nodo 5: 3.4.1. Complejidad de algoritmos
La primera opción es seguir la ruta 0 → 1 → 3 → 5, que La complejidad algorítmica es una medida de cuánto tiem-
tiene una distancia de 22 desde el nodo fuente. Esta po tardaría en completarse un algoritmo dada una entrada
distancia ya estaba registrada en la lista de distancias de tamaño n. Si un algoritmo tiene que escalar, debe calcular
en un paso anterior. el resultado dentro de un límite de tiempo finito y práctico
incluso para valores grandes de n. Por esta razón, la compleji-
La segunda opción es seguir la ruta 0 → 1 → 3 → 4 → 5,
dad se calcula de forma asintótica cuando n tiende a infinito
que tiene una distancia de 2 + 5 + 10 + 6 = 23 desde el
[43].
nodo fuente.
Si bien, la complejidad se expresa en términos de tiempo,
Para el nodo 6: a veces la complejidad también se analiza en términos de
espacio, lo que se traduce en los requisitos de memoria del
La ruta disponible es 0 → 1 → 3 → 4 → 6, que tiene una algoritmo [44].
distancia de 2 + 5 + 10 + 2 = 19 desde el nodo fuente.

Marcamos el nodo con la distancia más corta (actualmente 3.4.2. Complejidad del tiempo
conocida) como visitado (figura 11f). En este caso, el nodo 6.
La complejidad del tiempo es la cantidad de tiempo que
Nodo 0 1 2 3 4 5 6 tarda un algoritmo en ejecutarse, en función de la longitud
Distancia 0 2 6 7 17 22 19 de la entrada. Mide el tiempo necesario para ejecutar cada
     declaración de código en un algoritmo. Aquí, la longitud de
entrada indica el número de operaciones a realizar por el
algoritmo [45].
Solo un nodo no ha sido visitado todavía, el nodo 5. Vea-
mos cómo podemos incluirlo en la ruta. Hay tres caminos En general, la complejidad del tiempo mide el tiempo ne-
diferentes que podemos tomar para llegar al nodo 5 de los cesario para ejecutar cada instrucción de código en un algo-
nodos que se han agregado al camino: ritmo. Si una declaración está configurada para ejecutarse
repetidamente, la cantidad de veces que se ejecuta esa de-
0 → 1 → 3 → 5 con una distancia de 2 + 5 + 15 = 22. claración es igual a n multiplicado por el tiempo requerido
para ejecutar esa función cada vez [46].
0 → 1 → 3 → 4 → 5 con una distancia de 2+5+10+6 = 23.

0 → 1 → 3 → 4 → 6 → 5 con una distancia de 2 + 5 + 10 + 3.4.3. Notación Big O

2 + 6 = 25.
Existe una notación estándar que se usa para simplificar la
Es claro que la ruta más corta al nodo 5 es 0 → 1 → 3 → 5 comparación entre dos o más algoritmos: la notación Big O.
(figura 11g). Marcamos el nodo como visitado de la lista de La idea de esta notación es similar al concepto de la derivada
nodos no visitados. en cálculo. Representa la tasa de crecimiento del tiempo de
ejecución a medida que aumenta el número de elementos.
Nodo 0 1 2 3 4 5 6 Decir que un algoritmo es O(n) significa que el tiempo de
Distancia 0 2 6 7 17 22 19 ejecución está limitado por algunos tiempos constantes n.
      Esto se puede escribir como c ∗ n. Si el tamaño del conjun-
to se duplica, entonces el tiempo de ejecución es c ∗ (2n).
Tenemos el resultado final con el camino más corto desde Pero esto es 2 ∗ (c ∗ n), por lo que espera que el tiempo de
el nodo 0 hasta cada nodo del gráfico. ejecución también se duplique. Por otro lado, si un algoritmo
de búsqueda es O(log n) y se duplica el tamaño del conjun-
to, se pasa de c ∗ (log n) a c ∗ (log 2n), que es simplemente
3.4. Tiempo de ejecución c + c ∗ log n. Esto significa que los algoritmos O(log n) son
Pareciera que medir el tiempo de ejecución de un progra- más rápidos que los algoritmos O(n), y esta diferencia solo
ma es algo fácil. Podríamos usar un cronómetro, iniciar el aumenta a medida que aumenta el valor de n [47].
programa y observar cuánto tiempo pasa hasta que finali- Una tarea que requiere la misma cantidad de tiempo, sin
za el programa. Pero este tipo de medida, conocido como importar el tamaño de la entrada, se describe como O(1) o
tiempo de reloj de pared, no es, por varias razones, la mejor «tiempo constante». Una tarea que es O(n) se denomina tarea
caracterización de un algoritmo informático [41]. de «tiempo lineal». Una que es O(l og n) se llama logarítmi-
Un punto de referencia describe solo el rendimiento de ca. Otros términos que se utilizan incluyen cuadrático para
un programa en una máquina específica en un día deter- tareas O(n 2 ) y cúbico para algoritmos O(n 3 ) [48].
[Link] embargo, distintos procesadores pueden tener La tabla 2 muestra la complejidad del tiempo, en términos
actuaciones dramáticamente diferentes. Incluso trabajando de la notación Big O, de algunos algoritmos simples.
en la misma máquina, puede haber una selección de muchos Una limitación de la notación Big O es que no considera
compiladores alternativos para el mismo lenguaje de progra- el uso de la memoria. Hay algoritmos que son teóricamente
mación. Por esta y otras razones, los informáticos prefieren rápidos, pero usan una cantidad de memoria excesiva [49].
medir el tiempo de ejecución de una manera más abstracta En situaciones como esta, puede ser preferible en la práctica
[42]. un algoritmo más lento que use menos memoria.
Página 9
Tabla 2: Complejidad del tiempo de algunos algoritmos de búsque- [11] J. V. Álvarez. Tema 06: algoritmos de búsqueda y orde-
da y ordenamiento. nación [En línea]. Disponible en: [Link].
Complejidad de tiempo [12] Universidad Europea de Madrid. Análisis semánti-
Algoritmo
Mejor Promedio Peor co: la tabla de símbolos [En línea]. Disponible en:
Lineal1 O(1) O(n) O(n) [Link].
Binaria1 O(1) O(log n) O(log n) [13] S. Gálvez. Tabla de símbolos [En línea]. Disponible en:
Burbuja2 O(n) O(n 2 ) O(n 2 ) [Link].
Inserción2 O(n) O(n 2 ) O(n 2 )
1 Algoritmo de búsqueda. 2 Algoritmo de ordenamiento. [14] P. A. Sznajdleder. Algoritmos a fondo con implementa-
ciones en C y en JAVA. 1.a edición. Alfaomega, 2012.

[15] Principios de Programación: algoritmos de búsqueda y

3.5. Conclusiones
ordenación [En línea]. Disponible en: [Link].
Los dispositivos informáticos son omnipresentes en la so-
ciedad moderna. En las últimas décadas, hemos pasado de [16] E. K. Sáenz. Guía práctica de estudio 04: algoritmos de
un mundo en el que estos dispositivos eran prácticamente búsqueda parte 1 [En línea]. Disponible en: [Link]-
desconocidos a un mundo en el que miles de millones de [Link].
personas los usamos para llevar a cabo diversas actividades. [17] R. E. Neapolitan y K. Naimipour. Foundations of Algo-
Incluso nos hemos hecho dependientes de ellos. rithms Using C++ Pseudocode. 3.a edición. Massachu-
Gran parte de los algoritmos subyacentes que permiten setts: Jones and Bartlett Publishers, 2004.
que los dispositivos informáticos funcionen de forma ópti-
ma son los mismos que se describieron en este trabajo. En [18] S. S. Skiena. The Algorithm Design Manual. 2.a edición.
aplicaciones comerciales, computación científica, ingeniería New York: Springer, 2009.
y muchas otras áreas de investigación, los algoritmos que se
[19] Algoritmos de ordenación y búsqueda [En línea]. Dispo-
estudiaron marcan la diferencia entre poder resolver proble-
nible en: [Link].
mas en el mundo moderno y no poder abordarlos.
[20] R. Johnsonbaugh. Matemáticas discretas. 4.a edición.
Referencias México: Pearson, 1997.

[1] M. Habib, C. McDiarmid, J. Ramírez-Alfonsín y B. Reed. [21] V. M. de la Cueva, L. H. González y E. G. Salinas. Estruc-
Probabilistic Methods for Algorithmic Discrete Mathe- turas de datos y algoritmos fundamentales. 1.a edición.
matics. 1.a edición. Berlín: Springer, 1998. México: Editorial Digital, 2020.

[2] J. Lodder, D. Pengelley y D. Ranjan (2013, julio). Euclid’s [22] J. Knowles. Sorting Algorithms: Correcness, Comple-
Algorithm for the Greatest Common Divisor [En línea]. xity and other Properties [En línea]. Disponible en:
Disponible en [Link]. [Link].

[3] Geeks for Geeks (2022, febrero 3). Euclidean algo- [23] B. A. Cipra, «The Best of the 20th Century: Editors Name
rithms (Basic and Extended) [En línea]. Disponible en: Top 10 Algorithms», SIAM News, vol. 33, no. 4, pp. 1-2,
[Link]. mayo 2000.

[4] J. P. Tremblay, J. M. DeDourek y V. J. Friesen. Program- [24] M. Alberto, I. Schwer, V. Cámara y Y. Fumero Matemá-
ming in ADA. 1.a edición. McGraw-Hill Education, 1990. tica Discreta: con aplicaciones a las ciencias de la pro-
gramación y de la computación. 1.a edición. Santa Fe:
[5] A. Aho, J. Ullman y J. Hopcroft. Data Structures and Ediciones UNL, 2005.
Algorithms. 1.a edición. Pearson, 1983.
[25] M. T. Goodrich, R. Tamassia y D. M. Mount. Data Struc-
[6] E. E. García y J. A. Solano. Guía práctica de estudio 04: tures and Algorithms in C++. 2.a edición. Estados Uni-
pseudocódigo [En línea]. Disponible en [Link]- dos de America: John Wiley & Sons, 2011.
[Link].
[26] Algoritmos de Ordenamiento [En línea]. Disponible en:
[7] M. A. Rodríguez. Metodología de la programación: a [Link].
través del pseudocódigo. 1.a edición. Madrid: McGraw-
Hill, 1991. [27] L. Hernández. Fundamentos de la programación: al-
goritmos de ordenación [En línea]. Disponible en:
[8] R. Sedgewick. Algorithms in C, Part 5: Graph Algorithms. [Link].
3.a edición. Harlow: Pearson, 2001.
[28] A. Garrido. Fundamentos de Programación en C++. 1.a
[9] R. Sedgewick y P. Flajolet. An Introduction to the Analysis edición. Madrid: Delta, 2006.
of Algorithms. 2.a edición. Pearson, 2013.
[29] G. Martín y F. A. Martínez. Introducción a la progra-
[10] T. Alfaro. Algoritmos de Búsqueda y Ordenamiento [En mación estructurada en C. 1.a edición. Valencia: Quiles,
línea]. Disponible en: [Link]. 2003.
Página 10
[30] Geeks for Geeks (2021, julio 8). Insertion Sort [En línea].
Disponible en: [Link].

[31] N. Ziviani. Diseño de algoritmos con implementaciones

en Pascal y C. 1. a edición. Madrid: Thomson, 2007.

[32] J. Campos. Esquemas algorítmicos: algoritmos voraces

[En línea]. Disponible en: [Link].

[33] Geeks for Geeks (2022, abril 22). Greedy Algorithms [En
línea]. Disponible en: [Link].

[34] C. A. Shaffer. Data Structures & Algorithm Analysis in

C++. 3.a edición. Mineola: Dover Publications, 2011.

[35] Geeks for Geeks (2022, abril 19). Huffman Coding [En
línea]. Disponible en: [Link].

[36] Department of Mathematics and Computer Scien-

ce. Huffman Coding [En línea]. Disponible en:
[Link].

[37] M. McMillan. Data Structures and Algorithms Using C#.

1.a edición. Cambridge, 2007.

[38] Geeks for Geeks (2022, febrero 22). Dijkstra’s

shortest path algorithm [En línea]. Disponible en:
[Link].

[39] S. Kadry, A. Abdallah y C. Joumaa. On The Optimiza-

tion of Dijkstra’s Algorithm [En línea]. Disponible en:
[Link].

[40] Favtutor. Dijkstra’s Algorithm in C++: shortest Path Al-

gorithm [En línea]. Disponible en: [Link].

[41] Geeks for Geeks (2022, febrero 14). Measure execution

time of a function in C++ [En línea]. Disponible en:
[Link].

[42] Laboratorio de Matemáticas. Tiempo de ejecución

y eficiencia de algoritmos [En línea]. Disponible en:
[Link].

[43] J. A. Mañas. Análisis de Algoritmos: complejidad [En

línea]. Disponible en: [Link].

[44] Javatpoint. Complexity of Algorithm [En línea]. Dispo-

nible en: [Link].

[45] Geeks for Geeks (2022, marzo 2). Time Comple-

xity and Space Complexity [En línea]. Disponible en:
[Link].

[46] Geeks for Geeks (2022, abril 28). Understanding Time

Complexity with Simple Examples [En línea]. Disponi-
ble en: [Link].

[47] N. M. Josuttis. The C++ Standard Library: a tutorial

and reference. 2.a edición. Estados Unidos de América:
Pearson, 2012.

[48] M. Gregoire. Professional C++. 3.a edición. Estados Uni-

dos de América: John Wiley & Sons, 2014.

[49] Geeks for Geeks (2021, marzo 6). Analysis of Al-

gorithms: big-O analysis [En línea]. Disponible en:
[Link].

Página 11