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 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 laizquierda 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:

void quicksort(int *array, int inicio, int fin)
{
  int pivote;
  if (inicio < fin) {
    pivote = dividir(array, inicio, fin );
    quicksort( array, inicio, pivote - 1 ); //ordeno la lista de los menores
    quicksort( array, pivote + 1, fin ); //ordeno la lista de los mayores
  }
}

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í:

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

izq                                                                              der

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. a[izq]

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

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

while ((izq < der) && (array[izq] <= pibote)){
  izq++;
}

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

while (array[der] > pibote){
  der--;
}

Si al final de estas 2 operaciones, el índice izquierdo es menor al derecho se intercambian las posiciones a[izq] con a[der], 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[der];
array[der] = array[inicio]; // el pibote está en el inicio del array
array[inicio] = 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(a,0,5) // el pibote está en la posición 6
quicksort(a,7,12) // el pibote está en la posición 6

Se repite el mismo proceso con este primer subarray quicksort(a, 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(a,0,3) // la posición del pibote es 4
quicksort(a,5,5) // No se ejecuta nada, el inicio no es menor al final

El mismo proceso. Se ejecutar quicksort (a, 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 (a,0,1) // la posición del pibote es 2
quicksort (a,3, 3) // No se ejecuta nada, el inicio no es menor al final

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

2	1
1	2

Ahora se llamaría a quicksort(a, 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(a,7,10) // posición del pibote es 10 y la 1era 7
quicksort(a,11,12) //posición del pibote es 10 y la ultima 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(a, 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.

ini=clock(); // Antes del quicksort:
final = clock(); //Después que se ejecuta el quicksort
total =((double)(final – ini)) /
CLOCKS_PER_SEC; // El valor retornado por clock()
debe ser dividido por el valor de la macro 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++ disfrutenlo.

#include <iostream>
#include <time.h>
#include <stdio.h>

using namespace std;

//funcion para dividir el array y hacer los intercambios
int dividir (int *array, int inicio, int fin){
  int izq;
  int der;
  int pibote;
  int temp;

  pibote = array[inicio];
  izq = inicio;
  der = fin;

  //Mientras no se cruzen los índices
  while (izq < der){
    while (array[der] > pibote){
	  der--;
    }

	while ((izq < der) && (array[izq] <= pibote)){
      izq++;
    }

    // Si todavia no se cruzan los indices seguimos intercambiando
	if(izq < der){
      temp= array[izq];
      array[izq] = array[der];
      array[der] = temp;
    }
  }

  //Los indices ya se han cruzado, ponemos el pivote en el lugar que le corresponde
  temp = array[der];
  array[der] = array[inicio];
  array[inicio] = temp;

  //La nueva posición del pivote
  return der;
}

//funcion recursiva para hacer el ordenamiento
void quicksort( int *array, int inicio, int fin)
{
  int pivote;
  if(inicio < fin){
    pivote = dividir(array, inicio, fin );
    quicksort( array, inicio, pivote - 1 );//ordeno la lista de los menores
    quicksort( array, pivote + 1, fin );//ordeno la lista de los mayores
  }
}

int main()
{
  int const max = 100;
  int tamanyo;
  clock_t ini, final;
  double total;
  ini=clock();

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

  int a[tamanyo];
  srand(time(0));//para que el rand no genere siempre los mismos numeros, utilizando la hora del sistema

  for (int i = 0; i < tamanyo; i++){
    a[i] = rand() % max;//rand para generar enteros aleatorios
  }

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

  cout << endl << endl;

  quicksort(a, 0, tamanyo - 1 );

  final=clock();
  total=((double)(final - ini)) / CLOCKS_PER_SEC;
  printf("Tiempo de ejecucion : %lf segundos \n",total);

  cout << "Array ordenado " << endl;

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

  return 0;
}

---

Possibly related posts: (automatically generated)

• Se lanza el Microsoft Forefront Integration Toolkit para Network Access Pro…