QuickSelect para encontrar el k-ésimo menor en un subarreglo
Publicado por Daydream (1 intervención) el 12/07/2019 00:14:58
Dado un arreglo desordenado de enteros A[1..n], el algoritmo quickSelect() retorna el k-ésimo menor elemento del subarreglo A[l...r], para algún k ≤ r−l + 1:
El desafío se trata de implementar dos estrategias diferentes para encontrar, a partir del k-ésimo menor, los m menores elementos en A[l...r]; o dicho de otro modo, encontrar dentro de A[l...r], los elementos que est´en desde el k-ésimo menor hasta el (k +m−1)-ésimo menor, para algún par de valores m<< n y k < n−m.
Metodo 1
Reescriba el algoritmo Quickselect para que ahora encuentre los m menores pedidos. Implemente esta variante utilizando un stack S para ir guardando los elementos encontrados durante la recursividad.
Metodo 2
Utilice una lista doblemente enlazada, L, de largo maximo (k + m−1) e implemente la siguiente heurística para resolver el mismo problema:
1. Recorra secuencialmente el subarreglo A[l...l+k+m−1] e inserte, ordenada y ascendentemente, los k + m primeros elementos de A. Para el ejemplo anterior, L quedará con los siguientes k + m − 1 = 6 elementos ordenados: L = {2,3,5,6,11,16}. Note que si r − l = k + m, el problema ya está resuelto y los menores buscados están desde el nodo k hasta el último nodo de L.
2. Si hay más de (k + m) elementos en A[`...r], guarde en una variable maxL el máximo valor de L, es decir el valor del último nodo, el de posición k + m. Para el ejemplo, maxL = 16.
3. Sea l' = l+k+m, recorra A[l'...r] y para todo valor A[i] ≤ maxL, con l' ≤ i ≤ r, inserte A[i] en L, elimine el último nodo y actualice el valor de maxL. Note que los elementos A[i] > maxL no son necesarios. Para el ejemplo anterior, el primer A[i] que debe insertarse en L es A[l'] = 0, eliminando el último nodo (valor 16), quedando maxL = 11. Este proceso debe repetirse para todos los elementos restantes en A[l' + 1...r].
1
2
3
4
5
6
7
8
9
10
11
quickSelect(A, l, r, k){
if (l = r) then
return A[l]
p =partition(A, l, r)
u = p−l // # celdas a la izquierda de la particion
if (k = u + 1) then // el pivote es justo el menor buscado
return A[p]
if (k ≤ u) then
return quickSelect(A, l, p−1, k) // el k-ésimo menor está a la izquierda
return quickSelect(A, p + 1, r, k−u−1) // el k-ésimo menor está a la derecha
}El desafío se trata de implementar dos estrategias diferentes para encontrar, a partir del k-ésimo menor, los m menores elementos en A[l...r]; o dicho de otro modo, encontrar dentro de A[l...r], los elementos que est´en desde el k-ésimo menor hasta el (k +m−1)-ésimo menor, para algún par de valores m<< n y k < n−m.
Metodo 1
Reescriba el algoritmo Quickselect para que ahora encuentre los m menores pedidos. Implemente esta variante utilizando un stack S para ir guardando los elementos encontrados durante la recursividad.
Metodo 2
Utilice una lista doblemente enlazada, L, de largo maximo (k + m−1) e implemente la siguiente heurística para resolver el mismo problema:
1. Recorra secuencialmente el subarreglo A[l...l+k+m−1] e inserte, ordenada y ascendentemente, los k + m primeros elementos de A. Para el ejemplo anterior, L quedará con los siguientes k + m − 1 = 6 elementos ordenados: L = {2,3,5,6,11,16}. Note que si r − l = k + m, el problema ya está resuelto y los menores buscados están desde el nodo k hasta el último nodo de L.
2. Si hay más de (k + m) elementos en A[`...r], guarde en una variable maxL el máximo valor de L, es decir el valor del último nodo, el de posición k + m. Para el ejemplo, maxL = 16.
3. Sea l' = l+k+m, recorra A[l'...r] y para todo valor A[i] ≤ maxL, con l' ≤ i ≤ r, inserte A[i] en L, elimine el último nodo y actualice el valor de maxL. Note que los elementos A[i] > maxL no son necesarios. Para el ejemplo anterior, el primer A[i] que debe insertarse en L es A[l'] = 0, eliminando el último nodo (valor 16), quedando maxL = 11. Este proceso debe repetirse para todos los elementos restantes en A[l' + 1...r].
Valora esta pregunta
0