[ALGORITMO] Algoritmo de quicksort

te movi el tema a donde corresponde

a ver con esto

http://72.14.207.104/search?q=cache:...r&ct=clnk&cd=7

y tb te dejo la version en pdf x las dudas http://www.austral.edu.ar/web/ingenieria/ayed/clase08.pdf.


saluT

gracias Hi Matt por tu respuesta.

No puedo bajar el pdf, me parece que el link esta roto.

Otra cosa, no tenes algun link a alguna página que tenga problemas como este( y con respuestas si es posible):" tengo una máquina que ordena 1000 elementos en tanto segundos, cuantos elementos ordenaría en el triple de tiempo si sabemos que el algoritmo de ordenación fue el de selección". Ando buscando de este tipo de problemas en la web pero no encuentro(o no se buscar).

muchas gracias

perdón pero esto me resulta conocido... Programación 3 en el curso de verano de matanza???

Flojo lo mío por no recordar del todo bien esos ejercicios... Ya le tiro un PM a mi novia para q te de una mano, que justamente está haciendo el curso y tiene estos temas muchísimo más frescos que yo...

Pero la mano venía despejando las ecuaciones de O(t), que es un c.f(t) para obtener el c usando los valores conocidos (1t como tiempo y 1000 elementos como resultado), y después usar ese c obtenido junto con 3t para volver a plantear la ecuación y obtener los elementos ordenados en 3t...

La pregunta fue porque todo esto suena muy "dejean"...


El doc

ahi me llamo el doc

con el tema de quicksort con mediana de 3 lo q yo tengo anotado es:

tengo este vector
5 3 7 20 1 27 6 0 14

agarras el vector, y tomas los valores del principio, de la mitad y del final.

5 1 14

despues los ordenas de menor a mayor y los volves a ubicar en el vector que te queda. el valor que te quedo en el medio va a ser el pivot

1 3 7 20 5 27 6 0 14

ahora intercambias el valor que te quedo en el medio con el anteultimo (aca la prof pregunto si estaban ordenados, pero esa parte no la llegue a copiar)

1 3 7 20 0 27 6 5 14

y despues lo volves a intercambiar con el ultimo para que el pivot te quede en la ultima posicion, y proceder a quicksort normalmente

te quedaria:
1 3 7 20 0 27 6 14 5

despues posteo como se hacia el quicksort basico...

coloreo de grafos tengo un pseudocodigo pero ahora q lo lei, no se explica muy bien, otra cosa q me queda pendiente para postear.

y los problemas de complejidad suelen ser como el q pusiste vos, si vas a matanza todos los q podria tomar estan en la guia practica...

si tengo un vector de 1000 elementos y lo ordeno con shell en 5 segundos, cuanto tardo en ordenar el doble de elementos?

bueno como te dijo el doc tenemos que T(n) = c * f(n)
donde T(n) es el tiempo que tarda en hacer determinada operacion con n elementos
c es una constante cualquiera
y f(n) lo podes tomar como la complejidad del algoritmo con esos n elementos.

entonces tenes que 5 segundos = c * (1000)^(3/2) (1000 a la 3/2 que es la complejidad de shell)
de aca despejamos c = 5/(1000)^(3/2)
y con ese valor volvemos a hacer la cuenta, ahora tenemos c y f(n), nuestra incognita es t(n) = (5/(1000)^(3/2)) * (2000)^(3/2)

cualquier cosa sigo... yo creo q este jueves recupero el primer parcial

saludos

sab

gracias doc y shirley por las respuestas.

Viendo que son de la misma universidad y que conocen a la maquina "compiladora" dejean, procedo a hacerles estas consultas:

shirley con respescto al calculo de los tiempos, ¿como resolverias este problema? que lo tengo en la guia pero no se como resolverlo:

Problema 19: "Utilizando el algoritmo de quicksort se ordenó un vector de 1 millón de elementos en un tiempo T1. Cuántos elementos espera ordenar en el doble de tiempo?"

Mi mayor problema es tener que resolver algo con el algorimto de quicksort ya que tiene una complejidad de "n log n" y al momento de despejar la n hago cualquiera. Imaginate que me dice "El algoritmo de quicksort ordenó un vector de 10000 enteros en 5 seg ¿Cual sera el tamaño del vector que espera ordenar en 20 seg?", como joraca hago para resolverlo?, es mas que todo un problema matematico que de programación.

Y otra pregunta, el año pasado en el primer parcial me dejean me pregunto en el 1er parcial "Sabiendo que utilizo el algoritmo de quicsort, y que la entrada es aleatoria, ¿en cuantos pasos queda el mayor valor en su posicion definitiva? " Tenes idea de como es?

Desde de ya muchas gracias por sus tiempos, cualquier cosa que me quieran preguntar (tal vez la sepa) sobre prog 3 preguntenme ya que estoy estudiando para el final del 3/3.
saludos malevo

justamente le preguntamos eso a liliana (una de las profs.. bah yo digo liliana y sabes de quien hablo) y nos dijo:
T1 = c * 1000000 ln 1000000
con esto podemos afirmar que 2 T1 = 2 * c * 1000000 ln 1000000
y con eso hacemos que 2 T1 = c n ln n asi que te quedaria:
2 * c * 1000000 ln 1000000 = c * n ln n
las c se simplifican y entonces
2000000 ln 1000000 = n ln n
liliana nos dijo: dejenlo asi.

lo q me habia preguntado en un coloquio de ordenamiento era en cuantos pasos queda UN elemento en su posicion definitiva (no dijo nada de "el mayor"): contesté log n y me puso bien.
lo que tengo anotado que tambien te puede preguntar de quicksort: cuantas comparaciones hace, es 2 n log n (sedgewick)

pd: me saque 2 en el parcial (por el maldito algoritmo de correccion) asi que a recuperarlo y estudiar mas q antes

saludos,

sab

Te adjunto el algoritmo junto a un analisis completo, espero que te sirva

Passowrd: 2004
Fuente: Algoritmos y Complejidad: Notas de curso (Lic. en computacion - UNS) M. Falappa

te das cuenta que liliana sabes menos que un chico de jardín de infantes.

shirley, me quede pensando que es "el algoritmo de corrección", espero que no sea un algoritmo nuevo que hay que estudiar.

Saludos

AGUSTIN_RAMONE, gracias loco, ya lo baje y ahora me pongo a leerlo.

el algoritmo de corrección, es un algoritmo que dejean utiliza para ponerte la nota de un examen tomando como input las correcciones de los ejercicios... Es una mierda, ya que exige que tengas uno o 2 ejercicios bien (x lo gral el primero y el último)... sin esos ejercicios bien, es imposible aprobar dicho examen.

Es una reverenda cagada... Todos sufrimos a ese puto algoritmo.


El doc