El verdadero trabajo del ordenamiento rápido ocurre durante el paso de dividir, que hace la partición del subarreglo array[p..r] alrededor de un pivote del subarreglo. Aunque podemos elegir cualquier elemento en el subarreglo como el pivote, es fácil de implementar hacer la partición si elegimos el elemento que está hasta la derecha del subarreglo, A[r], como el pivote.
Una vez elegido un pivote, hacemos la partición del subarreglo al pasar por él, de izquierda a derecha, al comparar cada elemento con el pivote. Mantenemos dos índices q y j en el subarreglo que lo divide en cuatro grupos. Usamos el nombre de variable q porque ese índice eventualmente apuntará a nuestro pivote. Usamos j porque es un nombre común de una variable de contador, y la variable será descartada una vez que terminemos.
  • Los elementos en array[p..q-1] son el "grupo C", que consiste de elementos que se sabe que son más chicos o iguales que el pivote.
  • Los elementos en array[q..j-1] son el "grupo G," que consiste de elementos que se sabe que son más grandes que el pivote.
  • Los elementos en array[j..r-1] son el "grupo D", que consiste de elementos cuya relación con el pivote es desconocida porque todavía no han sido comparados.
  • Por último, array[r] es el "grupo P", el pivote.
Inicialmente, tanto q como j son iguales a p. En cada paso, comparamos A[j], el elemento hasta la izquierda en el grupo D, con el pivote. Si A[j] es mayor que el pivote, entonces simplemente incrementamos j, de modo que la línea que divide los grupos C y D se corra una posición hacia al derecha:
A[j] mayor que el pivote
Si en cambio A[j] es menor o igual que el pivote, intercambiamos A[j] con A[q] (el elemento hasta la izquierda en el grupo G), incrementamos j, e incrementamos q, corriendo así la línea que divide a los grupos C y G, y la línea que divide a los grupos G y D una posición hacia la derecha:
A[j] mayor que el pivote
Una vez que lleguemos al pivote, el grupo D está vacío. Intercambiamos el pivote con el elemento hasta la izquierda en el grupo G: A[r] con A[q]. Este intercambio pone al pivote entre los grupos C y G, y hace lo correcto incluso si el grupo G o el grupo C está vacío. (Si el grupo C está vacío, entonces q nunca aumentó su valor inicial de p, así que el pivote se mueve a la posición hasta la izquierda en el subarreglo. Si el grupo G está vacío, entonces q se incrementó cada vez que j incrementó, así que cuando j alcance el índice r del pivote, q es igual a r, y el intercambio deja al pivote en la posición hasta la derecha del subarreglo). La función partition que implementa esta idea también regresa el índice q en donde terminó poniendo al pivote, de modo que la función quicksort, que la llama, sepa en dónde están las particiones. Aquí están los pasos de hacer la partición del subarreglo [12, 7, 14, 9, 10, 11] en array[4..9]:
Pasos para hacer la partición
Hacer la partición de un subarreglo con n elementos toma un tiempo Θ(n) \Theta(n) . Cada elemento A[j] se compara una vez con el pivote. A[j] puede o no intercambiarse con A[q], q puede o no incrementarse, y j siempre se incrementa. El número total de líneas ejecutadas por elemento en el subarreglo es una constante. Como el subarreglo tiene n elementos, el tiempo para hacer la partición es Θ(n) \Theta(n) : una partición en tiempo lineal.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.