¿Comprende un algoritmo de selección mediano?

Question

Actualmente estoy aprendiendo algoritmos en mi tiempo libre, pero tengo la siguiente pregunta al estudiar algoritmos de selección de capítulo 3().

Entiendo que puedo usar el algoritmo select() para encontrar el número mediano (n/2º número más pequeño) si estaba usando una matriz de A a n números.

1) pero esta es la parte que estoy luchando por comprender. A = [3, 7, 5, 1, 4, 2, 6, 2]. supongamos que es la matriz. cuál es el contenido de la matriz después de cada llamada a Partition(), y los parámetros en cada llamada recursiva de Select().

¿alguien puede explicar cómo están resolviendo esto, por favor?

a continuación es el pseudocódigo para los 2 algoritmos.

Select(A, p, r, k) { 
    /* return k-th smallest number in A[p..r] */ 
    if (p==r) return A[p] /* base case */ 
    q := Partition(A,p,r) 
    len := q – p + 1 
    if (k == len) return A[q] 
    else if (k<len) return Select(A,p,q-1,k) 
    else return Select(A,q+1,r,k-len) 
} 

y el segundo código es

Partition(A, p, r) { /* partition A[p..r] */ 
    x := A[r] /* pivot */ 
    i := p-1 
    for j := p to r-1 { 
     if (A[j] <= x) { 
      i++ 
      swap(A[i], A[j]) 
     } 
    } 
    swap(A[i+1], A[r]) 
    return i+1 
} 

El libro que estoy usando se llama la derivación de Algoritmos por Anne Kaldewaij.

Answer 1

Este algoritmo funciona en dos pasos. El paso de división funciona eligiendo un elemento de pivote, luego reorganizando los elementos de la matriz de modo que todo lo que esté por debajo del pivote esté a un lado, todo lo que sea mayor que el pivote esté en el otro lado, y el pivote esté en el lugar correcto. Por ejemplo, dada la matriz

3 2 5 1 4 

Si escogemos un pivote de 3, entonces podríamos dividir el conjunto de esta manera:

2 1 3 5 4 
+--+^+--+ 
^ | ^
| | +--- Elements greater than 3 
| +-------- 3, in the right place 
+------------- Elements less than 3 

en cuenta que no se ha regulado la matriz; acabamos de hacer que esté más cerca de ser ordenado. Este es, por cierto, el primer paso en el quicksort.

El algoritmo utiliza la siguiente lógica. Supongamos que queremos encontrar el elemento que pertenece al índice k en orden ordenado (el k-ésimo elemento más pequeño). Luego, en relación con el pivote que elegimos, hay tres opciones:

1. El pivote está en la posición k. Entonces, dado que el pivote está en el lugar correcto, el valor que estamos buscando debe ser el pivote. Hemos terminado.
2. El pivote está en una posición mayor que k. Entonces, el k-ésimo elemento más pequeño debe estar en la porción de la matriz antes del pivote, por lo que podemos buscar recursivamente esa parte de la matriz para el k-ésimo elemento más pequeño.
3. El pivote está en una posición más pequeña que k. Entonces el k-ésimo elemento más pequeño debe estar en algún lugar en la región superior de la matriz, y podemos recurrir allí.

En nuestro caso, supongamos que queremos el segundo elemento más pequeño (el de la posición 2). Desde el pivote terminó en la posición 3, esto significa que el segundo más pequeño elemento debe estar en algún lugar en la primera mitad de la matriz, por lo que sería recursivo en el subconjunto

2 1 

Si queremos que el elemento de mediana real, dado que el pivote terminó justo en el medio de la matriz, solo obtendríamos que la mediana es 3 y listo.

Por último, si queríamos algo así como el cuarto más pequeño elemento, ya que el pivote es antes de la posición 4, nos Recurse en la mitad superior de la matriz, es decir

5 4 

y buscaríamos la primer elemento más pequeño aquí, ya que hay tres elementos antes de esta región.

El resto del algoritmo son los detalles de cómo realizar el paso de partición (que es probablemente la parte más complicada del algoritmo) y cómo hacer la elección de tres vías sobre recurrencia o no (un poco menos difícil). Sin embargo, con suerte, esta estructura de alto nivel ayuda a que el algoritmo tenga más sentido.

Espero que esto ayude!