K-ésima ordem em $O(N)$

Dada uma array A de tamanho N e um número K. O desafio é encontrar o K-ésimo maior número na array, ou seja, K-ésima ordem de estatística.

A idéia básica é usar a idéia do algoritmo quick sort (wiki). Na verdade, o algoritmo é simples, é mais difícil provar que ele é executado em uma média de O(N), em contraste com o quick sort.

Implementação (não 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)
        {
            // o tamanho da parte atual é 1 ou 2
            if (r == l+1 && a[r] < a[l])
                swap (a[l], a[r]);
            return a[k];
        }

        // ordenando 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]);

        // performando divisão
        // a[l + 1] - mediana entre 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]);
        }

        // inserindo a mediana
        a[l+1] = a[j];
        a[j] = cur;

        // continuamos a trabalhar nessa parte, que deve conter o elemento desejado
        if (j >= k)
            r = j-1;
        if (j <= k)
            l = i;
    }
}

Nota: na biblioteca padrão do C++, esse algoritmo já foi implementado - ele é chamado de nth_element(link).

Problemas