Algoritmo de ordenamiento QuickSort

Artículo perteneciente a la sección de algoritmos

Hola a todos,

Si habéis seguido la sección de algoritmos habréis visto ya los algoritmo más fáciles de implementar e ineficientes. Ahora le toca el turno a un algoritmo que es de lo más eficientes que existen sin tener un complejidad excesiva, el algoritmo QuickSort.

Este algoritmo se basa en la teoría de divide y vencerás. Parte el vector a ordenar en dos trozos, en la parte más baja pone los números más bajos y en la parte más alta los números más altos. Después se aplica el mismo procedimiento a cada una de las partes de forma recursiva hasta que no se puede dividir más... en ese momento el vector ya está ordenado.

El problema de este algoritmo más allá de su implementación (que ya veréis que tampoco es tan compleja) es la elección del valor (llamado pivote) que se usa para dividir cada una de las listas. Si el pivote está justo en el medio de la lista, el rendimiento es óptimo, si el pivote está a un extremo de los valores de esa subsección el rendimiento es parecido al del algoritmo de burbuja, el problema es que no es fácil encontrar ese valor. Para lo que nos interesa aquí ( que aprendáis el algoritmo) no nos hace falta decir más, si estáis interesados comentadlo y tal vez me expanda un poco más la explicación.

El código de este algoritmo es el siguiente:

int LPVector::distribuir(int b, int t)
{
    int i;
    int pivote, valor_pivote;
    int temp;

    pivote = b;
    valor_pivote = v[pivote];

    for (i=b+1; i<=t; i++)
{
        if (v[i] < valor_pivote)
{
           pivote++;
           temp=v[i];
           v[i]=v[pivote];
           v[pivote]=temp;
}
    }
    temp=v[b];
    v[b]=v[pivote];
    v[pivote]=temp;
return pivote;
}

void LPVector::RecursiveQuicksort(int b, int t)
{
int pivote;
    if(b < t)
{
pivote=distribuir(b, t);
        RecursiveQuicksort(b, pivote-1);
        RecursiveQuicksort(pivote+1, t);
    }
}

void LPVector::QuickSort(void)
{
RecursiveQuicksort(0,n-1);
}

Espero que os haya servido y hayáis aprendido un poco más sobre los algoritmos de ordenación.

En breve comenzaré con las comparativas entre algoritmos y las implementaciones en asm

Nos vemos

Algoritmo de ordenamiento por selección (Selection Sort)

Artículo perteneciente a la sección de algoritmos

Este artículo es una evolución del algoritmo de ordenación por burbuja

Hola a todos,

Hace poco os explique el algoritmo de ordenación por burbuja y el de ordenación por burbuja bidireccional. Pese a que este segundo es una evolución un poco mejor que el original, el problema de que usa demasiada memoria sigue ocurriendo.

En las arquitecturas hardware (tantos las actuales, como las antiguas, y seguramente también las futuras) lo que más limita la velocidad de ejecución de un programa es el acceso a memoria. Si nuestro algoritmo usa de forma intensiva la memoria lo más normal es que su rendimiento sea bajo.

Con esta premisa nació el algoritmo de ordenación por selección.  La idea es simple. Busco el elemento más pequeño de la lista, y lo intercambio con el elemento de la primera posición... busco el segundo elemento más pequeño y lo intercambio con el elemento de la segunda posición. Con esto se hace más o menos el mismo número de comparaciones que se hacen con el algoritmo de burbuja tradicional, pero con muchos menos movimientos  de memoria, y por lo tanto con un rendimiento claramente superior.

Un ejemplo de código de este algoritmo sería el siguiente:

void LPVector::SelectionSort(void)
{
int i,j,indmin=0;
float min = v[0];

for ( i = 0 ; i < (n-1) ; ++i)
{
indmin = i;
min = v[i];
for( j = i+1 ; j < n ; ++j)
{
if(v[j] < min )
{
indmin = j;
min = v[j];
}
}

v[indmin] = v[i];
v[i] = min;
}
}


No podemos decir que sea un algoritmo eficiente (su coste depende de forma cuadrática con la longitud del vector), pero si que podemos asegurar que solo hará tantos movimientos de memoria como elementos haya en el vector, y esto ya es una clara mejora.

En breve haré una lista comparativa con los costes de cada algoritmo en diferentes situaciones para que os hagáis una idea.

Espero que os sirva de referencia

Nos vemos

¿Que es un algoritmo?

Artículo perteneciente a la sección de Algoritmos
Artículo relacionado con Historia de la computación

Si eres nuevo en el campo de la programación estarás ya aburrido de oír siempre la palabra algoritmo y no saber que significa, tranquilo que a todos nos ha pasado.

Simplificando mucho el concepto, algoritmo es la descripción formal de como hacer una tarea concreta. Si nos ceñimos a esta descripción una receta de cocina podría ser un algoritmo (de hecho, a mi parecer lo es) y no os ha de extrañar que muchas cosas de nuestra vida cotidiana (como  por ejemplo seguir las instrucciones para montar un mueble ) se puedan entender como algoritmos  debido a que el concepto de algoritmo no proviene de la informática sino de Musa al-Juarismi, un pensador árabe del siglo IX.

En el caso concreto que nos atañe, se define algoritmo dentro de la programación como el conjunto finito de instrucciones secuenciales espaciadas en el tiempo que permiten transformar un conjunto finito de datos de entrada en un conjunto finito de resultados a la salida. No es más que la receta de cocina para resolver problemas de programación concretos.

La gracia de los algoritmos reside en que cada algoritmo, independientemente de la implementación que hagamos de el, tiene asociada una complejidad de cálculo. Esto quier decir que sin implementar ni una sola linea de código podemos saber si el cálculo se hará lento , muy lento o inviable a medida que el conjunto de datos de entrada vaya creciendo. Esto a promovido que grandes informáticos teóricos hayan dedicado sus esfuerzos a pensar nuevas maneras de realizar tareas ya conocidas de forma más eficiente (el ejemplo más claro de esto es la ingente cantidad de algoritmos de búsqueda y ordenamiento que existen).

Por desgracia, en muchas ocasiones los programadores nos centramos en mejorar la implementación de nuestro código, usando código con threads o trozos en ensamblador y no recordamos que lo principal es que el algoritmo sea eficiente para el tamaño de datos con el que vamos trabajar. Además se ha de tener en cuenta que una buena elección de algoritmo va a permitir mantener la calidad de código estable ya que no nos obligará a usar optimizaciones poco mantenibles para mantener el rendimiento.

En breve os iré colgando algoritmos típicos para que veáis con ejemplos lo que os quiero explicar.

Espero que os haya gustado,

Nos vemos