Paso 5: Implementación de qs_partition
Fondo
Antes de moverse a la aplicación de la función quick_sort, debemos entender que quick_sort no hace mucho por sí mismo. Nuestra función qs_partition hace la mayor parte de la obra. qs_partition toma como parámetros un array de enteros, un límite izquierdo en esa matriz y un límite derecho en esa matriz y devuelve un entero, como principal.
* Nota: debido a una biblioteca que estamos utilizando (algorithm.h) ya tiene una función llamada partición, que llamamos nuestra función de partición qs_partition.
Objetivo
El trabajo de qs_partition es un número en el array como pivote y separar todos los números de la matriz en dos grupos: aquellos que sean menor o igual que el pivote y los que son mayores. Lugares todos los números menores o iguales antes el pivote y el mayor número después. Aquí es una forma que se puede lograr.
Pasos
1) qs_partition primero lo primero que está permitido tocar (el punto en el límite izquierdo) se lleva y lo llama un pivote. No hay nada especial aquí. Todo la función que hace primero es declarar que un valor llamado pivote es igual al primer elemento que la función puede acceder.
2) de la misma manera, lo voy a llamar un toSwap variable y asignar el Índice del pivote.
3) entonces corremos a través de la matriz, mirando cada elemento desde el segundo valor para el límite derecho. No comparamos el primer valor con el valor pivote porque el primer valor es el valor del pivote.
4) en cada punto, comparamos el valor en ese punto nuestro pivote. Si ese valor es menor o igual que el pivote, queremos avanzar ese valor tan lejos hacia el principio de la matriz como sea posible. Es donde toSwap. A cambio el valor en toSwap (porque toSwap es un índice) y vemos el valor actual, entonces incrementaremos toSwap por uno para no cambiar los valores de nuevo en el centro de la matriz.
5) una vez que hemos recorren todos los números, nuestro índice de toSwap representa el lugar donde queremos poner nuestro pivote. Así que a cambiar el valor en toSwap y el pivote. Por último, a devolver, o pasar a la función que se llama qs_partition, el índice de donde ponemos el pivote. Usted verá por qué pronto.
Informe
Ojalá puedan ver que cambiando secuencialmente números menor que el pivote en el primer lugar después de nuestro último intercambio, hemos creado el efecto deseado: todos los números antes del pivote son menor o igual que el pivote y después de él todos los números son mayores.
