Buscar elemento k-esimo en un array no ordenado

[lRetro]

El ejercicio me pide buscar el elemento k-esimo en un array no ordenado pero como si el array estuviese ordenado, es decir:

Para el array ejemplo v = 3 4 5 2 6 8 y k = 2 el programa debe devolver v[3] = 2 pues si el array estuviese ordenado el segundo elemento seria el 2.

Este es el enunciado en cuestion:

·Aprovechando el método partir implementado en el primer apartado, completar en la
clase BuscaElem la implementación eficiente del método kesimoRec que tome como
parámetros un vector v (desordenado) y tres enteros, y encuentre el elemento que debería
estar en la posición k (si este estuviera ordenado, pero sin ordenar el vector) de dicho
vector desde izq a der.

Es una busqueda QuickSort. El metodo partir es un metodo implementado en otro apartado que funciona correctamente (para QuickSort).

[Serapis]

Ya, pero es que si usas QuickSort, ya estás ordenando el array, porque Si o Sí debe hacer intercambios.
Entonces que al final no esté completamente ordenado el array, porque queden algunos intercambios por hacer, es trivial... (quedaría completamente ordenado si te pidieran el elemento 0º)

Con la parte primera del enunciado, sin el asunto de QuickSort, puedes solventarlo así (sería equivalente al procedimiento para un ordenamiento SelectionSort):

Código [Seleccionar] Expandir


entero = BuscarKEsimo(entero ksimo, array Ar())
    entero menor

    // 1º: Buscar el mnor del array
    menor = BuscarMenor(ar, 0, ar.count -1)

    // 2º buscar el que sigue al menor hallado hasta el momento.
    bucle para k desde 1 hasta ksimo  //se supone que ksimo está dentro de los límites del array.
        menor = BuscarMenorSiguiente(ar, 0, ar.count-1, menor)
    fin bucle
    devolver menor
fin funcion

// Esta función busca el menor en un array.
entero = funcion BuscarMenor(array Ar(), entero desde, entero hasta)
    entero v
   
    v = ar(desde)
    Hacer mientras (desde <= hasta)
        Si (Ar(desde) < v) luego
            v = Ar(desde)
        fin si
        desde += 1
    repetir
   
    devolver = v
fin funcion

// esta función busca el menor en un array mayor que 'exige'.
entero = funcion BuscarMenorSiguiente(array Ar(), entero desde, entero hasta, entero exige)
    entero v
   
    v = ar(desde)
    Hacer mientras (desde <= hasta)
        Si (( Ar(desde) < v) y ( Ar(desde) > exige)) luego  // esta es la diferencia de la función previa: y ( Ar(desde) > exige)
            v = Ar(desde)
        fin si
        desde += 1
    repetir
   
    devolver = v
fin funcion


Nota: Que si el array tiene elementos repetidos (para el valor que se pide o anterior), no lo resuelve, queda a tu esfuerzo solucionarlo, así como pasar el pseudocódigo al lenguaje deseado.

[lRetro]

Ese codigo sería para una búsqueda normal, comparando uno a uno. Eso es facil de hacer poniendo un simple contador que cuando llegue a K salga del bucle y devuelva el valor obtenido. El contador iria aumentando a medida que se vaya encontrando un valor superior en el array.

Lo que me pide el ejercicio es que a partir de la funcion partir, que es la siguiente:

public static <T extends Comparable<? super T>> int partir(T v[], T pivote, int izq, int der) {
      int i = izq-1; // busqueda por la izquierda
      int j = der+1; // busqueda por la derecha
      T aux;
      while (i < j){ // mientras no se crucen las busquedas
       do{
          j--;
       }while (v[j].compareTo(pivote) > 0);
      
       do{
          i++;
       }while (v.compareTo(pivote) < 0);
      
       if (i < j){ // si no se han cruzado
          aux = v; // los intercambia
          v = v[j];
          v[j] = aux;
       }
      }      
      return j;
   }

(es la parte de encontrar el pivote y dividir el array en dos trozos, para luego repetir la operacion (el divide y venceras de toda la vida)), me pide encontrar el k-esimo elemento sin ordenar el array y utilizando ese codigo. Se que es complicado, por eso lo pregunto por aqui jeje.

[Serapis]

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...

Código [Seleccionar] Expandir


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 || 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).