Quicksort: Algoritmo de ordenamiento rápido

Software
Etiquetas:
3 Flares Twitter 0 Facebook 2 Google+ 1 Pin It Share 0 Email -- 3 Flares ×

Uno de los problemas más frecuentes con los que se enfrentan los diseñadores de software es la ordenación de una lista de elementos. Ya sea que estés lidiando con una base de datos de direcciones Web, una lista de clientes o el listín telefónico de tu ciudad, seguramente necesitarás ordenarlos de alguna forma para que esos datos te sean útiles. Quicksort es el algoritmo de ordenamiento más rápido del mundo, y hoy te contamos como funciona.

¿Como harías para ordenar una lista de números elegidos al azar? Esta pregunta se la han hecho los estudiantes de todas las carreras relacionadas con la informática desde la época de las cavernas. Es un problema con el que te encuentras casi a diario, cuya resolución eficaz dista mucho de ser trivial. Pensemos un poco. Imaginemos que tenemos una caja muy larga, dividida en 100 compartimientos numerados del 1 al 100, conteniendo cada uno de ellos un papel con un número diferente anotado en él. Los papeles se encuentran distribuidos aleatoriamente, y nuestra tarea consiste en ordenarlos. Una forma simple de hacerlo consiste en utilizar una segunda caja, idéntica a la primera pero vacía. Si recorremos cien veces la caja inicial y en cada pasada nos quedamos con el número más grande que encontremos y lo pasamos al primer casillero libre de la segunda, habremos resuelto el problema. Efectivamente, luego de las cien pasadas tendremos la primer caja vacía y la segunda llena, con los números ordenados de mayor a menor en sus divisiones internas. Este sistema, a pesar de lo rudimentario y sencillo que parece, funciona perfectamente. Sin embargo, es espantosamente lento y consume una cantidad inaceptable de recursos.

Quicksort: Algoritmo de ordenamiento rápido

Si se aplica como parte de un programa informático, el método explicado anteriormente necesita el doble de la memoria requerida para almacenar los números a ordenar, ya que hay que emplear una zona de memoria igual de grande a la que contiene el arreglo original como “destino” para los números que vamos ordenado. El tiempo implicado en la resolución del problema aumenta directamente con el numero de elementos que contenga la lista. Estos dos inconvenientes no son importantes en listas pequeñas, pero se vuelven muy importantes cuando la lista contiene miles de millones de elementos. Si tenemos en cuenta que a finales del siglo pasado un estudio demostró que más de la mitad del total del tiempo de cómputo utilizado por todos los ordenadores del mundo se empleaba en “ordenar cosas” (no es casualidad que a nuestros computadores los llamemos “ordenadores”), nos damos cuenta de la importancia que tiene disponer de un algoritmo que resuelva estas cuestiones de forma eficiente. El explicado anteriormente no es en absoluto eficaz, pero afortunadamente existen otros mucho más inteligentes. El más famoso de ellos quizás sea el denominado Quicksort.

Quicksort: Algoritmo de ordenamiento rápido

Este algoritmo fue propuesto por Sir Charles Antony Richard Hoare en 1960. Hoare no sólo encontró una forma muy ingeniosa para ordenar elementos, sino que además logró una demostración matemática que prueba que este sistema es en realidad el más rápido posible, por lo que desde hace más de 50 años la discusión de que pasos conviene seguir para ordenar una lista ha dejado de tener sentido. La respuesta es siempre la misma: Quicksort. Antes de ver como hace su magia este algoritmo, tenemos que comprender un concepto -muy utilizado por los informáticos- llamado recursividad. La recursividad es la es la forma en la cual se especifica un proceso basado en su propia definición.  Para ponerlo más claro podemos ver un ejemplo:  “la suma de los números de 1 a n es igual a la suma de 1 a (n-1) + n” En la frase anterior existe la recursividad. Se nos dice que para sumar una serie de números, basta con sumar el último de la lista a la suma de todos los anteriores. Obviamente, para obtener esa suma parcial puede aplicarse el mismo procedimiento, una y otra vez, hasta llegar a una lista que solo contiene el “1”. La posibilidad de definir la solución de un problema recurriendo a la propia definición se llama recursividad. Es sumamente útil, aunque debe prestarse mucha atención para evitar que un pequeño error de programación nos atrape en un bucle infinito. Comprendido esto, veamos como funciona Quicksort.

Quicksort: Algoritmo de ordenamiento rápido

El secreto de Quicksort consiste en dividir la lista original en dos listas más pequeñas. Para ello, se elige un elemento cualquiera (aunque en general se suele utilizar el que se encuentra en medio de la lista) que nos servirá como pivote. Luego se recorre toda la lista, con el objeto de colocar los elementos más pequeños que el pivote a la izquierda del mismo, y los mayores a la derecha. Las implementaciones más eficientes realizan esta tarea a la vez, recorriendo simultáneamente la lista en ambas direcciones e intercambiando entre sí cada par de elementos “descolocados” que se encuentran a su paso. Culminada esta etapa tenemos un grupo de elementos menores que el pivote, el pivote, y otro grupo compuesto por números mayores a él. En este punto es donde juega un papel importante la recursividad: si cada uno de esos grupos vuelve a dividirse en dos y se aplica lo explicado anteriormente de forma recursiva, tenemos resuelto el problema. Lo mejor de todo es que el tamaño de las sublistas -y por ende el tiempo que se necesita para procesarlas- es cada vez menor.  En cada nivel el tamaño de las sublistas la mitad del anterior, lo que permite ordenar una lista de 1024 elementos en 10 “pasadas”, y una de más de un millón en solo 20. Y lo mejor de todo es que no requiere de una “segunda caja vacía” sobre la que ordenar los elementos, con lo que el consumo de recursos (memoria) es menor.

