4

Algoritmos recursivos de ordenamiento 
Aunque actualmente existen varios algoritmos recursivos de ordenamiento y varias versiones 
de cada uno, nosotros sólo estudiaremos las versiones básicas de dos de ellos: Quick sort y 
Merge sort. Estos algoritmos son, por mucho, los más utilizados hoy en día. 

Quick sort En esencia, quick sort ordena un arreglo a[1], a[2], …, a[n] seleccionando el valor v de una 
llave en el arreglo como el elemento ​
pivote​
, alrededor del cual se organizarán el resto de los 
elementos en el arreglo. Idealmente, el pivote estará cerca al valor medio de las llaves en el 
arreglo, tal que sea precedido y seguido por aproximadamente la mitad de los registros. Se 
intercambian los elementos en el arreglo de tal forma que para alguna j, todos los registros con llaves menores a v aparezcan en a[1], a[2], …, a[j­1] y todos los registros con llaves 
mayores o iguales a v se ubiquen en a[j+1], a[j+2], …, a[n]. Entonces quick sort se aplica 
recursivamente a a[1], a[2], …, a[j­1] y a a[j+1], a[j+2], …, a[n] para ordenar ambos 
subarreglos.Debido a que las llaves de los registros en el primer grupo preceden a las llaves de los registros en el segundo grupo, el arreglo en su totalidad estará ordenado. 
 
Veamos una demostración del funcionamiento de quick sort. Consideremos un arreglo a 
como el que se muestra a continuación: 
 
 
 
El primer paso de este algoritmo es definir una posición cuyo valor servirá como pivote. 
Nosotros utilizaremos la posición n del arreglo, es decir la última posición. En este ejemplo, la 
última posición contiene un 3. 
 El siguiente paso se refiere a agrupar a todos aquellos números menores al pivote en las 
primeras j­1 posiciones y los números mayores o iguales al pivote se agrupan a partir de las 
posición j+1. La siguiente figura ilustra este caso. 
 
En este momento, tenemos que los números menores a 3 están ubicados antes de la cuarta 
posición y los mayores o iguales a 3 a partir de la quinta posición. 
 El siguiente, es el paso recursivo, en donde el algoritmo se aplica tanto para el subarreglo 
definido por los índices 1 y 3, como para el subarreglo definido por los índices 5 y 10. Si 
hacemos las llamadas recursivas sobre los subarreglos subsecuentes hasta que su tamaño 
sea 1, tenemos el siguiente resultado: 

 
 
Y así, finalmente, obtenemos el siguiente arreglo ordenado: 
 
 
 El siguiente es el algoritmo del método de ordenamiento quick sort. Nótese que este método 
está compuesto por dos funciones: una que es la función recursiva quick sort y otra que 
hacer la partición del arreglo. 
 
función​
 quickSort (RegistroT *a, entero p, entero r) 
comienza 
si​
 p < r ​
entonces 
q ← particionar (a, p, r) 
quickSort (a, p, q−1) 
quickSort (a, q+1, r) 
fin si 
fin 
 
función​ particionar (RegistroT *a, entero p, entero r) 
tipoLlave pivote 
entero último, i 
comienza 
// ​
a[r] es el registro elegido cuya llave ​
será ​
el pivote 
pivote ← a[r].llave 
 
// ​
indica el índice del último registro ​
cuya ​
llave es menor a x 
último ← p − 1 
 

// ​
Se agrupan los elementos menores a pivote en las primeras 
// ​
posiciones del arreglo a 
para​
 i ← p ​
hasta​
 r − 1 ​
hacer 
si​
 a[i].llave < pivote ​entonces 
último ← último + 1 
intercambiar (a[último], a[i]) 
fin si 
fin para 
 
// ​
Y se mueve al pivote a su posición correcta 
intercambiar (a[último+1], a[r]) 
regresar​
 último+1 

fin 
 
Regresemos al ejemplo anterior para analizar la ejecución de quick sort con detalle. 
Originalmente tenemos el arreglo 
 
a = {3, 1, 5, 1, 6, 9, 2, 4, 5, 3} 
 La primera llamada a la función quick sort, enviará quickSort (a, 1, 10), es decir, p = 1 y r = 
10. 
 
a = {3, 1, 5, 1, 6, 9, 2, 4, 5, 3} 
     ↑                          ↑ 
     p                          r 
 
Como p < r, procedemos a hacer la partición del arreglo. En este caso, pivote toma el valor 
de 3 y último se inicia en 0. Recordemos que las llaves de todos los registros en las ...