Análisis de Algoritmos de Ordenamiento

El uso de Excel y Visual Basic

En nuestro artículo El Estudio de los Algoritmos planteamos el uso de Excel para observar la forma en que trabaja uno de los algoritmos clásicos de ordenamiento, el método de burbuja o buble sort. En este artículo vamos a plantear el análisis, con Excel, de uno de los algoritmos mas veloces de ordenamiento: QuickSort. El código en Visual Basic está al final de este artículo.

Fig. 1 Gráfico de Excel con datos aleatorios.

Si no implementaron la práctica propuesta con el algoritmo Buble Sort, les recomiendo que lo hagan primero, estudien detenidamente el código y observen la forma en que se desempeña con nuestro gráfico de Excel. Esto lo digo, porque el método de burbuja, es muy fácil de comprender y es una buena introducción para luego analizar el método de Partición o QuickSort.

Fig. 2 Quick Sort Cada línea corresponde a 1 pasada.

QuickSort es un algoritmo de ordenamiento muy eficiente, desarrollado por Edsger W. Dijkstra, que plantea el viejo axioma “divide y vencerás”. Aunque puede implementarse en forma iterativa, la solución recursiva es muy elegante. Para mas detalles sobre recursividad, vea el artículo Recursion and Machine Language en este blog.

Fig. 3 Grafico Excel al finalizar Quick Sort.

Su principio de funcionamiento se basa en el hecho de que es más rápido ordenar dos vectores de n/2 elementos que uno de n elementos.

Dado un vector a1, a2, a3, ..., an:

1. Seleccionar el valor central del vector (pivot))
2. Recorrer la partición que ha quedado a la izquierda del pivote de izquierda a derecha, y la otra de derecha a izquierda
3. Comparar los elementos de la izquierda y de la derecha e intercambiarlos si el primero es mayor que el segundo.

Al finalizar este proceso todos los elementos colocados a la izquierda del pivot son menores que los colocados a la derecha.

4) Para cada uno de los sub-vectores derecho e izquierdo repetir el proceso

En el caso del Quick Sort (ver Fig. 2), cada línea corresponde a 1 pasada, y se sabe que la eficiencia de este algoritmo es del orden de N * Log(N) (en este caso específico, tenemos 9 líneas, en realidad quité un par de líneas donde no había cambios, y está dentro del orden correspondiente): 10 * Log (10) = 10

Fig. 4 Buble Sort, cada línea corresponde a 10 pasadas.

En cambio, en el método Buble Sort

Dado un vector a1, a2, a3, ..., an:
1) Comparar a1 con a2 e intercambiarlos si a1>a2(o a1<a2)
2) Idem a2 con a3
3) Seguir hasta que todo se haya comparado an-1 con an
4) Repetir el proceso anterior n-1 veces

Con respecto a la eficiencia de Buble Sort (ver Fig. 4), cada línea corresponde a 10 pasadas de 10 elementos o sea que corresponde al orden de N^2 (en este caso puntual, fueron 9 x 10 pasadas, es decir, 90).

El Código en Visual Basic

Private Sub QS(Izquierda As Integer, Derecha As Integer) Dim pivot As Integer Dim tmpSwap As Integer Dim tmpIzquierda As Integer Dim tmpDerecha As Integer tmpIzquierda = Izquierda tmpDerecha = Derecha pivot = Range("A" & Trim(Str((Izquierda + Derecha) \ 2))).Value While (tmpIzquierda <= tmpDerecha) While (Range("A" & Trim(Str(tmpIzquierda))).Value < pivot And tmpIzquierda < Derecha) tmpIzquierda = tmpIzquierda + 1 Wend While (pivot < Range("A" & Trim(Str(tmpDerecha))).Value And tmpDerecha > Izquierda) tmpDerecha = tmpDerecha - 1 Wend If (tmpIzquierda <= tmpDerecha) Then tmpSwap = Range("A" & Trim(Str(tmpIzquierda))).Value Range("A" & Trim(Str(tmpIzquierda))).Value = Range("A" & Trim(Str(tmpDerecha))).Value Range("A" & Trim(Str(tmpDerecha))).Value = tmpSwap tmpIzquierda = tmpIzquierda + 1 tmpDerecha = tmpDerecha - 1 End If DoEvents Wend If (Izquierda < tmpDerecha) Then QS Izquierda, tmpDerecha If (tmpIzquierda < Derecha) Then QS tmpIzquierda, Derecha End Sub


Hasta la próxima,

Sergio Otaño