Estadístico de orden -ésimo en
Se da un arreglo de tamaño y un número . El problema es hallar el -ésimo número más grande del arreglo, es decir, el estadístico de orden -ésimo.
La idea básica: usar la idea del algoritmo quicksort. En realidad, el algoritmo es sencillo; es más difícil demostrar que corre en un promedio de , a diferencia del quicksort.
Implementación (no recursiva)
template <class T>
T order_statistics (std::vector<T> a, unsigned n, unsigned k)
{
using std::swap;
for (unsigned l=1, r=n; ; )
{
if (r <= l+1)
{
// the current part size is either 1 or 2, so it is easy to find the answer
if (r == l+1 && a[r] < a[l])
swap (a[l], a[r]);
return a[k];
}
// ordering a[l], a[l+1], a[r]
unsigned mid = (l + r) >> 1;
swap (a[mid], a[l+1]);
if (a[l] > a[r])
swap (a[l], a[r]);
if (a[l+1] > a[r])
swap (a[l+1], a[r]);
if (a[l] > a[l+1])
swap (a[l], a[l+1]);
// performing division
// barrier is a[l + 1], i.e. median among a[l], a[l + 1], a[r]
unsigned
i = l+1,
j = r;
const T
cur = a[l+1];
for (;;)
{
while (a[++i] < cur) ;
while (a[--j] > cur) ;
if (i > j)
break;
swap (a[i], a[j]);
}
// inserting the barrier
a[l+1] = a[j];
a[j] = cur;
// we continue to work in that part, which must contain the required element
if (j >= k)
r = j-1;
if (j <= k)
l = i;
}
}Notas
- El algoritmo aleatorizado de arriba se llama quickselect . Hay que hacer un shuffle aleatorio de antes de llamarlo o usar un elemento aleatorio como barrera para que corra correctamente. También hay algoritmos deterministas que resuelven el problema especificado en tiempo lineal, como mediana de medianas .
- std::nth_element resuelve esto en C++ pero la implementación de gcc corre en tiempo en el peor caso.
- Hallar los elementos más pequeños se puede reducir a hallar el -ésimo elemento con un overhead lineal, porque son exactamente los elementos que son menores que el -ésimo.