QUICKSORT
El quicksort es probablemente la técnica de ordenación más rápida conocida hasta el momento. Fue desarrollada por C.A.R. Hoare en 1960.
La idea inicial fue hacer un algoritmo recursivo, pero dada su poca eficiencia actualmente se utilizan técnicas iterativas en la implementación de dicho algoritmo.
El quicksort funciona de la siguiente manera:
1. Eliges un elemento de una lista, llamado elemento de división..
2. Buscas la posición que le corresponde a ese elemento en la lista ordenada.
3. Vas poniendo los elementos menores de la lista a los lados del elemento de división de manera que a un lado quedan los menores y a otro lado los mayores.
(de esta manera se crean 2 sublistas divididas por el elemento de división)
4. Se aplica de forma recursiva este algoritmo a las 2 sublistas creadas mientras que tengan un largo mayor que 1.
Una vez terminado el proceso todos los elementos estarán ordenados.
Para optimizar el rendimiento del quicksort se podría elegir un elemento de división con un valor medio dentro de la lista. También se podría hacer una versión iterativa utilizando pilas para ir guardando los límites superior e inferior de cada sublista.
En cuanto a la estabilidad, el quicksort no es estable, el tiempo de ejecución de dicho algoritmo es variable, desde un tiempo promedio de ordenación de O(n log2n) hasta O(n2) con toda la lista ordenada ya que tiene que hacer subdivisiones de todos los elementos. (Pudiéndose este último caso evitar realizando algunas optimizaciones en el rendimiento.)
Finalmente hay que destacar del quicksort la rapidez de este algoritmo y que no requiere memoria adicional para ejecutarse y por el contrario tiene una implementación algo complicada, si se utiliza recursividad se utilizan muchos recursos y finalmente hay una gran diferencia en el tiempo utilizado entre el peor y el mejor caso, da una muy mala respuesta si la lista inicial está ordenada al revés o es una lista de constantes.
Pido perdón si hay algún error e intentaré corregirlo si dejáis un comentario rectificando.
Espero que os sea útil!
Solo un pequeño detalle que, imagino, será un simple lapsus:
Dices en el punto dos: “Buscas la posición que le corresponde a ese elemento en la lista ordenada.”
Evidentemente, no sabes qué posición tendrá en la lista ordenada hasta que los ordenes. Simplemente, al ir “apilando” los valores menores a un lado y los mayores a otro, el elemento “encuentra” su sitio.
Es decir que, en realidad, el paso 2 es el resultado inevitable de ejecutar el paso 3, y no su anterior.
Naturalmente, si fueras capaz de avieriguar a priori qué posición ocupará un elemento en el array final, la ordenación se simplificaría mucho: ¡Solo tendrías que repetir el paso 2 para cada uno de los elementos!
Muchas gracias por la puntualización!
necesito el programa de quicksort en VB por favor
Hola mi nombre es Carolina estoy en segundo de telematica.
Bueno el proyecto de fin de cutrimestre es pasar quicksort a un lenguaje funcional(Haskell). yo quisiera saber si me podian ayudar.
y me envian a mi correo algo de eso.
No tengo ni idea de lo que es Haskell, de todas maneras por la red hay muchísimas páginas donde podrás encontrar información acerca del Quicksort con pseudocódigo etc.
hola, bueno estoy estudiando licenciatura en computacion y me pidieron hacer el quicksort sin recursividad, tienes idea de como hacerlo?, te agradeceria mucho si me pudieses responder, la idea es que haga la misma funcion que el quicksort pero sacandole la recursividad, en c++
no sabia que en lcc habian locos tan flojos… hace la wea tu mismo… por lo menos date el tiempo pa buscarlo bien en internet y no que te lo haga otro… una verguenza…
El mejor algoritmo de ordenacion es el HeapShort, es nLog(n) puro, quickshort en el peor de los casos es cuadratico
holamepuedesayudar con un proyectoen lenguaje c trata sobreun sistemasefacturacion completocon ingresos eliminaciones recuperacion de datos y que trabaje con archivos