Quicksort en C++

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 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++.

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
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 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 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 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: Follow @ronnyml