Particionamiento en Quick Sort con analisis de pivote

La idea en simple

Que hace Lomuto. El pivote es el ultimo elemento (aqui $6$). Recorres el arreglo con un dedo $j$. Llevas otro dedo $i$ que marca “hasta aqui todo es menor o igual que el pivote”. Cada vez que $A[j] \leq 6$, adelantas $i$ y metes ese elemento a la zona de los pequenos con un intercambio. Al final pones el pivote justo despues de la zona de los pequenos.

Primera particion de $[15,3,9,8,5,2,7,1,6]$: los que son $\leq 6$ (el $3$, el $5$, el $2$, el $1$) se van agrupando a la izquierda; los grandes ($15, 9, 8$) quedan a la derecha. El pivote $6$ aterriza en el medio:

$[3, 5, 2, 1, \;\mathbf{6}, \;9, 7, 8, 15]$

Todo a la izquierda de $6$ es menor, todo a la derecha es mayor. Luego se repite lo mismo, por separado, en cada mitad.

El truco del peor caso. Si el arreglo YA esta ordenado y siempre eliges el ultimo como pivote, el pivote es siempre el mas grande: una mitad queda vacia y la otra casi entera. En vez de partir por la mitad, quitas un solo elemento cada vez $\rightarrow$ haces $8+7+\dots+1 = 36$ comparaciones y el costo se dispara a $O(n^2)$. Se arregla eligiendo el pivote al azar o con “mediana de tres”.

Estabilidad. No es estable: dos elementos con el mismo valor pueden quedar en orden distinto al original, porque los intercambios los pueden cruzar.

Solucion formal

(a) Particion de Lomuto sobre $A = [15,3,9,8,5,2,7,1,6]$, pivote $A[8]=6$.

Invariante: al examinar $j$, el segmento $A[lo..i]$ contiene elementos $\leq$ pivote y $A[i+1..j-1]$ elementos $>$ pivote.

$$\begin{aligned} &j{=}1{:}\ 3\leq 6 \Rightarrow i{=}0,\ \text{swap}(0,1) &&[3,15,9,8,5,2,7,1,6]\\ &j{=}4{:}\ 5\leq 6 \Rightarrow i{=}1,\ \text{swap}(1,4) &&[3,5,9,8,15,2,7,1,6]\\ &j{=}5{:}\ 2\leq 6 \Rightarrow i{=}2,\ \text{swap}(2,5) &&[3,5,2,8,15,9,7,1,6]\\ &j{=}7{:}\ 1\leq 6 \Rightarrow i{=}3,\ \text{swap}(3,7) &&[3,5,2,1,15,9,7,8,6]\\ &\text{final: swap}(i{+}1,hi)=\text{swap}(4,8) &&[3,5,2,1,\mathbf{6},9,7,8,15] \end{aligned}$$

Comparaciones $= 8$, intercambios $= 5$.

(b) Posicion final del pivote: indice $4$. Izquierda $A[0..3] = [3,5,2,1]$ (todos $\leq 6$); derecha $A[5..8] = [9,7,8,15]$ (todos $> 6$).

(c) Sea $B = [1,\dots,n]$ ordenado con pivote $= A[hi]$. El pivote es el maximo, luego cada particion deja izquierda de tamano $n-1$ y derecha vacia. Recurrencia:

$T(n) = T(n-1) + (n-1) \implies T(n) = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2} = \Theta(n^2).$

Para $n=9$, comparaciones $= 36$. Por tanto $O(n^2)$. $\blacksquare$

(d) Estrategias para evitar el peor caso:

1. Pivote aleatorio $\Rightarrow$ tiempo esperado $O(n\log n)$ (ninguna entrada fija es adversaria).
2. Mediana de tres $\{A[lo], A[mid], A[hi]\}$ $\Rightarrow$ particiones balanceadas en datos casi ordenados.
3. Introsort (fallback a Heap Sort a profundidad $> 2\log n$) $\Rightarrow$ garantiza $O(n\log n)$ en el peor caso.

(e) Quick Sort de Lomuto no es estable. Contraejemplo con claves iguales $3_a, 3_b$:

$[3_a, 3_b, 1] \xrightarrow{\text{pivote }1,\ \text{swap}(0,2)} [1, 3_b, 3_a],$

que invierte el orden relativo de $3_a$ y $3_b$. $\blacksquare$

Solucion

(a) Particionamiento de Lomuto

Partimos de $A = [15, 3, 9, 8, 5, 2, 7, 1, 6]$ (indices $0$ a $8$). Con la particion de Lomuto el pivote es el ultimo elemento, $A[8] = 6$. Usamos dos indices:

• $i$ = frontera de los elementos $\leq$ pivote (empieza en $lo - 1 = -1$).
• $j$ = elemento que estamos examinando (recorre de $lo$ a $hi - 1$).

La regla es: si $A[j] \leq pivote$, avanzamos $i$ e intercambiamos $A[i] \leftrightarrow A[j]$.

