¿Porque no?
Si en Quicksort se usara la comparacion “<=”, para los datos de antes de la posicion de pivote, y “<” para los datos de despues del pivote, el algoritmos sería estable, y posiblemente mejoraría su rendimiento en situaciones de repetición de claves.
EDIT: La respuesta dos post más adelante “Ejemplo superadaptativo”, el quicksort estable pierde rendimiento.
May 18th, 2007 at 23:17
Ya que tienes semejante vicio con el quicksort, igual te ayuda el estudiarlo desde un punto de vista funcional.
quicksort [] = []
quicksort (s:xs) = quicksort [x|x = s]
http://en.wikipedia.org/wiki/Haskell_(programming_language)
byee
May 25th, 2007 at 19:27
Perdón por el retraso al publicar tu comentario… tenía un modo pelín talibán para aprobar comentarios.
Sobre lo que comentas; lo poco que he leído sobre Haskell me ha encantado, pero también parece ser que es un poco “engorroso”. El concepto de “lazy evaluation” me encanta.
Lo que no veo es que más me puede aportar ese enfoque (funcional), siempre que haya entendido lo que hace quicksort.
Otro día que nos crucemos por los pasillos te explico con más tiempo las cosas a las que les estoy dando vueltas (no tienen “mucho” que ver con Quicksort… o en realidad sí, pero bueno.
De hecho Quicksort es un algoritmo “inversamente adaptativo” o algo así, funciona mejor cuanto más desordenado esta el vector a ordenar.
A lo que yo le estoy dando vueltas ahora mismo es más bien a algo parecido al Smoothshort http://en.wikipedia.org/wiki/Heapsort
. Que grande fué Dijkstra.
Algo que si que me podría ayudar es un heapsort en haskell.