La partición que haces es la original de Hoare, con la excepción de que Hoare, toma para el caso como pivot, el valor el índice minimo (el parámetro que tu llamas izq). En implementaciones más óptimas se suele tomar como pivot el índice central del rango presente.
El caso es que la partición es ciega, es decir, ni sabe que valores contiene, ni sabe donde está el menor ni el mayor, ni guarda información al respecto.
La partición simplemente divide hacia un lado u otro del pivot los valores mayores o menores del pivot, respectivamente. ...pero solo de los valores en el rango izq-der que recibe el array. No sabes en qué momento el valor késimo está en su sitio, solo tienes garantía de que al terminar de ordenar si lo estará.
Pero es que además, la partición para funcionar y evolucionar en las siguientes fases, DEBE forzosamente intercambiar valores, luego el algoritmo Quicksort se está ejecutando y por ende, el array se está ordenando, te guste o no.
En resumen, así opera el algoritmo QuickSort de Hoare...
...y no hay forma de saber* en qué llamada tendrás el késimo valor ordenado en su sitio, excepto al término.
Por ejemplo, aquí un ejemplo, la primera línea es el array desordenado, las siguientes, son el array parcial en la siguiente etapa (he despreciado las etapas donde no cambia nada, para que quede lo más breve posible).
4 1 7 10 5 2 6 0 7 9
-----------------------
0 1 7 10 5 2 6 4 7 9
0 1 2 10 5 7 6 4 7 9
0 1 2
10 5 7 6 4 7 9
9 5 7 6 4 7 10
9 5 7 6 4 7
7 5 7 6 4 9
7 5 7 6 4
4 5 7 6 7
4 5 6 7 7
4 5 6
5 6
7 7
Aunque QuickSort sea muy eficiente, no es una búsqueda binaria (incluso a pesar de que en cierto modo haga particiones binarias), y por tanto no hay información precisa de dónde se haya el késimo valor que resultará ordenado hasta que no termine de ordenarse.
Si lo entiendes o no, es otra historia...
p.d.:
*: Aunque añadas código intermedio para intentar excrutarlo, será del todo ineficiente. Pués basta saber que con recorrer 1 sola vez el array obtienes el menor, para hallar el kesimo te basta recorrerlo k veces y si k es más de la mitad del tamaño, lo buscas desde el mayor hacia atrás. En realidad si k es un valor alto, será más ineficiente que ordenar el array.
Un modo mejor para lograr lo que quieres que con el procedimiento de Selection (que busca el menor en el array, sobre los n elementos no ordenados aún), es operar con grupos de tamaño k. entre sí, es decir si k = 5, ordena el array de 5 en 5 (supongamos 40 elementos); del 0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-34, 35-39
Tras ese ordenamiento de los 8 grupos, se trata de hacer otra fase donde se procede a ordenar nuevamente (pero ahora por refundición puesto que ya están pre ordenados), cada dos grupos entre sí, y tras esta primera fase ya puedes descartar del 5-9, 15-19, 25-29, 35-39 (por que los 5 menores de cada grupo 5+5), se han movido al grupo de abajo), luego se sigue refundiendo otros grupos, pero saltanto los excluídos, así se refunde ahora: 0-4 con 10-14, 20-24 con 30-34. igualmente en cada etapa se van descartando la mitad de los elementos con los que se ha operado.
En esa última refundición será el grupo: 0-4 con 20-24 (los 5 menores se dejarán en 0-4, descartando finalmente también el grupo 20-24).
En la última refundición ya tendríamos 0-4 como menores, luego la solución sería miArray(4) (ya que dijimos que k=5)...
Esta solución también va particionando el array en 2, pero de cada vez deshecha (ordenar) la mitad (de los que quedan) que no contiene los deseados. Este método es incluso más óptimo para buscar el késimo elemento (que resultaría una vez ordenado) que por cualquier otro método donde el array no esté ya ordenado.
p.d2: Te pongo un ejemplo desarollado y comentado con éste último método... Si no eres capaz se implementarlo lo señalas y veo de sacar un tiempito y te oriento
El késimo pedido vamos a suponer que es el 5º (k=5), y supongamos el siguiente array aleatorio (de 40 elementos, 8 grupos, por simplicidad al no tener que lidiar con elementos sueltos, ...el propósito es que lo enttiendas):
16 11 12 14 13 20 31 32 42 26 17 28 4 25 15 6 11 2 29 5 8 32 21 25 37 41 1 7 40 30 35 11 0 22 34 3 19 43 38 27
El array separado en grupos de k (k=5 hemos puesto de ejemplo), solo por claridad...
16 11 12 14 13 || 20 31 32 42 26 || 17 28 4 25 15 || 6 11 2 29 5 || 8 32 21 25 37 || 41 1 7 40 30 || 35 11 0 22 34 || 3 19 43 38 27
Ordenando en la priemra fase (cada grupo de k entre sí). Ésta es una fase de ordenamiento previa, usando cualquier algoritmo de ordenamiento, cuando hay muy pocos elementos el más efectivo suele ser InsertionSort):
11 12 13 14 16 || 20 26 31 32 42 || 4 15 17 25 28 || 2 5 6 11 29 || 8 21 25 32 37 || 1 7 30 40 41 || 0 11 22 34 35 || 3 19 27 38 43
Refundimos gada dos grupos de 5 entre sí (y luego tachamos el segundo grupo que ya no se usará en la siguiente etapa):
11 12 13 14 16 ||20 26 31 32 42 || 2 4 5 6 11 || 15 17 25 28 29 || 1 7 8 21 25 || 32 37 30 40 41 || 0 3 11 19 22 || 34 35 27 38 43
En la siguiente, se refunden (y se muestrasn ya refundidos) los k elementos de dos grupos separados ahora por el doble de distancia previa (y tras los tachados de antes, se añade otro grupo de tachados)
2 4 5 6 11 ||20 26 31 32 42 || 12 13 14 16 11 || 15 17 25 28 29 || 0 1 3 7 8 || 32 37 30 40 41 || 21 25 11 19 22 || 34 35 27 38 43
Finalmente solo quedan 2 grupos por refundir, se queda el bajo y se tacha el alto, con lo cual ya terminamos:
0 1 2 3 4 ||20 26 31 32 42 || 12 13 14 16 11 || 15 17 25 28 29 || 5 6 11 7 8 || 32 37 30 40 41 || 21 25 11 19 22 || 34 35 27 38 43
Y así el késimo será: Ar(k-1) = 4
Nota que segundo grupo tras la refundición no permanece ordenado (como se ve en: 5 6 11 7 8 ), una vez obtenido los k elementos en el 1º grupo, se pasa al segundo los que estaban en el 1º grupo remplazados por los del 2º... y se pasan para mantener la integridad del array (que siga teniendo los mismos elementos a la salida que contenía a la entrada).
El caso es que la partición es ciega, es decir, ni sabe que valores contiene, ni sabe donde está el menor ni el mayor, ni guarda información al respecto.
La partición simplemente divide hacia un lado u otro del pivot los valores mayores o menores del pivot, respectivamente. ...pero solo de los valores en el rango izq-der que recibe el array. No sabes en qué momento el valor késimo está en su sitio, solo tienes garantía de que al terminar de ordenar si lo estará.
Pero es que además, la partición para funcionar y evolucionar en las siguientes fases, DEBE forzosamente intercambiar valores, luego el algoritmo Quicksort se está ejecutando y por ende, el array se está ordenando, te guste o no.
En resumen, así opera el algoritmo QuickSort de Hoare...
Código [Seleccionar]
Funcion QuicksortHoare(array Ar(), entero Min, entero Max)
entero p
si (Min < Max) luego
p = ParticionHoare(Ar, Min, Max)
llamada QuicksortHoare(Ar, Min, p)
llamada QuicksortHoare(Ar, p + 1, Max)
fin si
fin funcion
entero Funcion ParticionHoare(array Ar(), entero Min, entero Max)
entero j, k, i, pivot
pivot = Ar(Min)
j = (Min - 1)
k = (Max + 1)
Hacer
Hacer
j = (j + 1)
Repetir Mientras (Ar(j) < pivot)
Hacer
k = (k - 1)
Repetir Mientras (Ar(k) > pivot)
si (j < k) luego
i = Ar(j)
Ar(j) = Ar(k)
Ar(k) = i
Sino
devolver k
Fin si
Repetir
Fin Funcion
...y no hay forma de saber* en qué llamada tendrás el késimo valor ordenado en su sitio, excepto al término.
Por ejemplo, aquí un ejemplo, la primera línea es el array desordenado, las siguientes, son el array parcial en la siguiente etapa (he despreciado las etapas donde no cambia nada, para que quede lo más breve posible).
4 1 7 10 5 2 6 0 7 9
-----------------------
0 1 7 10 5 2 6 4 7 9
0 1 2 10 5 7 6 4 7 9
0 1 2
10 5 7 6 4 7 9
9 5 7 6 4 7 10
9 5 7 6 4 7
7 5 7 6 4 9
7 5 7 6 4
4 5 7 6 7
4 5 6 7 7
4 5 6
5 6
7 7
Aunque QuickSort sea muy eficiente, no es una búsqueda binaria (incluso a pesar de que en cierto modo haga particiones binarias), y por tanto no hay información precisa de dónde se haya el késimo valor que resultará ordenado hasta que no termine de ordenarse.
Si lo entiendes o no, es otra historia...
p.d.:
*: Aunque añadas código intermedio para intentar excrutarlo, será del todo ineficiente. Pués basta saber que con recorrer 1 sola vez el array obtienes el menor, para hallar el kesimo te basta recorrerlo k veces y si k es más de la mitad del tamaño, lo buscas desde el mayor hacia atrás. En realidad si k es un valor alto, será más ineficiente que ordenar el array.
Un modo mejor para lograr lo que quieres que con el procedimiento de Selection (que busca el menor en el array, sobre los n elementos no ordenados aún), es operar con grupos de tamaño k. entre sí, es decir si k = 5, ordena el array de 5 en 5 (supongamos 40 elementos); del 0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-34, 35-39
Tras ese ordenamiento de los 8 grupos, se trata de hacer otra fase donde se procede a ordenar nuevamente (pero ahora por refundición puesto que ya están pre ordenados), cada dos grupos entre sí, y tras esta primera fase ya puedes descartar del 5-9, 15-19, 25-29, 35-39 (por que los 5 menores de cada grupo 5+5), se han movido al grupo de abajo), luego se sigue refundiendo otros grupos, pero saltanto los excluídos, así se refunde ahora: 0-4 con 10-14, 20-24 con 30-34. igualmente en cada etapa se van descartando la mitad de los elementos con los que se ha operado.
En esa última refundición será el grupo: 0-4 con 20-24 (los 5 menores se dejarán en 0-4, descartando finalmente también el grupo 20-24).
En la última refundición ya tendríamos 0-4 como menores, luego la solución sería miArray(4) (ya que dijimos que k=5)...
Esta solución también va particionando el array en 2, pero de cada vez deshecha (ordenar) la mitad (de los que quedan) que no contiene los deseados. Este método es incluso más óptimo para buscar el késimo elemento (que resultaría una vez ordenado) que por cualquier otro método donde el array no esté ya ordenado.
p.d2: Te pongo un ejemplo desarollado y comentado con éste último método... Si no eres capaz se implementarlo lo señalas y veo de sacar un tiempito y te oriento
El késimo pedido vamos a suponer que es el 5º (k=5), y supongamos el siguiente array aleatorio (de 40 elementos, 8 grupos, por simplicidad al no tener que lidiar con elementos sueltos, ...el propósito es que lo enttiendas):
16 11 12 14 13 20 31 32 42 26 17 28 4 25 15 6 11 2 29 5 8 32 21 25 37 41 1 7 40 30 35 11 0 22 34 3 19 43 38 27
El array separado en grupos de k (k=5 hemos puesto de ejemplo), solo por claridad...
16 11 12 14 13 || 20 31 32 42 26 || 17 28 4 25 15 || 6 11 2 29 5 || 8 32 21 25 37 || 41 1 7 40 30 || 35 11 0 22 34 || 3 19 43 38 27
Ordenando en la priemra fase (cada grupo de k entre sí). Ésta es una fase de ordenamiento previa, usando cualquier algoritmo de ordenamiento, cuando hay muy pocos elementos el más efectivo suele ser InsertionSort):
11 12 13 14 16 || 20 26 31 32 42 || 4 15 17 25 28 || 2 5 6 11 29 || 8 21 25 32 37 || 1 7 30 40 41 || 0 11 22 34 35 || 3 19 27 38 43
Refundimos gada dos grupos de 5 entre sí (y luego tachamos el segundo grupo que ya no se usará en la siguiente etapa):
11 12 13 14 16 ||
En la siguiente, se refunden (y se muestrasn ya refundidos) los k elementos de dos grupos separados ahora por el doble de distancia previa (y tras los tachados de antes, se añade otro grupo de tachados)
2 4 5 6 11 ||
Finalmente solo quedan 2 grupos por refundir, se queda el bajo y se tacha el alto, con lo cual ya terminamos:
0 1 2 3 4 ||
Y así el késimo será: Ar(k-1) = 4
Nota que segundo grupo tras la refundición no permanece ordenado (como se ve en: 5 6 11 7 8 ), una vez obtenido los k elementos en el 1º grupo, se pasa al segundo los que estaban en el 1º grupo remplazados por los del 2º... y se pasan para mantener la integridad del array (que siga teniendo los mismos elementos a la salida que contenía a la entrada).
