6.1.2 Quick Sort Ordenacion

Ordinación por el método quicksort

El método de ordenación quicksort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Es también conocido como método rápido y de ordena por partición.  Este método es una mejora sustancial détodo de intercambio direct0  y se denomina quicksort rapido— por la velocidad con que ordena los elemento del arreglo. Su autor, C. A. Hoare, lo llamo así. La idea central de este algoritmo con en lo siguiente:

1.     Se toma un elemento X de una posición cualquiera del arreglo.

2.     Se trata de ubicar a X en la posición correcta del arreglo, de tal forma que todo los elementos que se encuentren a su izquierda sean menores o iguales a X y todos los se encuentren a su derecha sean mayores o iguales a X.

3.     Se repiten los pasos anteriores, pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición de X en el arreglo.

4.     El proceso termina cuando todos los elementos se encuentran en su posición correcta en el arreglo.

Se debe seleccionar, entonces, un elemento X cualquiera. En este caso se seleccionará A[l]. Se empieza a recorrer el arreglo de derecha a izquierda comparando si elementos son mayores o iguales a X. Si un elemento no cumple con esta condición, se intercambian aquellos y se almacena en una variable la posición del elemento intercambiado —se acota el arreglo por la derecha—. Se inicia nuevamente el recorrido. pero ahora de izquierda a derecha, comparando si los elementos son menores o iguales a X.

Si un elemento no cumple con esta condición, entonces se intercambian aquellos y se almacena en otra variable la posición del elemento intercambiado —se acota el arreglo por la izquierda—. Se repiten los pasos anteriores hasta que el elemento X encuentra su posición correcta en el arreglo. Analicemos a continuación el siguiente ejemplo.

Supongamos que se desea ordenar los elementos que se encuentran en el arreglo A utilizando el método.

�

A:    15    67    08    16   44    27    12    35

1.     Se selecciona A[1], por lo tanto, X <- 15.

2.     Se llevan a cabo las comparaciones que se muestran a continuación:

PRIMERA PASADA

Recorrido de derecha a izquierda

• A[8]  >  X              (35 ≥ 15)              no hay intercambio
• A[7]  >  X              (12 ≥15)               si hay intercambio

A:    12*   67   08   16   44    27    15*    35

Nota:  La cota con el * indica los elementos a intercambiar.

Recorrido de izquierda a derecha

• A [2]   <  X            (67  ≤  15)             si hay intercambio

A:    12    15*    08    16    44    27    67*    35

SEGUNDA PASADA

Recorrido de derecha a izquierda

• A[6]  >  X        (27 ≥ 15)       no hay intercambio
• A[5]  >  X        (44 ≥ 15)       no hay intercambio
• A[4]  >  X        (16 ≥ 15)       no hay intercambio
• A[3]  >  X        (08 ≥ 15)       si hay intercambio

  
A:    12    08*    15*    16    44    27    67    35

Como el recorrido de izquierda a derecha se debería iniciar en la misma posición donde se encuentra el elemento X, el proceso termina ya que se detecta que el elemento X se encuentra en la posición correcta. Observe que los elementos que forman parte del primer conjunto son menores o iguales a X, y los del segundo conjunto son mayores o iguales a X.

�

A:    12   08    15    16    44    27    67    35

• ler. Conjunto  conformados por los elementos 12, 08
• posición de X en el elemento 15
• 2o. conjunto conformados por los elementos 16, 44, 27, 67, 35

Este proceso de aprisionamiento aplicado para localizar la posición correcta de elemento X en el arreglo se repite cada vez que queden conjuntos formados por dos o más elementos. El método se puede aplicar de manera iterativa o recursiva.

El algoritmo de ordenación por el método quicksort en su versión recursiva es:

Rapido_recursivo (A, N)
{Este algoritmo ordena los elementos del arreglo unidimensional utilizando el método rápido. de manera recursiva. A es un arreglo unidimensional de N elementos}

1. Llamar al algoritmo Reduce_recursivo con 1 y N

Observe que el algoritmo Rapido_recursivo requiere para su funcionamiento otro algoritmo

Reduce_recursivo (INI, FIN, INI y FIN representan las posiciones del extremo izquierdo y derecho, respectivamente, del conjunto de elementos a ordenar}
{IZQ, DER, POS y AUX son variables de tipo entero. BAND es una variable de tipo
booleano}

