Código
int dividir(int *cad, int inc, int end) { int j; int pibote, valor_pivote; int temp; pibote = inc; valor_pivote = cad[pibote]; for (j = inc+1; j <= end; j++) { if (cad[j] < valor_pivote) { pibote++; temp = cad[j]; cad[j] = cad[pibote]; cad[pibote] = temp; } } temp = cad[inc]; cad[inc] = cad[pibote]; cad[pibote] = temp; return pibote; } void quicksort(int *array, int inicio, int fin) { int pivote; if(inicio < fin) { pivote = dividir (array, inicio, fin); quicksort(array, inicio, pivote-1); //ordeno la lista de los menores quicksort(array, pivote+1, fin); //ordeno la lista de los mayores } }
Supongamos que tenemos un array con estos valores:
Código
cad[] = {5, 2, 10, 7, 4};
En este caso tomamos como pibote al 5 y con el ciclo for recorremos el array desde la posicion 1 hasta la 4; y justo abajo tenemos un if con la condicion de que si el valor contenido en el array es menor al pibote, se ejecutara el bloque de instrucion siguiente.
En este caso, en el primer recorrido se encuentra al 2 menor al pibote, por lo tanto se cumple la condicion de la que hablabamos. Primeramente el valor del pibote aumenta a uno segun esta declaracion (pibote++;).
Luego a la variable auxiliar (temp) le asignamosel valor de 2 ya que en ese instante el indice [j] contendra el valor de 1 donde esta guardada 2, luego a (cad[j]) le asignamos (cad[pibote]) recuerden que pibote ahora vale 1 y no olvidar que tambien [j]
Se dieron cuenta cad[j] conservo su valor y en esta parte ocurrio lo mismo
(cad[pibote] = temp;) por que los dos [j] y [pibote] trabajaroncon las mismas posiciones osea 1 y no se produjeron intercambios.
Continuamos con el primer recorrido y detectamos que 4 es menor al pibote se cumple la condicion pibote aumenta a 2 ya que valia 1, luego hacemos los cambios (temp) contendra a 4 y (cad[j]) la ultima posicion le asignamos 10 recuerden que [j] vale 4, luego a cad[pibote] le asignamos temp osea 4 recuerden que [pibote] vale 2.
Como ven se intercambiaron 10 y 4; ahora nuestro array quedara asi:
Código
cad[] = {5, 2, 4, 7, 10};
Ahora ya salimos del primer recorrido en esta parte hacemos los intercambios
pertinentes con estas declaraciones:
Código
temp = cad[inc]; cad[inc] = cad[pibote]; cad[pibote] = temp;
Con los valores finales de pibote al salir del ciclo en este caso es 2
como se daran cuenta aca ocurre un intercambio, deben saber que (inc) vale 0 su
valor no varia mientras no se ejecute la funcion recursiva, y e obvio que se
intercambiaron 4 y 5 ahora el array pasa asi:
Código
cad[] = {4, 2, 5, 7, 10};
Al salir pibote retorna 2 y se ejecuta la funcion que ordena la lista de los menores
como ven a (pivote-1) pasa a valer solo 1, osea solo podemos leer los valores
cad[] = {4, 2}; ahora el 4 actua como pibote y (inc) sigue valiendo 0 ahora en este
recorrido encuentra que 2 es menor al pibote y aumenta pibote a 1 como ya es de predecir en esta parte no se produciran intercambios.
Salimos de ciclo, y hacemos los intercambios con las declaraciones de abajo,
pibote termina con un valor final de 1 y (inc) sigue con 0; se intercambian los valores quedando asi nuestro array:
Código
cad[] = {2, 4, 5, 7, 10};
Y de esta forma quedo ordenado nuestro array; creo que luego se volvio a ejecutar la parte que ordena la lista de los mayores pero sin realizar cambios.
Espero que a algunos iniciados en esto de la programacion le sirva para aprender de este algoritmo y a los que ya dominan este tema me corrija si he fallado en algo
Saludos!!