Imaginemos un mundo libre – El blog de Ronny

La paz interior comienza en el momento en el que decides no permitir, que otra persona o evento, tome el control de tus emociones.

Quicksort en C++

with 25 comments

Quicksort es un algoritmo de ordenación  considerado entre los más rápidos y eficientes. Fue diseñado en los años 60s por  C. A. R. Hoare un científico en computación. 
 
El algoritmo usa la técnica divide y vencerás que básicamente se basa en dividir un problema en subproblemas y luego juntar las respuestas de estos subproblemas para obtener la solución al problema central.
 
Me pareció una buena manera de practicar programación y C++ y hacer una explicación que permite entender este algoritmo , bueno al menos eso intenté.   Hace año y medio también publiqué unos ejemplos de ordenación en Haskell.
 
Voy a explicar el funcionamiento del quicksort brevemente y después veremos su implementación en C++.

Se tiene una array de n elementos, tomamos un valor del array como pibote(usualmente el primero), separamos los elementos menor a este pibote a la izquierda y los mayores a la derecha, es decir, dividimos el array en 2 subarrays.

Con estos subarrays se repite el mismo proceso de forma recursiva hasta que estos tengan más de 1 elemento. Por lo tanto la función quicksort quedaría de la siguiente manera:

// Función recursiva para hacer el ordenamiento
void quicksort(int *array, int start, int end)
{
    int pivot;

    if (start < end) {
        pivot = divide(array, start, end);

        // Ordeno la lista de los menores
        quicksort(array, start, pivot - 1);

        // Ordeno la lista de los mayores
        quicksort(array, pivot + 1, end);
    }
}

La magia está en la función dividir que es la que voy a explicar a continuación:

Empezamos creando o generando un array de n elementos, por ejemplo yo use la función rand() de C++ para generar aleatorios del 1 al 15, mi arreglo quedó así:

array[] = {8, 1, 5, 14, 4, 15, 12, 6, 2, 11, 10, 7, 9};

left                                                                              right

0 1 2 3 4 5 6 7 8 9 10 11 12
8 1 5 14 4 15 12 6 2 11 10 7 9

Tomamos como pibote el 8 y usamos 2 índices que me indiquen la posición del array:

Uno que vaya de izquierda a derecha buscando los elementos mayores al pibote. array[left]

Y un índice que busque de derecha a izquierda los elementos menores al pibote.  array[right]

El índice izquierdo irá aumentando en 1 mientras el array en la posición izquierda sea menor o igual al pibote:

        while ((left < right) && (array[left] <= pivot)) {
            left++;
        }

El índice derecho irá reduciéndose en 1 mientras el array en la posición derecha sea mayor al pibote.

        while (array[right] > pivot) {
            right--;
        }

Si al final de estas 2 operaciones, el índice izquierdo es menor al derecho se intercambian las posiciones array[left] con array[right] usando una variable temporal:

En este caso, en la primer recorrido el índice izquierdo encuentra al 14 (mayor al pibote) y el índice derecho al 7 (menor al pibote), y se intercambian los índices:

8 1 5 14 4 15 12 6 2 11 10 7 9
8 1 5 7 4 15 12 6 2 11 10 14 9

Segundo recorrido: El índice izquierdo encuentra al 15 (mayor al
pibote) y el índice derecho al 2 (menor al pibote), se intercambian:

8 1 5 7 4 15 12 6 2 11 10 14 9
8 1 5 7 4 2 12 6 15 11 10 14 9

Tercer recorrido: El índice izquierdo encuentra al 12 (mayor al pibote) y el índice derecho al 6 (menor al pibote), se intercambian:

8 1 5 7 4 2 12 6 15 11 10 14 9
8 1 5 7 4 2 6 12 15 11 10 14 9

Cuando los índices se juntan o se cruzan ponemos el pibote en el lugar que le corresponde en el array:

    temp = array[right];
    array[right] = array[start];
    array[start] = temp;

Se intercambian el 8 con el 6 y el array quedaría así:

6 1 5 7 4 2 8 12 15 11 10 14 9

Ahora la función quicksort se llamaría 2 veces recursivamente para los 2 subarray que tenemos:

quicksort(array, 0, 5) // el pibote está en la posición 6
quicksort(array, 7, 12) // el pibote está en la posición 6

Se repite el mismo proceso con este primer subarray quicksort(array,  0,  5)

El pibote es 6, se encuentra por la izquierda al 7 y por la derecha al 2. Se intercambian y como se cruzaron los índices movemos el pibote a su lugar:

6 1 5 7 4 2
6 1 5 2 4 7
4 1 5 2 6 7

Otra vez tenemos 2 subarrays. Entonces se vuelve a llamar la función

quicksort(array, 0, 3) // la posición del pibote es 4
quicksort(array, 5, 5) // no se ejecuta nada, el inicio no es menor al final

El mismo proceso. Se ejecutar quicksort (array,  0,  3). El pibote ahora es 4, se encuentra por el índice izquierdo al 5 y por el derecho a 2.  Se intercambian y como se juntaron los índices se mueve el pivote a su lugar.

