Me está costando entender la clasificación rápida, la mayoría de las demostraciones y explicaciones omiten lo que realmente sucede (http://me.dt.in.th/page/Quicksort/ por ejemplo).

Wikipedia dice:

Elija un elemento, llamado pivote, de la matriz. Particionamiento: reordene la matriz para que todos los elementos con valores menores que el pivote lleguen antes del pivote, mientras que todos los elementos con valores mayores que el pivote van después (los valores iguales pueden ir en cualquier dirección). Después de esta partición, el pivote está en su posición final. Esto se llama la operación de partición. Aplique recursivamente los pasos anteriores a la submatriz de elementos con valores más pequeños y separadamente a la submatriz de elementos con valores más grandes.

¿Cómo funcionaría eso con una matriz de 9,1,7,8,8, por ejemplo, con 7 como pivote? El 9 necesita moverse a la derecha del pivote, parece que todas las implementaciones de ordenación rápida están en funcionamiento, por lo que no podemos agregarlo después del 8,8, por lo que la única opción es intercambiar el 9 con el 7.

Ahora la matriz es 7,1,9,8,8. La idea detrás de quicksort es que ahora tenemos que ordenar recursivamente las partes a la izquierda y derecha del pivote. El pivote está ahora en la posición 0 de la matriz, lo que significa que no hay parte izquierda, por lo que solo podemos ordenar la parte derecha. Esto no sirve de nada como 7> 1, por lo que el pivote terminó en el lugar equivocado.

En esta imagen, 4 es el pivote, entonces ¿por qué 5 va casi a la izquierda? ¡Es más grande que 4! Después de mucho intercambio, termina siendo ordenado, pero no entiendo cómo sucedió eso.