El estudio de los Algorítmos Fundamentales

Herramientas para visualizar los algorítmos

Además de las estructuras abstractas de datos, una de las áreas de estudio básicas en Informática, son los modelos de algoritmos(*) de búsqueda y ordenamiento. En la actualidad, el estudiante dispone de numerosas herramientas muy atractivas para estudiar, analizar y experimentar con estos algoritmos.

(*) Algorítmo deriba del vocablo árabe alkhowarizmi, seudónimo de un matemático y astrónomo árabe que escribió un tratado sobre manipulación de números de sistema indú y ecuaciones en el siglo IX.

Planilla de Cálculo

Para ilustrar esto, vamos a utilizar la planilla de cálculos Excel y el lenguaje Visual Basic con el algoritmo denominado Bubble Sort u Ordenamiento de Burbuja. Para estudiar los detalles de este y otros algorítmos, les recomiendo que lean algún texto como: “The Art of Computer Programming: Fundamental Algorithms” de Knuth o "C Programming Language" de Kernigan y Ritchie. O alguno similar.

Generación de un conjunto de valores aleatorios

Para la generación de valores aleatorios crearemos un procedimiento llamado "Aleatorios" que completara el rango de celdas A1:A100.

Sub Aleatorios() Dim i As Integer Randomize For i = 1 To 100 Range("A" & Trim(Str(i))).Value = Int(Rnd * 1000) + 100 Next End Sub

Para la representación gráfica, emplearemos columnas y estableceremos dos series, una con los valores aleatorios generados por nuestro procedimiento “Aleatorios” correspondiente al rango A1:A100 y una serie que simplemente reproducirá el mismo valor absoluto pero con signo negativo. Esta última serie corresponde al rango B1:B100.

El Gráfico Inicial

Fig. 1 Valores Aleatorios Desordenados.

El algoritmo más elemental e ineficiente de ordenamiento es el denominado “Bubble Sort” u ordenamiento de burbuja, y recibe este nombre porque al cambiar la posición de los valores, da la impresión de que suelta burbujas.

El método de burbuja

En el método de burbuja, se cuenta con dos bucles que permiten comparar dos valores adyacentes y en caso de que estén fuera de orden, los intercambia. Por cada comparación puede ordenar solamente dos elementos adyacentes. La eficiencia que presenta es n^2 o n en el mejor de los casos (cuando la lista está previamente ordenada).

La subrutina BubbleSort

Sub BubbleSort() Dim i As Integer Dim j As Integer Dim AUX As Integer Dim inicio Range("G1").Value = 0 For i = 2 To 100 For j = 100 To i Step -1 If Range("A" & Trim(Str(j - 1))).Value > Range("A" & Trim(Str(j))).Value Then AUX = Range("A" & Trim(Str(j - 1))).Value Range("A" & Trim(Str(j - 1))).Value = Range("A" & Trim(Str(j))).Value Range("A" & Trim(Str(j))).Value = AUX Range("G1").Value = Range("G1").Value + 1 End If DoEvents ‘Utilizar DoEvents para permitir que Excel actualice el gráfico en "tiempo real" Next Next End Sub

Gráfico Resultante

Fig. 2 El mismo conjunto de valores ordenados.

Hasta la próxima entrega,

Sergio Otaño