$j$	$A[j]$	$A[j] \leq 6$?	Accion	Arreglo tras el paso
0	15	No	$j$ avanza	[15, 3, 9, 8, 5, 2, 7, 1, 6]
1	3	Si	$i=0$, swap $A[0]\leftrightarrow A[1]$	[3, 15, 9, 8, 5, 2, 7, 1, 6]
2	9	No	$j$ avanza	[3, 15, 9, 8, 5, 2, 7, 1, 6]
3	8	No	$j$ avanza	[3, 15, 9, 8, 5, 2, 7, 1, 6]
4	5	Si	$i=1$, swap $A[1]\leftrightarrow A[4]$	[3, 5, 9, 8, 15, 2, 7, 1, 6]
5	2	Si	$i=2$, swap $A[2]\leftrightarrow A[5]$	[3, 5, 2, 8, 15, 9, 7, 1, 6]
6	7	No	$j$ avanza	[3, 5, 2, 8, 15, 9, 7, 1, 6]
7	1	Si	$i=3$, swap $A[3]\leftrightarrow A[7]$	[3, 5, 2, 1, 15, 9, 7, 8, 6]

Al terminar el bucle colocamos el pivote en su lugar intercambiando $A[i+1] \leftrightarrow A[hi]$, es decir $A[4] \leftrightarrow A[8]$:

$A = [3, 5, 2, 1, \mathbf{6}, 9, 7, 8, 15]$

En esta primera particion se hicieron 8 comparaciones y 5 intercambios.

La visualizacion siguiente ejecuta la traza completa (no solo la primera particion, sino todas las llamadas recursivas hasta ordenar el arreglo). Usa los controles para avanzar paso a paso: el morado es el pivote, el ambar el elemento comparado, el rojo un intercambio y el verde los elementos ya ubicados en su posicion definitiva.

(b) Resultado de la particion

Tras la primera particion el pivote $6$ queda en el indice 4, que es su posicion definitiva en el arreglo ordenado:

• Subarreglo izquierdo (elementos $\leq 6$): $[3, 5, 2, 1]$ en los indices $0..3$.
• Pivote: $6$ en el indice $4$.
• Subarreglo derecho (elementos $> 6$): $[9, 7, 8, 15]$ en los indices $5..8$.

Quick Sort continua recursivamente sobre los subarreglos izquierdo y derecho, que son independientes. El arreglo final ordenado es:

$[1, 2, 3, 5, 6, 7, 8, 9, 15]$

(c) Peor caso: arreglo ya ordenado

Para $B = [1, 2, 3, 4, 5, 6, 7, 8, 9]$ con pivote = ultimo elemento, el pivote es siempre el maximo del subarreglo. Entonces en cada particion todos los elementos cumplen $A[j] \leq pivote$: el indice $i$ avanza en cada paso con $i = j$ (no hay intercambios reales) y el pivote termina en su propia posicion final. La particion produce:

• un subarreglo izquierdo de tamano $n - 1$ (todo menos el pivote), y
• un subarreglo derecho vacio.

El tamano solo disminuye en $1$ por nivel, generando una recursion de profundidad $n$:

$T(n) = T(n-1) + (n-1), \qquad T(1) = 0$

El numero total de comparaciones es:

$(n-1) + (n-2) + \cdots + 1 + 0 = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}$

Para $n = 9$: $8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = \mathbf{36}$ comparaciones. Como $\frac{n(n-1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n = \Theta(n^2)$, la complejidad en este caso es $O(n^2)$. Ironicamente, un arreglo ya ordenado es el peor caso para esta variante de Quick Sort.

(d) Como evitar el peor caso

1. Pivote aleatorio. Antes de particionar se elige un indice al azar en $[lo, hi]$ y se intercambia con $A[hi]$. Ningun patron fijo de entrada (como un arreglo ordenado) puede provocar el peor caso sistematicamente; el tiempo esperado pasa a ser $O(n \log n)$.
2. Mediana de tres. Se toma la mediana entre $A[lo]$, $A[\lfloor (lo+hi)/2 \rfloor]$ y $A[hi]$ como pivote. Sobre datos casi ordenados produce particiones mucho mas balanceadas y elimina el peor caso en la practica.

Complementos habituales: cambiar a Insertion Sort para subarreglos pequenos (menos overhead) y, para garantizar $O(n \log n)$ incluso en el peor caso, usar Introsort (Quick Sort que cae a Heap Sort cuando la profundidad de recursion supera $2 \log n$).

(e) Estabilidad

Quick Sort (Lomuto) NO es estable: puede alterar el orden relativo de elementos con clave igual.

Contraejemplo. Sea el arreglo de pares (ordenando por el primer componente) $[\,3_a,\ 3_b,\ 1\,]$, donde $3_a$ y $3_b$ tienen la misma clave $3$ pero $3_a$ aparece antes. Con pivote $= A[hi] = 1$: ningun elemento es $\leq 1$, asi que $i$ se queda en $-1$ y al final se intercambia $A[i+1] = A[0] \leftrightarrow A[2]$:

$[\,3_a,\ 3_b,\ 1\,] \;\longrightarrow\; [\,1,\ 3_b,\ 3_a\,]$

Ahora $3_b$ aparece antes que $3_a$: se invirtio el orden original de dos elementos iguales, por lo que la ordenacion no es estable.