4 1 5 2
4 1 2 5
2 1 4 5
quicksort(array, 0, 1) // la posición del pibote es 2
quicksort(array, 3, 3) // no se ejecuta nada, el inicio no es menor al final

Cuando se ejecuta quicksort (array,  0,  1) se intercambia los índices otra vez.

2 1
1 2

Ahora se llamaría a quicksort(array,  0,  0), se divide en 2 elementos el subarray y no hay nada más que hacer por que solo tienen 1 elemento.

Ahora se ejecuta el mismo proceso con el segundo subarray del array original. Quicksort (a,  7, 12)

Se encuentra el 15 y el 9, se intercambian y como luego se juntan los índices, se coloca el pibote a su lugar:

12 15 11 10 14 9
12 9 11 10 14 15
10 9 11 12 14 15

Tenemos otros 2 subarrays y se vuelve a llamar la función quicksort

quicksort(array, 7, 10) // posición del pibote es 10 y la primera 7
quicksort(array, 11, 12) // posición del pibote es 10 y la última 12

Se intercambian los índices y nos quedan otros 2 subarrays de 1 solo elemento entonces no se ejecuta nada.

10 9 11
9 10 11

Con el anterior subarray (14, 15) se llama a quicksort(array,  11, 12).

14 15

Se divide en 2 elementos este subarray y no hay nada más que hacer por que los array que contienen al 14 y al 15 solo tienen 1 elemento.

De manera que el árbol recursivo de ordenación queda más o menos así:

Quick Sort

Quick Sort

Complejidad computacional del Quicksort:

En el mejor de los casos tiene un costo de O(n*log (n)). Que es cuando el pibote siempre queda al medio del arreglo.

quicksort

Quicksort Mejor caso

En el peor de los casos tiene un costo de O(n^2). Cuando el pibote siempre se inclina hacia a un lado, es decir, genera una array de sólo 1 elemento y una segunda con el resto de elementos.

quicksort

Quicksort peor caso

En el caso promedio también tiene un costo de O(n*log (n)). Se produce cuando el pibote se inclina más hacia un lado y los 2 subarrays tienen distinto tamaño de elementos.

quicksort

Quicksort caso promedio

Para calcular el tiempo de ejecución estoy usando la función clock() que determina el tiempo usado por el procesador.  En este caso defino 3 variables ini, final y total.

    // Antes del quicksort:
    clock_t start_time;
    clock_t final_time;
    double total_time;
    start_time = clock();

    // Después que se ejecuta el quicksort
    final_time = clock();
    total_time = ((double)(final_time - start_time)) / CLOCKS_PER_SEC;

He leído en varios sitios de c++ que la función clock no tiene mucha precisión. Si alguien sabe un mejor método para calcular el tiempo de ejecución, algún comentario, sugerencia o aporte para optimizar al algoritmo, bienvenido.

Queda pendiente para otro post calcular con exactitud tiempos de ejecución e implementar el código del número de comparaciones e intercambios.

Bueno, aquí está la implementación del algoritmo en C++ disfrútenlo.

quicksort.cpp

