ejemplo algoritmo quicksort para ordenación de vectores

[foxternoster]

Hola, he estado leyendo sobre el algoritmo quicksort para ordenar una serie de números, pero la verdad es que no acabo de comprender la mecánica en que se basa. Agradecería que alguien me pusiera un ejemplo numérico explicado paso a paso.

[Mastermind]

Hola Foxternoster, hay distintas variantes del algoritmo quicksort. Quizás la más clásica es la que se basa en dado un vector como (3, 1, 9, 2, 6, 12, 5) tomar el primer elemento del vector como pivote. Ese primer elemento se deja "aparcado" hasta el instante final del proceso.

Ahora se comienza a recorrer los elementos desde el principio hacia el final (i=2 hasta i=n) hasta encontrar uno mayor que el pivote. Una vez terminado esto, en este caso nos encontraremos sobre el número 9 (i=3), y pasamos a recorrer los elementos desde el final hacia el principio (j=7 hasta j=1) hasta encontrar uno menor que el pivote. En nuestro caso el mismo 5 es mayor que el pivote, por lo que nos detenemos en j=7. Ahora intercambiamos los números en que nos hemos detenido, es decir, el vector queda:

(3, 1, 5, 2, 6, 12, 9)

¿Qué estamos haciendo? Lo más grande que el pivote lo vamos "echando" hacia la derecha y lo más pequeño hacia la izquierda. El pivote lo dejamos aparte de momento.

Ahora seguimos el recorrido desde los índices en que nos habíamos quedado, es decir, seguimos con i=3+1, i=4 y comprobamos si es más grande que el pivote, no lo es, pasamos al siguiente, y ahora con i=5 número 6 este sí es más grande que el pivote. Paramos aquí y nos pasamos al recorrido de las jotas. Chequeamos j=6 para ver si es menor que el pivote, pero no lo es. Seguimos j=5, j=4. En j=4 nos encontramos al 2, que sí es menor que el pivote. Ahora tenemos que tener en cuenta que se produce la circunstancia i > j ¿Qué significa esto? Que los dos índices se han cruzado y el elemento mayor ya está a la derecha del elemento menor, por tanto no tiene sentido realizar intercambio entre ellos. ¿Qué nos falta por hacer? Sabemos que a la derecha del índice j todos los números son mayores que el pivote. Lo que hacemos ahora es poner el pivote en la posición que nos indica j, con lo cual ya tenemos todos los números mayores a un lado y todos los números menores a otro.

(2, 1, 5, 3, 6, 12, 9)

Con esto ya tenemos el vector dividido: el pivote está en su posición definitiva, no tendremos que tocarlo más.

Hay un subvector izquierdo que es (2, 1, 5) y otro subvector derecho que es (6, 12, 9)

Esto es básicamente el mecanismo de quicksort. La idea es aplicarlo recursivamente cierto número de veces hasta tener vectores de tamaño pequeño y en ese momento proceder a la ordenación por otro método más directo como el de ordenación por inserción.

[foxternoster]

Este ejemplo veo que cuadra porque el 3 acaba colocándose como elemento central, pero ¿qué pasaría si en vez de un 3 tuviéramos un 0? O ya no cuadra, o tendríamos que coger otro pivote, o habría que hacer algo... ¿Cómo haríamos en este caso?

[Mastermind]

En este caso el 3 acaba colocándose como elemento central digamos que de casualidad. En realidad, el pivote puede terminar colocado en cualquier posición del vector, desde un extremo (izquierdo o derecho) hasta cualquier posición intermedia. En el caso que planteas: (0, 1, 5, 2, 6, 12, 9)

Tomamos el 0 de pivote y empezamos el recorrido de izquierda a derecha con i=2 hasta i=7 buscando un elemento mayor que el pivote. Nos paramos en i=2 porque ya el 1 es mayor que el cero. Comenzamos el recorrido de derecha a izquierda desde j=7 hasta j=1 buscando un elemento menor o igual que el pivote. Recorremos j=7, 6, 5, 4, 3, 2, 1 y llegamos al último elemento, es decir, al propio pivote. Esto nos indica que en el vector no hay ningún elemento menor que el pivote.

 
Ahora tenemos que tener en cuenta que se produce la circunstancia i > j ¿Qué significa esto? Que los dos índices se han cruzado y el elemento mayor ya está a la derecha del elemento menor, por tanto no tiene sentido realizar intercambio entre ellos. ¿Qué nos falta por hacer? Sabemos que a la derecha del índice j todos los números son mayores que el pivote. Lo que hacemos ahora es poner el pivote en la posición que nos indica j, con lo cual ya tenemos todos los números mayores a un lado y todos los números menores a otro. En este caso el pivote está en 1, y tendríamos que colocarlo en posición 1. Conclusión: el pivote se queda donde ya estaba y el vector resultante es:

(0, 1, 5, 2, 6, 12, 9)

Lo que tenemos como resultado es:

Subvector izquierdo: vacío
Pivote: cero
Subvector derecho: (1, 5, 2, 6, 12, 9)

Ahora tendríamos que repetir el proceso sobre los subvectores. Pero como el izquierdo está vacío, no podemos hacer nada sobre él.

En este caso comprobamos que el quicksort no ha logrado dividir al vector original en dos partes parecidas, sino que existe un desequilibrio con el subvector izquierdo vacío y el derecho casi igual al inicial. Esto lo que nos indica es que en determinados casos el quicksort no es eficiente.

[foxternoster]

¿El quicksort no es eficiente? He leído por ahí que es uno de los métodos más eficientes, pero no acabo de verlo claro.

[César Krall]

Hola, en relación a eficiencia caben distinguir varias cuestiones. En el caso de quicksort, se puede decir que "en el peor caso" no es un método eficiente. Sin embargo, para el caso "medio" es uno de los métodos más eficientes. Es decir, que si te dan un conjunto de vectores donde tengas 1000 vectores con números aleatorios y órdenes aleatorios, quicksort sí es eficiente en relación a otros métodos. Si te dan un vector concreto "el peor caso" puede que no sea tan eficiente como sería deseable.

[foxternoster]

La verdad es que no me aclaro 

[César Krall]

Voy a poner un ejemplo un poco bruto, pero que a lo mejor aclara algo. Supongamos que queremos demoler una construcción y nos planteamos qué método usar.

Supongamos que la construcción es un edificio de 4 plantas y nos planteamos usar explosivos. Ponemos varias cargas explosivas, volamos el edificio tomando las precauciones oportunas, y listo. Hemos sido eficientes.

Ahora supongamos que la construcción es una carpa que se monta como una tienda de campaña con unos clavos al suelo y vientos para sujección. El método de los explosivos, que es eficiente en determinados casos, ¿sería eficiente ahora? No, porque usar explosivos requiere tomar unas medidas de seguridad, requiere de especialistas en explosivos, tiene un alto coste conseguir el explosivo, etc. Entonces, ¿cómo haríamos con la carpa? Pues simplemente desclavamos los clavos e iríamos quitando poco a poco la cubierta, los hierros, etc. En este caso es más eficiente el "desmontaje manual".

Ahora finalmente nos planteamos, para el caso peor --> mejor explosivos, para el caso mejor --> mejor desmontaje manual. ¿Y para el caso medio? El caso medio serían edificaciones de 1 o 2 plantas. Este caso medio se resuelve de forma eficiente usando una máquina autopropulsada tipo pala de construcción con algún utensilio específico para demolición.

Con el quicksort lo que decimos es que es eficiente para el caso medio. El peor caso para el quicksort sería el de vector prácticamente ordenado.

[foxternoster]

ok césar creo que esto ha aclarado bastante. Hay otra cosa que no veo clara, se dice "La idea es aplicarlo recursivamente cierto número de veces hasta tener vectores de tamaño pequeño y en ese momento proceder a la ordenación por otro método más directo como el de ordenación por inserción."

Si estoy usando un método lo lógico es quedarme con ese método hasta el final, ¿para qué cambiar cuando quedan pocos números?

[Alex Rodríguez]

Hola foxternoster, te indico por dónde creo yo que van los tiros. En el ejemplo que ha puesto César ha dicho algo así como que "según la naturaleza del problema, por ejemplo derribar un edificio o derribar una carpa, puede ser más eficiente un método u otro".

Yo veo que este ejemplo es bastante bueno y nos sigue sirviendo para lo que ahora planteas: imagínate que usas cargas explosivas para demoler un edificio (sería aplicar quicksort a una ordenación). Una vez aplicas las cargas explosivas, el edificio "cae", sin embargo, no cae completamente, quedan algunos pilares a medio derruir y quizás algunas paredes en la primera planta sin derruir. ¿Qué aplicaríamos ahora? ¿Cargas explosivas otra vez? No, porque usar cargas explosivas resulta muy caro y costoso. Una vez tenemos el edificio reducido a algunas paredes y pilares, procederíamos con el caso de uso de una máquina autopropulsada que es un término medio.

Con el quicksort, sería similar, primero lo aplicamos y reducimos el problema a algo muy manejable (el edificio demolido al que solo le quedan algunos pilares y paredes). Luego aplicamos un método eficiente para este tipo de problemas, en este caso el método de ordenación por inserción (que sería la máquina autopropulsada en el caso de la demolición de edificios).

Saludos.

[César Krall]

Gracias por el apunte Alex, como siempre...

[foxternoster]

Gracias a todos, las explicaciones han sido fenomenales, quizá me quede alguna duda pero estoy avanzando gracias