**QUICKSORT**
Qu es?
En que consiste?
Analisis
Implementacin en c
Expresin de recurrencia
Mtodo iterativo
rbol de recurrencia
Mtodo maestro
Qu es?
Es unalgoritmo creado por el cientfico britnico en
computacinC. A. R. Hoare.
Esta basado en la tcnica dedivide y vencers.
Permite, en promedio,ordenarnelementos en un tiempo
proporcional anlogn en el mejor de los casos y n^2 en el
peor de los casos.
En que consiste?
Consiste en ordenar un arreglo de forma ascendente de
la siguiente manera:
1.
Elegir un elemento de la lista de elementos a ordenar, al
que llamaremospivote.
2.
Acomodar los elementos del arreglo a cada lado del pivote,
de manera que del lado izquierdo queden todos los
menores al pivote y del lado derecho los mayores al pivote
3.
Colocar el pivote en su lugar, el arreglo queda separado en
dos subarreglos.
4.
Repetir este proceso de forma recursiva para cada
subarreglo mientras estos contengan mas de un elemento.
Una vez terminado este proceso todos los elementos
estarn ordenados.
Eleccin del pivote
1.
El pivote ser el primer elemento del arreglo
2.
El pivote ser el elemento que esta a la mitad del
arreglo
3.
Que el pivote se elija de entre tres elementos del
arreglo(cualesquiera), los cuales debe comparar para
seleccionar el valor intermedio de los tres y considerarlo
como el pivote.
PSEUDOCDIGO
funcin quickSort (RegistroT *a, entero p, entero r)
comienza
si p < r entonces
q particionar (a, p, r)
quickSort (a, p, q1)
quickSort (a, q+1, r)
fin si
fin
Particionar(*a,p,r)
X a[r]
ip-1
for jp to r-1
do if a[j]<= x
then ii+1
a[i]a[j]
a[i+1]a[r]
return i+1
Anlisis
Como se puede suponer, la eficiencia del algoritmo depende de
la posicin en la que termine el pivote elegido.
En el mejor caso, el pivote termina en el centro de la lista.
En este caso, el orden de complejidad del algoritmo
esO(nlog n).
En el peor caso, el pivote termina en un extremo de la lista.
El orden de complejidad del algoritmo es entonces
deO(n). El peor caso depender de la implementacin del
algoritmo, aunque habitualmente ocurre en listas que se
encuentran ordenadas, o casi ordenadas.
En el caso promedio, el orden esO(nlog n).
Rendimiento del QuickSort
Depende de si la particin est o no balanceada
Depende de qu elemento se utilizo para particionar.
Particin balanceada
Rpido como MergeSort
Particin no balanceada
Lento como InsertionSort
Rendimiento del QuickSort...(2)
Peor caso en particin(entrada previamente ordenada)
Una region con n-1 elementos y otra con 1 elemento
Asume que esto sucede en cada paso del algoritmo
Costo de particionar O(n), T(1)=O(1).
Recurrencia T(n)=T(n-1)+O(n).
O(
Mejor caso en particin
Regiones de tamao n/2
Recurrencia T(n)=2T(n/2)+O(n)
Particionamento balanceado
Caso promedio mas cerca del mejor caso que del peor
Suponiendo un split en proporcin 9-1parece muy
desbalanceado
Recurrencia T(n)=T(9n/10)+T(n/10)+n
Ventajas:
Muy rpido
No requiere memoria adicional.
Desventajas:
Implementacin un poco ms complicada.
Recursividad (utiliza muchos recursos).
Mucha diferencia entre el peor y el mejor caso.
Implementacin en c
Expresin de recurrencia
Mtodo iterativo
T(1)=1
T(n)=2T(n/2)+n
2. T(n)= 2T(n/2)+n
T(n/2)= 2T(n/4)+n/2
T(n/4)= 2T(n/8)+n/4
T(n/8)= 2T(n/16)+n/8
3. T(n)= n+2(n/2+2(n/4+2(n/8+2T(n/16))))
= n+2*n/2+2*2*n/4+2*2*2*n/8+2*2*2*2T(n/16)
4.
5.
trmino inductivo trmino base
6.
7.
Mtodo maestro
T(1)=1
T(n)=2T(n/2)+n
a=2
b=2
c=1
k=1
rbol de recurrencia
