Análisis y Diseño de Algoritmos

Prof: Ing. Victor Garro

Asistente: Marco Elizondo Vargas

ORDENAMIENTOS

Ordenamiento Quicksort

Esta es probablemente la técnica más rápida conocida. Fue desarrollada por C.A.R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos). El algoritmo fundamental es el siguiente:

Eliges un elemento de la lista. Puede ser cualquiera (en Optimizando veremos una forma más efectiva). Lo llamaremos elemento de división.
Buscas la posición que le corresponde en la lista ordenada (explicado más abajo).
Acomodas los elementos de la lista a cada lado del elemento de división, de manera que a un lado queden todos los menores que él y al otro los mayores (explicado más abajo también). En este momento el elemento de división separa la lista en dos sublistas (de ahí su nombre).
Realizas esto de forma recursiva para cada sublista mientras éstas tengan un largo mayor que 1. Una vez terminado este proceso todos los elementos estarán ordenados.

Una idea preliminar para ubicar el elemento de división en su posición final sería contar la cantidad de elementos menores y colocarlo un lugar más arriba. Pero luego habría que mover todos estos elementos a la izquierda del elemento, para que se cumpla la condición y pueda aplicarse la recursividad. Reflexionando un poco más se obtiene un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos contador por la izquierda, y j, al que llamaremos contador por la derecha. El algoritmo es éste:

Recorres la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento).
Cuando lista[i] sea mayor que el elemento de división y lista[j] sea menor los intercambias.
Repites esto hasta que se crucen los índices.
El punto en que se cruzan los índices es la posición adecuada para colocar el elemento de división, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados).

Al finalizar este procedimiento el elemento de división queda en una posición en que todos los elementos a su izquierda son menores que él, y los que están a su derecha son mayores.

Pseudocódigo en C.

Tabla de variables
Nombre	Tipo	Uso
lista	Cualquiera	Lista a ordenar
inf	Entero	Elemento inferior de la lista
sup	Entero	Elemento superior de la lista
elem_div	El mismo que los elementos de la lista	El elemento divisor
temp	El mismo que los elementos de la lista	Para realizar los intercambios
i	Entero	Contador por la izquierda
j	Entero	Contador por la derecha
cont	Entero	El ciclo continua mientras cont tenga el valor 1

 Nombre Procedimiento: OrdRap

 Parámetros:

    lista a ordenar (lista)

    índice inferior (inf)

    índice superior (sup)

    // Inicialización de variables

    1. elem_div = lista[sup];

    2. i = inf - 1;

    3. j = sup;

    4. cont = 1;

    // Verificamos que no se crucen los límites

    5. if (inf >= sup)

    6.      retornar;

    //  Clasificamos la sublista

    7. while (cont)

    8.      while (lista[++i] < elem_div);

    9.      while (lista[--j] > elem_div);

   10.      if (i < j)

   11.           temp = lista[i];

   12.           lista[i] = lista[j];

   13.           lista[j] = temp;

   14.      else

   15.           cont = 0;

   // Copiamos el elemento de división

   // en su posición final

   16. temp = lista[i];

   17. lista[i] = lista[sup];

   18. lista[sup] = temp;

   // Aplicamos el procedimiento

   // recursivamente a cada sublista

   19. OrdRap (lista, inf, i - 1);

   20. OrdRap (lista, i + 1, sup);

Nota:

La primera llamada debería ser con la lista, cero (0) y el tamaño de la lista menos 1 como parámetros.

Un ejemplo

Esta vez voy a cambiar de lista ;-D

5 - 3 - 7 - 6 - 2 - 1 - 4

Comenzamos con la lista completa. El elemento divisor será el 4:

5 - 3 - 7 - 6 - 2 - 1 - 4

Comparamos con el 5 por la izquierda y el 1 por la derecha.

5 - 3 - 7 - 6 - 2 - 1 - 4

5 es mayor que cuatro y 1 es menor. Intercambiamos:

