Monday, January 09, 2006

Metodo quict sort

QUICKSORT
- Este Algoritmo es inestable ya que si se pueden producir intercambios de claves con datos iguales, es posible que se altere el orden relativo inicial del arreglo a ser ordenado.
- Este Algoritmo no requiere memoria adicional, ya que los subarreglos son ordenados In Situ.
-También apreciamos que funciona en base a comparaciones en los WHILEs dentro de PARTITION, ahí compara varias veces.
- El caso promedio La complejidad para dividir una lista de n es O(n). De cada sublista se crean 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(2) = 2 + 2*f(1)
…..
Así llegamos a la recursividad:
f(n) = n + 2*f(n/2)
Y esto significa una complejidad de O( ).
- El Peor Caso de este Algoritmo es cuando la lista está ordenada (curiosamente) porque en cada llamada recursiva el arreglo es dividido en una parte que contiene todos los elementos del arreglo menos el pivote (que vendría siendo el mayor o el menor de la lista) y otra vacía. En este caso la complejidad del algoritmo es O( ).
- En el mejor caso el pivote es siempre la media de todos los elementos, de esta forma el arreglo se divide en dos partes equilibradas siendo la complejidad del algoritmo O( ).

No comments: