Algoritmos de Ordenamiento - UNLaM

La complejidad del peor caso del Quick sort es O(n^2).
El fusion cual es? falta uno que se llama ordenamiento por monticulos o HeapSort, que tiene O(n log n) en el peor caso. Pero no se si ese lo estudiaron.
Suerte

gracias shirley por la tabla,
otra cosa, cuando vean algo de coloreo de grafos me pasas un pequeño resumen? (si no es molestia claro) saludos

muy bueno shirley... a ver si te vemos mas seguido x aca

leomalevo... busco lo q tengo de teoria de grafos en general y subo... ya vi otro pedido x ahi perdido en el tiempo

saluT

Eso es cierto, pero no según quicksort como se ve en la universidad de la matanza (palabras de mi profesora)... yo tenia n^2 y cuando me lo corrigio, ella me dijo que no iba por esa razon... (Supongo q la implementacion según como la explicaron ellos -q no es mediana de tres ni la de ninguno de los autores- da siempre n ln n?)
Eso si: tenemos un ejercicio en la guia practica que pregunta por qué puede tardar quicksort lo mismo que seleccion y cómo solucionar el tema.
(al que contesté: tarda lo mismo si estamos en el peor caso y para solucionar se aplica quicksort con mediana)

btw: Fusion, es Mergesort... y a heapsort no lo dan en matanza...

sab

es que no lo quiero opacar al doc

(FFFFFFFFAAAAAAAAAAAAAA) lo primero que hago cuando tengo una duda de programacion es preguntarle...

Igual, no dejen de agarrar el libro de algoritmos de Aho-Ullmann.... leo, ese libro está en biblioteca y ahí tenés casi todo lo que entra en el programa de programación 3...


El doc

coincido, saque mucha info de ahi para armar la tabla y para otras cosas tambien

Buenisimo por la tabla, ami tambien me interesa lo de grafos.

En el libro de Cormen, esta la demostracion de un algoritmo Quicksort que es de complejidad O(n log n)
en todos los casos. Este algoritmo no es muy comun debido a que usa un par de algoritmos para calcular el pseudo-mediano y pivotear en tres partes. Realmente no recuerdo si valia la pena utilizarlo ya que hay que considerar las constantes ocultas que pueden dar un resultado negativo para tamaños de entrada muy grandes, pero bue... el que lo quiera usar ahi esta =).

El quicksort clasico da O(n^2) si el arreglo esta ordenado de menor a mayor o viceversa, o si todos los elementos del arreglo son iguales... estos casos son poco probables cuando uno hace un ordenamiento y ademas, se suma la muy buena eficiencia en cuanto a constantes ocultas. Por esto es un algoritmo muy usado y simple de entender.

Saludos