// Función para dividir el array y hacer los intercambios
int divide(int *array, int start, int end) {
    int left;
    int right;
    int pivot;
    int temp;

    pivot = array[start];
    left = start;
    right = end;

    // Mientras no se cruzen los índices
    while (left < right) {
        while (array[right] > pivot) {
            right--;
        }

        while ((left < right) && (array[left] <= pivot)) {
            left++;
        }

        // Si todavía no se cruzan los indices seguimos intercambiando
        if (left < right) {
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }

    // Los índices ya se han cruzado, ponemos el pivot en el lugar que le corresponde
    temp = array[right];
    array[right] = array[start];
    array[start] = temp;

    // La nueva posición del pivot
    return right;
}

// Función recursiva para hacer el ordenamiento
void quicksort(int *array, int start, int end)
{
    int pivot;

    if (start < end) {
        pivot = divide(array, start, end);

        // Ordeno la lista de los menores
        quicksort(array, start, pivot - 1);

        // Ordeno la lista de los mayores
        quicksort(array, pivot + 1, end);
    }
}

main.cpp

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include "quicksort.cpp"

using namespace std;

int main()
{
    int const MAX = 100;
    int arraySize;

    clock_t start_time;
    clock_t final_time;
    double total_time;
    start_time = clock();

    cout << "Ingresa tamanyo: " << endl;
    cin >> arraySize;

    int a[arraySize];

    // Para que el rand no genere siempre los mismos números, utilizando la hora del sistema
    srand(time(0));

    // Para generar enteros aleatorios usamos rand()
    for (int i = 0; i < arraySize; i++) {
        a[i] = rand() % MAX;
    }

    cout << "Array antes de ordenarse: " << endl;
    for (int i = 0; i < arraySize; i++) {
        cout << a[i] << " ";
    }

    cout << endl << endl;

    quicksort(a, 0, arraySize - 1);

    final_time = clock();
    total_time = ((double)(final_time - start_time)) / CLOCKS_PER_SEC;

    printf("Tiempo de ejecución : %lf segundos \n", total_time);

    cout << "Array ordenado " << endl;
    for (int i = 0; i < arraySize; i++ ){
        cout << a[i] << "-";
    }

    cout << endl << endl;

    return 0;
}

El código fuente de este y otros ejercicios de C++ está disponible en Github:

https://github.com/ronnyml/C—Tutorial

Gracias por tu visita al blog.  Puedes seguirme en Twitter haciendo click en el siguiente enlace:

About these ads

Written by Ronny Yabar Aizcorbe

julio 19, 2009 at 7:02 pm

25 comentarios

Subscribe to comments with RSS.

  1. Excelente. Muito didático. Indiquei a meus alunos de Sistemas de Informação.
    Aluisio

    Aluisio

    junio 7, 2009 at 11:50 am

  2. Mejor que esta explicacion no existe, gracias

    alex

    julio 29, 2009 at 1:15 am

  3. Muy buen aporte compañero, tenia algunas dudas, pero ahora la tengo clara

    gracias…

    John

    septiembre 4, 2009 at 3:42 pm

  4. Talves podrias dar otros ejemplos, si no es mucha molestia

    John

    septiembre 4, 2009 at 3:46 pm

  5. Muy interesante, el uso del pivote, no lo habia aplicado en mis funciones, intente de otras formas, pero este muy buen trabajo, voy a aplica lo que mencionas

    marck

    noviembre 5, 2009 at 4:26 pm

  6. Hola ronyl la verdad me encanta el trabajo que realizas, yo estoy estudfiando programacion y justo encontre esta informacion y me ayudo mucho gracias

    dina

    noviembre 5, 2009 at 4:43 pm

  7. GENIAAAAAAAAAAAAAAAAAAAAAAAAAL simplemente asi: GENIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAL

    Lucia del mar

    agosto 21, 2011 at 8:07 pm

  8. especialmente tu forma de explicar :D

    Lucia del mar

    agosto 21, 2011 at 8:08 pm

  9. [...] - En la Ciencia de la Computación: Algoritmos críticos para el desarrollo de software usan la técnica divide y vencerás para ganar eficiencia y performance.  Hace 2 años escribí sobre uno de los algoritmos de ordenamiento de datos más eficientes: El Quicksort. Si eres programador o te interesan los algoritmos puedes leer la explicación aquí. [...]

  10. thanks soo much for the information =D are u a good programing =D thanks again

    JoseTobon

    octubre 7, 2011 at 3:45 pm

  11. Estupendo trabajo, nunca cambies!

    Barcelona

    octubre 16, 2011 at 9:59 am

  12. buena aportacion cuando termine mi curso de programacion subire todos mis programas para seguir compartiendo…..compartir no es piratear xD

    sila

    octubre 17, 2011 at 7:49 pm

  13. Gracias brother!!!

    SUCIOJOE

    noviembre 2, 2011 at 2:35 pm

  14. Muchas gracias, andaba algo confundido y me ayudó mucho tu post

    herman

    febrero 6, 2012 at 10:33 am

  15. Muy bueno amigo! aunque aun no lo entiendo por completo es el mejor explicado!! Gracias

    Chava Dee Laa OO

    marzo 21, 2012 at 2:49 pm

  16. Amigo muy buen programa demasiado bien explicado gracias.!!

    Andres

    mayo 29, 2012 at 9:16 pm

  17. lo mejor me ayudo demasiado.. estoy muy agradecida tenia demaciadas dudasss gracias q dios les bendiga

    marigel

    junio 8, 2012 at 11:04 pm

  18. Excelente! gracias por compartirlo. Saludos desde Caracas-Venezuela

    Kenis

    junio 10, 2012 at 1:54 pm

  19. muy bueno son mis primeros pasos graias

    juan mayta

    octubre 23, 2012 at 1:33 pm

    • MUY BUENO SON MIS PRIMEROS PASOS EN PROGRAMACIÓN DESDE LA PAZ – BOLIVIA A 3600 METROS DE ALTURA

      juan mayta

      octubre 23, 2012 at 1:45 pm

  20. […] El quicksort.cpp lo pueden encontrar aquí: http://ronnyml.wordpress.com/2009/07/19/quicksort-en-c/ […]

    • Excelente trabajo muy completo …lo que estaba buscando ..te agradezco mucho, sigue compartiendo tus conocimientos!!!

      Wilman

      noviembre 21, 2013 at 12:56 am

  21. Muchas gracias, justamente necesitaba hacer las mediciones de tiempos de ejecución, me ahooró un montón de trabajo. :3

    Jonathan Amaya

    marzo 13, 2014 at 6:08 pm

  22. Exelente explicacion :)

    Joseph salas

    marzo 21, 2014 at 8:31 pm

  23. Excelente progrma y explicacion, gracias

    fabian

    junio 15, 2014 at 7:43 pm


Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: