Instituto Tecnolgico de Ciudad Madero Dra.
Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
4. 3 ORDENAMIENTO QUICKSORT (pag 159 Libro de Sara Baase)
4.3.1. Estrategia General
El Algoritmo Quicksort usa el Paradigma divide y vencers y fue publicado en 1962 por
C.A.R. Hoare. En el paso dividir: se reacomodan los elementos de modo que todas las
claves menores que un elemento pivote queden a la izquierda y la mayores o iguales a la
derecha. En el paso vencer: si la implementacin se hace con arreglos, no hay nada que
hacer porque los elementos ya estn en su posicin correcta.
4.3.2 Algoritmo
Bosquejo QuickSort (arreglo, lmites)
1 Si existe ms de un elemento en el arreglo acotado por lmites
2 Partir el arreglo: menores a la izquierda y mayores a la derecha
3 Ordenar con Quicksort la particin izquierda.
4 Ordenar con Quicksort la particin derecha.
Algoritmo QuickSort (E, primero, ultimo)
Entradas: Arreglo E, e ndices primero y ultimo que delimitan el subarreglo
a ordenar contenido en E[primero,...,ultimo].
Salidas: E[primero,...,ultimo] en orden ascendente.
1 if (primero < ultimo)
2 puntoPartir ! partir(E, primero, ultimo)
3 quickSort (E, primero, puntoPartir-1)
4 quickSort (E, puntoPartir+1, ultimo)
pivote
E
puntoPartir
primero ltimo
E [ ] < pivote E[ ] ! pivote
primero ultimo
primero ultimo
.
.
.
.
.
.
45 14 62 46 51 20
20 14 46 51 62
14
51 62
45
20 "
46 "
62
51 "
14 20 45 46 51 62
Combina
Divide
E
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
4.3.3 Una Estrategia para la Funcin Partir
Quicksort (nivel de recursividad 0):
45, 14, 62, 46, 51, 20
primero ultimo
Partir: pivote = 45; i = primero; j = ltimo
__, 14, 62, 46, 51, 20
i j
20, 14, 62, 46, 51, __
i j
20, 14, 62, 46, 51, __
i j
20, 14, __, 46, 51, 62
i j
20, 14, __, 46, 51, 62
i j
20, 14, __, 46, 51, 62
i j
20, 14, 45, 46, 51, 62
!
pivote
<
pivote
espacio
no
examinado
Regin baja Regin alta
examina
avanzando i
examina
retrocediendo j
Mueve a posicin
vacante
Mueve a posicin
vacante
Regin Alta
Regin Baja
Regin Alta
Regin Baja
! pivote
< pivote
E[j] ! pivote?
No, entonces mueve E[j]
E[i] < pivote?
Si, entonces avanza i
E[i] < pivote?
No, entonces mueve E[i]
E[j] ! pivote?
Si, entonces retrocede j
E[j] ! pivote?
Si, entonces retrocede j
j > vacante? No, termina
i < vacante? No, termina
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
Algoritmo partir (E, primero, ultimo)
Entradas: Arreglo E, e ndices primero y ultimo que delimitan el subarreglo
E[primero,...,ultimo] que se particionar.
Salidas: Regresa a puntoPartir, la ubicacin del pivote; reacomoda E en dos
subintervalos, tales que E[primero,..., puntoPartir-1] son menores que
pivote y E[puntoPartir + 1,...,ultimo] son mayores o iguales.
1 pivote ! E[primero]
2 vacante ! primero
3 i ! primero
4 j ! ultimo
5 while (i < j)
6 while (j > vacante) //expande regin alta
7 if(E[j]< pivote)
8 E[vacante] ! E[j]
9 vacante ! j
10 i++
11 break
12 else j -- //Seguir buscando
13
14 while (i < vacante) // expande regin baja
15 if(E[i] ! pivote)
16 E[vacante] ! E[i]
17 vacante ! i
18 j--
19 break
20 else i ++ //Seguir buscando
21 E[vacante] ! pivote
22 return vacante
4.3.4 Implementacin en Lenguaje C
QuickSort (arreglo, lmites)
1 Si existe ms de un elemento en el subarreglo delimitado por lmites
2 Extraer el pivote de la primera posicin del subarreglo
3 Partir el subarreglo usando el pivote
4 Almacenar el pivote en el punto de particin.
5 Ordenar con Quicksort la particin izquierda.
6 Ordenar con Quicksort la particin derecha.
void quickSort (Elemento E[ ], int primero, int ultimo)
{
if (primero < ultimo)
{
Elemento elementoPivote = E[primero];
Clave pivote = [Link];
int puntoPartir = partir (E, pivote, primero, ultimo);
E [puntoPartir] = elementoPivote;
quickSort (E, primero, puntoPartir-1);
quickSort (E, puntoPartir+1, ultimo);
}
}
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
Partir (arreglo, pivote, limites)
1. Inicializar ndices de exploracin con los lmites.
2. Mientras exista ms de un elemento en el espacio no examinado
Explorar de derecha a izquierda; extendiendo la regin alta con los elementos que
son mayores o iguales que el pivote. Termina cuando encuentra un elemento
menor que el pivote, el cual se mueve a una posicin vacante en la regin baja.
Explorar de izquierda a derecha; extendiendo la regin baja con los elementos que
son menores que el pivote. Termina cuando encuentra un elemento mayor o
igual que el pivote, el cual se mueve a una posicin vacante en la regin alta.
Actualizar ndices de exploracin.
3. Regresar como punto de partir la posicin donde se encuentren los ndices de
exploracin.
ExtenderReginAlta (arreglo, pivote, limites de la regin)
1. Inicializar vacante de baja con el lmite inferior de la regin.
2. Inicializar ndice de exploracin del arreglo con el lmite superior.
3. Mientras no se alcance el lmite inferior de la regin
Si elemento actual no pertenece a la regin alta.
Pasar elemento a posicin sealada por vacante baja.
Hacer que vacante alta tome la posicin de exploracin actual
Si no
Continuar con el elemento precedente.
4. Regresar a la posicin de vacante alta.
Avance para el primer ciclo partir
int partir (Elemento[] E, Clave pivote, int primero, int ultimo)
int bajo, alto;
Pivote=E[primero]
no examinada
primero ltimo
no examinada
bajo alto
vacante
baja
vacante
baja
!pivote < pivote
regin alta
explorada
actual
no examinada
< pivote !pivote
vacante
alta
Extender
regin
alta
no examinada
!pivote
vacante
alta
pivote
regin baja
explorada
regin alta
explorada
no examinada
< pivote ! pivote
vacante
baja
regin baja
explorada
regin alta
explorada
Extender
regin
baja
regin alta
explorada
< pivote
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
bajo = primero; alto = ultimo;
while (bajo < alto)
int vacAlta = extenderRegionGrande (E, pivote, bajo, alto);
int vacBaja = extenderRegionChica (E, pivote, bajo+1, vacAlta);
bajo = vacBaja; alto = vacAlta-1;
return bajo; //ste es puntoPartir
/** Condicin posterior de extenderRegionAlta:
* El elemento de la extrema derecha de E[vacBaja+1],..., E[alto]
* cuya clave es < pivote, se transfiere a E[vacBaja] y
* se devuelve el ndice de la posicin en la que estaba.
* Si no hay tal elemento, se devuelve vacBaja.
*/
int extenderRegionAlta (Elemento[] E, Clave pivote, int vacBaja, int alto)
int vacAlta, actual;
vacAlta = vacBaja; //Suponer fracaso, ninguna clave < pivote
actual = alto;
while (actual > vacBaja)
if(E[vacBaja].clave<pivote)
E[vacBaja] = E[actual]; //xito
vacAlta = actual;
break;
actual --; //Seguir buscando
return vacAlta;
/** Condicin posterior de extenderRegionBaja */
int extenderRegionBaja (Elemento[] E, Clave pivote, int bajo, int vacAlta)
int vacBaja, actual;
vacBaja = vacAlta; //suponer fracaso, ninguna clave pivote
actual = bajo;
while (actual < vacAlta)
if(E[actual].clave ! pivote)
E[vacAlta] = E[actual]; //xito
vacBaja = actual;
break;
actual ++; //Seguir buscando
return vacBaja;
4.3.5 Ejemplo
a) Extraer pivote
pivote
45 14 62 46 51 20 E
primero ltimo
bajo alto
45 14 62 46 51 20
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
b) Partir arreglo
14 62 46 51 20
vacanteBaja
actual
(20 < pivote)
regin sin examinar
20 14 62 46 51
vacanteAlta
actual
(62 ! pivote)
extender
ReginAlta
(sentido de la
exploracin)
extender
ReginBaja
(sentido de la
exploracin)
20 14 46 51 62
vacanteBaja
regin sin examinar
regin sin examinar
20 14 62 46 51
vacanteAlta
regin sin examinar
Regin
Baja
Regin
Baja
(51> pivote)
20 14 62 46 51
vacanteAlta actual
(14 < pivote)
regin sin examinar
Regin
Baja
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
c) Almacenar pivote
d) Ordenar con el procedimiento quickSort la particin izquierda
e) Ordenar con el procedimiento quickSort la particin derecha
20 14 46 51 62
20 14 45 46 51 62
< pivote ! pivote
20 14 pivote
14
"
14 20
20
20 14 46 51 62
vacanteBaja actual
regin sin examinar
extender
ReginAlta
(sentido de la
exploracin)
Regin
Alta
Regin
Baja
vacanteBaja actual
regin sin examinar
(46> pivote)
Regin
Alta
Regin
Baja
20 14 46 51 62
vacanteAlta
actual
regin sin examinar
Regin
Alta
Regin
Baja
20 14 46 51 62
extender
ReginBaja
vacanteAlta
actual
Regin
Alta
Regin
Baja
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
f) Despus del paso e, el arreglo termina ordenado.
4.3.6 Complejidad de peor caso
En cualquier invocacin de partir donde se requieren acomodar los elementos
almacenados en k posiciones, partir extrae el pivote quedando un espacio vacante:
Dado que hay k - 1 claves, entonces partir efecta k -1 comparaciones de claves para
acomodarlas en dos regiones.
El peor caso sucede cuando partir divide el intervalo de k posiciones como sigue (el
arreglo ya est ordenado):
As, en cada ocasin que se invoca al algoritmo partir, el nmero de elementos y
comparaciones se reducir como se muestra en el rbol de recursin:
pivote
62
"
46 51 62 46 51 62
51 62
"
14 20 45 46 51 62
vacante
lim inferior lim superior
k posiciones
k-1 posiciones
pivote ! <
intervalo
vaco
(regin baja)
intervalo
con k-1 posiciones
(regin alta)
46
51
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
No. de
elementos
K
No. de comparaciones
( 1) k !
k n = 1 n !
1 k n = ! 2 n !
2 k n = ! 3 n !
.
.
.
.
.
.
3 k = 2
2 k = 1
El nmero total de comparaciones de clave se obtiene sumando el nmero de
comparaciones (k-1) de cada nivel con k elementos:
( 1)
( )
2
n n
W n
!
=
2
( ) ( ) W n n ! "
Un anlisis equivalente se obtiene observando directamente los valores de serie:
1
1
( ) 1 2 ... ( 3) ( 2) ( 1)
( )
n
i
W n n n n
W n i
!
=
= + + + ! + ! + !
=
"
( 1)
( )
2
n n
W n
!
=
2
( ) ( ) W n n ! "
4.3.7 Comportamiento promedio
a) Comparaciones en el nivel cero.
n
n-1
n-2
2
n
"
pivote
"
pivote
"
pivote
1
2 1
( ) ( 1)
n n
k k
W n k k
!
= =
= ! =
" "
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
b) Posiciones posibles para ubicar el pivote en i.
c) Ejemplo de partir en el punto i=3; y el nmero de comparaciones promedio que se
efectan para ordenar las particiones izquierda y derecha.
d) Nmero de comparaciones en el caso promedio.
Comparaciones para ordenar un arreglo con uno o cero elementos
(1) (0) 0 A A = =
Comparaciones para ordenar un arreglo de tamao n
( )
1
0
1
( ) ( 1) ( ) ( 1 )
n
i
A n n A i A n i
n
!
=
" #
= ! + + ! !
$ %
& '
(
( ) 1.386 lg 2.846 A n n n n ! " (Ver pginas 167 y 168 del libro de Sara Baase)
( ) ( log ) A n n n ! " #
4.3.8 Complejidad de mejor caso
El mejor desempeo del algoritmo quickSort ocurre cuando el procedimiento particion
divide en partes iguales el segmento dado, generando un rbol de particin balanceado.
vaco
n-1 comparaciones
n
0 n -1
i
0 1 2 3 4 5 6 7
i
A(i)=A(3) A(n-1-i)=A(4)
n = 8
Comparaciones
de partir en ese
nivel Probabilidad de
cada particin
Posibles
posiciones del
punto de
particin
Comparaciones
para ordenar la
parte izquierda
Comparaciones
para ordenar la
parte derecha
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
Primera aproximacin
Sea:
m = nmero de niveles del rbol de particin balanceado
lg m n =
c = nmero de comparaciones en un nivel
1 c n ! "
En el mejor caso, el nmero de comparaciones totales es a lo ms:
( )
( ) ( 1)(lg )
( ) ( log )
B n cm
B n n n
B n n n
!
! "
#$
Segunda aproximacin
El nmero de elementos y comparaciones disminuye en cada llamada al procedimiento
partir, tal como se ilustra en el rbol de recursin:
Nivel de
recursividad
No. de
subarreglos
No. de elementos en cada
subarreglo
No. de comparaciones
en cada subarreglo
No. de comparaciones
en todos los subarreglos
0 1 n n-1 n-1
1 2 (n-1)/2 ((n-1)/2)-1= (n-3)/2 ( (n-3)/2)*2= n-3
2 4 (((n-1)/2)-1)/2= (n-3)/4 ((n-3)/4)-1= (n-7)/4 ( (n-7)/4)*4= n-7
3 8 (((n-3)/4)-1)/2= (n-7)/8 ((n-7)/8)-1= (n-15)/8 ((n-15)/8)*8= n-15
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0|1 0 0
Tomando los valores del nmero de comparaciones totales en cada nivel del rbol de
particin, se obtiene la siguiente serie:
( ) ( 1) ( 3) ( 7) ( 15) ... 0 B n n n n n = ! + ! + ! + ! + +
n
(n-1)/2
(n-3)/4
pivote
pivote
(n-1)/2
(n-3)/4
pivote
(n-3)/4
(n-3)/4
pivote
(n-7)/8
(n-7)/8
pivote
(n-7)/8
(n-7)/8
pivote
(n-3)/8
(n-7)/8
pivote
(n-7)/8
(n-7)/8
0|1 0|1
0|1 0|1 0|1 0|1 0|1 0|1 0|1 0|1 0|1 0|1 0|1 0|1 0|1 0|1
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
La siguiente expresin permite generar cada uno de los elemento de la serie:
1
2 1
i
n
+
! +
Para obtener los lmites de la serie se iguala la expresin generadora a los trminos primero
y ltimo:
1
1
1
2 1 1
2 2
lg 2 lg 2
1 1
0
i
i
i
n n
i
i
+
+
+
! + = !
=
=
+ =
=
1
2 1 0
1
2
2
1
lg
2
i
i
n
n
n
i
+
! + =
+
=
+ " #
=
$ %
& '
Para obtener la complejidad de mejor caso se utiliza la serie geomtrica
1
0
2 2 1
k
i k
i
+
=
= !
"
1
lg
2
1
0
1 1 1
lg lg lg
2 2 2
0 0 0
1
lg 1
2
( ) ( 2 1)
( ) 2 2 1
1 1
( ) lg 1 2 2 1 lg 1
2 2
1 1
( ) lg 2 2 1
2 2
n
i
i
n n n
i
i i i
n
B n n
B n n
n n
B n n
n n
B n n n
+ ! "
# $
% &
+
=
+ + + ! " ! " ! "
# $ # $ # $
% & % & % &
= = =
+ ! "
+
# $
% &
= ' +
= ' +
! "
! + " ! + " ! " ! "
= + ' ' + + # $
# $ # $ # $ # $
# $
% & % & % & % &
% &
+ + ! " ! "
= + ' '
# $ # $
% & % &
(
( ( (
( ) ( )
1
lg 1
2
( ) lg( 1) lg 2 lg( 1) lg 2 1
( ) lg( 1) lg( 1) 1 1
( ) lg( 1) 2 lg( 1)
( ) ( lg )
n
B n n n n n
B n n n n n n
B n n n n n
B n n n
! + " ! "
+ +
# $ # $
% & % &
= + ' ' + + ' +
= + ' ' + + ' +
= + ' + +
)*
4.3.9 Mejoras al algoritmo QuickSort bsico
Seleccin de pivote:
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
a) Escoger al azar un entero q entre primero y ltimo.
b) La mediana de las claves en las posiciones: primero, (primero+ltimo)/2, ltimo.
En ambos casos, el pivote se intercambiar con el primer elemento antes de proceder con el
algoritmo partir.
Estrategias de particin:
a) Intercambiar elementos durante el recorrido de las regiones.
Ordenamiento pequeo:
a) Evitar quickSort para n pequea (n " 10), debido al procedimiento fijo que implica la
invocacin de procedimientos.
b) Modificar quickSort para que ordene subconjuntos pequeos con una tcnica sencilla:
Optimizacin del espacio de pila:
La profundidad de recursin con quickSort puede llegar a ser muy grande, proporcional a n
en el peor caso.
. . .
0 1 2 3 n
intercambio
elegido al azar
< "
intercambio
" <
regiones
n=30
n=10
n=19
quickSort
quickSort burbuja
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
Estrategia ORT (optimizacin de recursin trasera)
Esta estrategia evita que la profundidad de la recursin sea excesiva, y consiste en que
despus de cada particin, la siguiente invocacin recursiva trabaja con el subintervalo ms
pequeo y que el mayor subintervalo se maneje directamente en un ciclo. En otras palabras
el proceso consiste en:
a) Ordenar recursivamente el segmento ms pequeo.
b) Ordenar iterativamente el segmento ms grande.
Condiciones importantes de ORT:
! El ciclo while avanza si existe ms de 1 elemento.
! La recursividad se encuentra inmersa en el ciclo while, por lo tanto la condicin del while
detiene la recursividad.
! La recursin se aplica al subsegmento ms pequeo, esto es, al que sea menor que la
mitad del segmento.
Algorithm QuickSortORT(arreglo, lmites del arreglo)
1. lmites_iterativos = lmites_del_arreglo
2. Mientras existan ms de dos elementos en el arreglo delimitado por
lmites_iterativos
Extraer pivote.
5
4
3
2
1
"
cumple
condicin de
avance
(primero<ltimo)
si
si
si
si
no
Nivel de
recursividad
0
1
2
3
4
n
n-1
n-2
1
.
.
.
Nivel de
recursividad
0
1
2
.
.
.
n-1
Llamadas
recursivas
2
2
2
.
.
.
0
No. De
llamadas
recursivas
= 2(n-1)
a) Profundidad de un caso b) Profundidad en general
"
"
"
"
"
"
"
Instituto Tecnolgico de Ciudad Madero Dra. Laura Cruz Reyes
Unidad II TCNICAS DE DISEO DE ALGORITMOS Captulo 4 Ordenamiento y Bsqueda
Partir el arreglo usando el pivote.
Almacenar el pivote en la posicin dada por partir
Actualizar lmites: lmites_iterativos, lmites_recursivos
Llamar a quickSort con lmites_recursivos
3. Regresar
Algorithm quickSortORT(Elemento[] E, int primero, int ultimo)
int primero1, ultimo1, primero2, ultimo2;
primero2 = primero;
ultimo2 = ultimo;
while(ultimo2-primero2>1)
elementoPivote = E[primero];
pivote = [Link];
int puntoPartir = partir(E, pivote, primero2, ultimo2);
E[puntoPartir] = elementoPivote;
if (puntoPartir < (primero2 + ultimo2) / 2)
primero1 = primero2;
ultimo1 = puntoPartir - 1;
primero2 = puntoPartir + 1;
ultimo2 = ultimo1;
else
primero1 = puntoPartir + 1;
ultimo1 = ultimo2;
primero2 = primero1;
ultimo2 = puntoPartir 1;
quickSort(E, primero1, ultimo1);
return;