Otra innegable ventaja del algoritmo Quicksort es que puede ser paralelizado. ¿Que significa esto? Que en ordenadores con más de un microprocesador -algo muy común en los superordenadores que, justamente, son los que suelen realizar procesos como estos con cantidades enormes de elementos- el problema puede dividirse en muchas partes pequeñas y cada una ser resuelta por una CPU diferente. Esta característica también es importante cuando el numero de elementos es tan grande que no pueden mantenerse todos en la memoria RAM del ordenador encargado de ordenarlos. En ese caso, Quicksort permite ir guardando en un subsistema de almacenamiento externo cada porción ordenada, y al final juntar todo para tener la lista completa. Por supuesto, no todo son rosas: este algoritmo es fuertemente dependiente de la “suerte” que hayamos tenido al elegir el elemento pivote. Si somos tan burros como para elegir un elemento que se encuentre en uno de los extremos de la lista, habremos dividido el problema en dos partes muy dispares (una con solo un elemento, ya ordenada, y otra casi del mismo tamaño que la original, desordenada) y el algoritmo no será tan eficiente. Este problema puede minimizarse mediante diferentes estrategias, como el primer elemento, el último y el central, y hallar el promedio entre los tres (suponiendo que sean números). Otro enfoque es, antes de cada pasada, recorrer toda la lista de valores buscando el mejor valor posible para el pivote. Esto es óptimo, pero en listas largas costoso en términos de tiempo. A pesar de este costado flaco, Quicksort es uno de los algoritmos más estudiados y optimizados del mundo de la informática. ¿Lo conocías?


  • Variant

    Ya lo sabía. Pero debo reconocer que este artículo es muy ilustrativo.
    Bien por el autor.

    ¡Que burbuja lenta entre otros métodos!

    • stick

      #1 recien estoy empesando mi carrera de informatica y necesito sabes los metodos de ordenamiento de datos en consola.ok le agradeceria un monton XD thx. stephen_125@hotmail.com

    • dddd

      #1 jtttttttttttttttttttttttttttttttttttttt gññ h g

  • Infer

    No lo conocía, muy buena técnica y me puede servir para algunos desarrollos. ;)

  • playdramon

    Curioso que este tipo de reportajes lleguen en momento justo, hace años que dejé ver ordenamiento y las estructuras de datos y ahora en clase de IA hay que desempolvar eso, cosa que realmente me da mucha flojera (nada que ver con el mundo fantástico de Asimov).
    En resumen, gracias por el artículo.

  • djeeld

    Excelente artículo, asi explicado con manzanitas para los que no controlabamos bien el algoritmo…

    Les cuento, en los demos del JDK 1.6 de Java viene una demos de un Applet con 3 algoritmos de ordenamiento, el Burbuja, el Doble Burbuja (un poco mas rapido) y el Quick Sort, explicaditos con lineas desornadas (color negro) y se ordenan al darles click (con lineas de color) y allí tambien se ve con bastante ilustración lo que nos comenta este gran artículo de NeoTeo.

    Saludos.

  • ac

    "Quicksort es el algoritmo de ordenamiento más rápido del mundo".

    Ejem, no exactamente. Es cierto que es uno de los algoritmos mas rápidos como promedio, pero en el peor caso se comporta como o (n^2). Si se necesita garantía de que corra en o(n log n), el heapsort es una mejor opción.

    • Puntopeek

      Pero HeapSort, de todos los algoritmos nlogn es la peor opción… Si queremos que corra en O(nlogn) sería mejor aún MergeSort ;)

  • ltadam

    Este algoritmo esta muy padre, agraciadamente o desgraciadamente ya viene implementado en casi todos los lenguajes.. creo q en C no jejejeje. Es muy buen ejercicio de recursividad deberian hacerlo para practicar ^^
    Buen articulo..

    PD: Aunque la burbuja es un algorimo casi nato en todos jejejej se descubre por si solo :p lastima q sea el mas lento

  • Mish

    Aaa si Padrisimo…!!!!!…m nknta Buen Articulo…siempre hay cosas nuevas x aprender y otras muchas x recordar…

  • Rober2D2

    Que recuerdos. Como cultura general, o para aprender está bien (yo mismo hice uno en C hace tiempo). Afortunadamente, algunos lenguajes como Java (y supongo que muchos otros) ya vienen con funciones que ejecutan el algoritmo, así que no hay que molestarse en implementarlo

  • Genaro

    uff… ojala lo hubieran puesto 3 años antes, cuando lo necesitaba, pero esta muy bueno para recordar, estos posts donde uno aprende algo son los mejores de neoteo :)

    Saludos

  • jakala

    en C existia la funcion qsort, que implementaba este algoritmo. Interesante volver a oir hablar de estos temas :D

  • DeepRed82

    Este algoritmo es igual a la estrategia seguida para el juego de averiguar un numero del 1 a X, que vas dividiendo por la mitad por eliminacion hasta encontrar el numero, solo que en este caso guardas todos los resultados y combinaciones.

  • camilo_m22

    Me recuerda los tiempo de analisis de algoritmos…

  • liberar iphone

    no conocia el dato, buen articulo e interesante. gracias

  • ucuz otel

    en C existia la funcion qsort, que implementaba este algoritmo. Interesante volver a oir hablar de estos temas

  • xyz765

    quick sort es increiblemente dificil de entender en codigo es por eso que sea poco popular, ademas debes conocer la naturaleza de los datos para seleccionar un buen pivote. Deberian hacer una entrada sobre la hast table es un buen sistema de ordenamiento.

  • Luis

    Interesante. . .

  • Chuck Norris

    laguien podria explicar incluso mejor esto ?
    1 a (n-1) + n porque yo no he captado que importancia tiene
    porfavor

  • igrios

    En ciencias de la computacion es fundamental el Quicksort y sobre todo el concepto de recursividad es para mi un bello artilugio cuando es bien usado….

  • Demian

    Muy bueno la nota !! Me gusto el video tambien. Este algoritmo lo vi en la facultad hace años, me alegro que lo pusieran en neoteo, porque si bien es algo bastante especifico la idea se entiende perfectamente y asombra al pensarlo un ratito.

  • ZeK005

    Excelente nota

  • kyo3556

    Primero que nada en Java no existe una funcion que lo implemente solo. Podra haber herramientas en los IDEs de desarrollo para tal efecto, pero, no.
    Son 4 metodos de ordenamiento principales, claro que hay más, en el libro de Deitel, "Como programar en Java", se explican el buble, el quicksort, otro que no recuerdo el nombre y otro conocido como hash o algo asi, este último supuestamente era mas rapido que los otros tres, pero era mas complicado de entender, en programación se conoce esto como estructura de datos

  • Dixcroix

    xDDD
    Quicksort dudo que sea mas rapido, como decian mas arriba Heap Sort es de O(nlogn). Ademas, la pila de recursion…. fatal xDDDD
    Temporalmente es bueno en el mejor caso, pero espacialmente… considerando que es una funcion recursiva….
    =D

  • dix

    Apoyando al compañero ‘ac’, el rendimiento temporal dependera exclusivamente de que pivote se elija. En cuanto a costo espacial… ni hablar de la pila de recursion con este metodo xDDDDD

  • Puntopeek

    Solo añadir que en la práctica se usa QuickSort hasta obtener subarreglos de un tamaño fijo mucho menor (una longitud que ha traído buenos resultados es 20). Entonces se aplica Ordenación por Inserción a estos subarreglos, que es bastante eficiente cuando el arreglo está casi ordenado y hay pocas inversiones.

  • warlien

    ta de la ptm!!…