1. Hacer IZQ <- INI, DER <- FIN, POS <- INI y BAND <- VERDADERO
2. Mientras (BAND = VERDADERO) Repetir
       Hacer BAND <- FALSO
       2.1. Mientras ((A[POS]  ≤  A[DER]) y (POS  ≠  DER)) Repetir
               Hacer DER <- DER - 1
       2.2. {Fin del ciclo del paso 2.1}
       2.3. Si (POS ≠ DER) entonces
               Hacer AUX <- A[POS], A[POS] <- A[DER],
                     A[DER] <- AUX y POS <- DER
               2.3.1. Mientras ((A[POS]  ≥  A[IZQ]) y (POS  ≠  IZQ)) Repetir
                          Hacer IZQ <- IZQ + 1
               2.3.2. {Fin del ciclo del paso 2.3.1}
               2.3.3. Si (POS  ≠  IZQ) entonces
                          Hacer BAND <- VERDADERO, AUX <- A[POS],
                                 A[POS] <- A [IZQ], A [IZQ] <- AUX y POS <- IZQ
               2.3.4. {Fin del condicional del paso 2.3.3}
       2.4. {Fin del condicional del paso 2.3}
3. {Fin del ciclo del paso 2}
4.  Si ((POS - 1) > INI) entonces
       Regresar a Reduce_recursivo con INI y (POS - 1) {Llamada recursiva}
5. {Fin del condicional del paso 4}
6. Si (FIN > (POS + 1)) entonces
       Regresar a Reduce_recursivo con (POS + 1) y FIN {Llamada recursiva}
6. {Fin del condicional del paso 6}

Aun cuando el algoritmo del quicksort presentado resulte claro, es posible aumentar su velocidad de ejecución eliminando las llamadas recursivas. La recursividad es un instrumento muy poderoso, pero la eficiencia de ejecución es un factor muy importante en un proceso de ordenación que es necesario cuidar y administrar muy bien. Estas llamadas recursivas se pueden sustituir utilizando pilas, dando lugar entonces a la interactividad.

Al utilizar la interactividad, se deben almacenar en las pilas los índices de los dos conjuntos de datos que falta tratar. Se utilizaran dos pilas, PILAMENOR y PILAMAYOR. En la primera se almacenara el extremo izquierdo y en la otra se almacenara el extremo derecho de los conjuntos de datos que falta tratar.

Los índices del primer conjunto quedaron almacenados en la primera posición de PILAMENOR y PILAMAYOR, respectivamente. La posición del extremo izquierdo del primer conjunto (1) en PILAMENOR y la del extremo derecho del mismo conjunto (2) en PILAMAYOR. Las posiciones de los extremos izquierdos y derecho del segundo conjunto (4 y 8) fueron almacenados en la cima de PILAMENOR y PILAMAYOR, respectivamente.

A continuación se presenta el algoritmo de ordenación por el método del quicksort utilizando interactividad en lugar de recursividad.

Rapido_iterativo (A, N)
{Este algoritmo ordena los elementos de un arreglo unidimensional utilizando el método rápido, de manera iterativa. A es un arreglo unidimensional de N elementos}
{TOPE, INI, FIN y POS son variables de tipo entero. PILAMENOR y PILAMAYOR son arreglos unidimensionales, que funcionan como pilas}

1. Hacer TOPE <- 1, PILAMENOR[TOPE] <- 1 y PILAMAYOR[TOPE] <- N
2. Mientras (TOPE > 0) Repetir
        Hacer INI <- PILAMENOR [TOPE],
                  FIN <- PILAMAYOR[TOPE]  y
                  TOPE <- TOPE - 1
         Llamar al algoritmo Reduce_iterativo con INI, FIN y POS.
         2.1. Si (INI < (POS - 1)) entonces
                Hacer TOPE <- TOPE + 1,
                       PILAMENOR[TOPE] <- INI  y
                       PILAMAYOR[TOPE] <- POS - 1
         2.2. {Fin del condicional del paso 2.1}
         2.3. Si (FIN > (POS + 1)) entonces
                 Hacer TOPE <- TOPE + 1,
                        PILAMENOR [TOPE] <- POS + 1  y
                        PILAMAYOR[TOPE] <- FIN
          2.4. {Fin del condicional del paso 2.3}
3. {Fin del ciclo del paso 2}

Note que el algoritmo Rapido_iterativo necesita para su funcionamiento de algoritmo, el cual se presenta a continuación.

