algorithm - sort - ¿Comprender un algoritmo de selección mediano?

quicksort explicacion

Question

Actualmente estoy aprendiendo algoritmos en mi tiempo libre pero tengo la siguiente pregunta mientras estudio los 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 entender. 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 ().

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

a continuación está 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 The Derivation of Algorithms por Anne Kaldewaij.

Answer 1

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

3 2 5 1 4

Si seleccionamos un pivote de 3, entonces podemos dividir la matriz de esta manera:

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

Tenga en cuenta que no hemos ordenado 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 luego usa 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 porción 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 que está en la posición 2). Dado que el pivote terminó en la posición 3, esto significa que el segundo elemento más pequeño debe estar en algún lugar en la primera mitad de la matriz, por lo que recurriríamos en el subcampo

2 1

Si quisiéramos el elemento mediano real, dado que el pivote termina justo en el medio de la matriz, solo obtendríamos que la mediana es 3 y listo.

Finalmente, si quisiéramos algo así como el cuarto elemento más pequeño, como el pivote está antes de la posición 4, recurriríamos en la mitad superior de la matriz, es decir,

5 4

y buscaría el 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 hacer el paso de partición (que es probablemente la parte más involucrada 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!