1 - 3 - 7 - 6 - 2 - 5 - 4

Avanzamos por la izquierda y la derecha:

1 - 3 - 7 - 6 - 2 - 5 - 4

3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos ahí.

1 - 3 - 7 - 6 - 2 - 5 - 4

7 es mayor que 4 y 2 es menor: intercambiamos.

1 - 3 - 2 - 6 - 7 - 5 - 4

Avanzamos por ambos lados:

1 - 3 - 2 - 6 - 7 - 5 - 4

En este momento termina el ciclo principal, porque los índices se cruzaron. Ahora intercambiamos lista[i] con lista[sup] (pasos 16-18):

1 - 3 - 2 - 4 - 7 - 5 - 6

Aplicamos recursivamente a la sublista de la izquierda (índices 0 - 2). Tenemos lo siguiente:

1 - 3 - 2

1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha. Como se intercambiaron los índices termina el ciclo. Se intercambia lista[i] con lista[sup]:

1 - 2 - 3

Al llamar recursivamente para cada nueva sublista (lista[0]-lista[0] y lista[2]-lista[2]) se retorna sin hacer cambios (condición 5.).Para resumir te muestro cómo va quedando la lista:

Segunda sublista: lista[4]-lista[6]

7 - 5 - 6

5 - 7 - 6

5 - 6 - 7

Para cada nueva sublista se retorna sin hacer cambios (se cruzan los índices).

Finalmente, al retornar de la primera llamada se tiene el arreglo ordenado:

1 - 2 - 3 - 4 - 5 - 6 - 7

Eso es todo. Bastante largo ¿verdad?

Optimizando.

Sólo voy a mencionar algunas optimizaciones que pueden mejorar bastante el rendimiento de quicksort:

Hacer una versión iterativa: Para ello se utiliza una pila en que se van guardando los límites superior e inferior de cada sublista.
No clasificar todas las sublistas: Cuando el largo de las sublistas va disminuyendo, el proceso se va encareciendo. Para solucionarlo sólo se clasifican las listas que tengan un largo menor que n. Al terminar la clasificación se llama a otro algoritmo de ordenamiento que termine la labor. El indicado es uno que se comporte bien con listas casi ordenadas, como el ordenamiento por inserción por ejemplo. La elección de n depende de varios factores, pero un valor entre 10 y 25 es adecuado.
Elección del elemento de división: Se elige desde un conjunto de tres elementos: lista[inferior], lista[mitad] y lista[superior]. El elemento elegido es el que tenga el valor medio según el criterio de comparación. Esto evita el comportamiento degenerado cuando la lista está prácticamente ordenada.

Análisis del algoritmo.

Estabilidad: No es estable.
Requerimientos de Memoria: No requiere memoria adicional en su forma recursiva. En su forma iterativa la necesita para la pila.
Tiempo de Ejecución:

Caso promedio. La complejidad para dividir una lista de n es O(n). Cada sublista genera en promedio dos sublistas más de largo n/2. Por lo tanto la complejidad se define en forma recurrente como:

f(1) = 1

f(n) = n + 2 f(n/2)

La forma cerrada de esta expresión es:

f(n) = n log₂n

Es decir, la complejidad es O(n log₂n).

El peor caso ocurre cuando la lista ya está ordenada, porque cada llamada genera sólo una sublista (todos los elementos son menores que el elemento de división). En este caso el rendimiento se degrada a O(n²). Con las optimizaciones mencionadas arriba puede evitarse este comportamiento.

Ventajas:

Muy rápido
No requiere memoria adicional.

Desventajas:

Implementación un poco más complicada.
Recursividad (utiliza muchos recursos).
Mucha diferencia entre el peor y el mejor caso.

La mayoría de los problemas de rendimiento se pueden solucionar con las optimizaciones mencionadas arriba (al costo de complicar mucho más la implementación). Este es un algoritmo que puedes utilizar en la vida real. Es muy eficiente. En general será la mejor opción.