Reduce_iterativo(I NI,FIN,POS) INI y FIN representan las posiciones de los extremos izquierdo y derecho, respectivamente, del conjunto de elementos a evaluar. POS es una variable donde se almacenara el resultado; este algoritmo IZQ, DER y AUX son variables de tipo entero. BAND es una variable de tipo booleano}

1. Hacer IZQ <- INI, DER <- FIN, POS <- INI y BAND <- VERDADERO
2. Mientras (BAND = VERDADERO) Repetir
       2.1. Mientras ((A[POS]  ≤  A [DER]) y (POS  ≠  DER)) Repetir
                Hacer DER <- DER -1
       2.2. {Fin del ciclo del paso 2.1}
       2.3. Si (POS = DER)
              entonces
                   Hacer BAND  <-  FALSO
                  si no
                        Hacer AUX <- A[POS], A[POS] <- A[DER],
                                   A[DER] <- AUX  y  POS <- DER
                   2.3.1. Mientras ((A[POS]  ≥ A[IZQ]) y (POS ≠ IZQ)) Repetir
                                   Hacer IZQ <- IZQ +1
                   2.3.2 {Fin del ciclo del paso 2.3.1}
                   2.3.3. Si (POS = IZQ)
                            entonces
                                    Hacer BAND  <- FALSO 
                            si no
                                     Hacer AUX <- A[POS], A[POS] <- A [IZQ],
                                    A[lZQ] <- AUX y POS <- IZQ
       2.3.4. {Fin del condicional del paso 2.3.3 }
       2.4. {Fin del condicional del paso 2.3}
3. {Fin del ciclo del paso 2}

Análisis de eficiencia del método quicksort

El método quicksort es el más rápido de ordenación interna que existe en la actualidad. Esto es sorprendente, porque el método tiene su origen en étodo de intercambio directo, el peor de todétodos directos. Diversos estudios realizados sobre su comportamiento demuestran que si se escoge en cada pasada el elemento que ocupa la posición central del conjunto de datos a analizar, el número de pasadas necesarias para ordenarlo es del orden de log n. Respecto del número de comparaciones, si el tamaño del arreglo es una potencia de 2, en la primera pasada realizara (n — 1) comparaciones, en la segunda (n - l)/2 comparaciones, pero en dos conjuntos diferentes, en la tercera realizara (n - l)/4 comparaciones, pero en cuatro conjuntos diferentes y así sucesivamente. Por lo tanto:
lo cual es lo mismo que:

C = (n - 1) + in - 1) + {n - 1) + ... + (n - 1)

Si se considera a cada uno de los componentes de la sumatoria como un término y el número de términos de la sumatoria es igual a m, entonces se tiene que:

C = (n - 1) * m

Considerando que el número de términos de la sumatoria (m) es igual al número de pasadas, y que este es igual a log n, la expresión anterior queda:

C = ( n –l )*log n

Sin embargo, encontrar el elemento que ocupe la position central del conjunto de datos que se van a analizar es una tarea difícil, ya que existen 1/n posibilidades de lograrlo. Además, el rendimiento medio del método es aproximadamente (2 * In 2) inferior al caso optimo, por lo que Hoare, el autor del método, propone como solución que el elemento X se seleccione arbitrariamente o bien entre una muestra relativamente pequeña de elementos del arreglo.

El peor caso ocurre cuando los elementos del arreglo ya se encuentran ordenados, o bien cuando se encuentran en orden inverso.
Como conclusión, se puede afirmar que el tiempo promedio de ejecución del algoritmo es proporcional a (n * log n), O(n * log n). En el peor caso, el tiempo de ejecución es proporcional a n2, O(n2).

Ejemplo en C, recursivo

void swap(int l[], int i, int j)
{

      int dummy;
      dummy=l[j];
      l[j]=l[i];
      l[i]=dummy;
}

int partions(int l[],int low,int high)
{
      int prvotkey=l[low];
      while (low<high)
      {
            while (low<high && l[high]>=prvotkey)
            --high;
            swap(l,high,low);
            while (low<high && l[low]<=prvotkey)
            ++low;
            swap(l,high,low);
      }

      return low;
}

void qsort(int l[],int low,int high)
{
      int prvotloc;
      if(low<high)
      {
            prvotloc=partions(l,low,high);
            qsort(l,low,prvotloc);
            qsort(l,prvotloc+1,high);
      }
}

void quicksort(int l[],int n)
{
      qsort(l,0,n);
}