¿Cuál es la diferencia práctica entre std :: nth_element y std :: sort?

Question

He estado mirando el std :: algoritmo nth_element que al parecer:

reordena los elementos en el rango [primero, último), de tal manera que el elemento en la posición enésima resultante es la elemento que sería en esa posición en una secuencia ordenada, sin ninguno de los elementos anterior a que sea mayor y ninguno de los elementos que lo siguen más pequeño que él. Ni los elementos que lo preceden ni los elementos que le siguen están garantizados para ser pedidos.

Sin embargo, con mi compilador, ejecutando el siguiente:

vector<int> myvector; 
    srand(GetTickCount()); 

    // set some values: 
    for (int i = 0; i < 10; i++) 
     myvector.push_back(rand()); 

    // nth_element around the 4th element 
    nth_element (myvector.begin(), myvector.begin()+4, myvector.end()); 

    // print results 
    for (auto it=myvector.begin(); it!=myvector.end(); ++it) 
     cout << " " << *it; 

    cout << endl; 

Siempre devuelve una lista ordenada de números enteros completamente exactamente de la misma manera que std :: sort hace. ¿Me estoy perdiendo de algo? ¿Para qué es útil este algoritmo?

EDITAR: Ok el siguiente ejemplo usando un conjunto mucho más grande muestra que hay una gran diferencia:

vector<int> myvector; 
    srand(GetTickCount()); 

    // set some values: 
    for (int i = 0; i < RAND_MAX; i++) 
     myvector.push_back(rand()); 

    // nth_element around the 4th element 
    nth_element (myvector.begin(), myvector.begin()+rand(), myvector.end()); 

    vector<int> copy = myvector; 
    std::sort(myvector.begin(), myvector.end()); 

    cout << (myvector == copy ? "true" : "false") << endl; 

Answer 1

Es perfectamente válido para std::nth_element ordenar todo el rango para cumplir con la semántica documentada; sin embargo, al hacerlo, no podrá cumplir con la complejidad requerida (lineal). El punto clave es que puede hacerlo, pero no tiene que.

Esto significa que std::nth_element puede rescatar temprano: tan pronto como sepa el elemento n'th de su rango, puede detenerse.Por ejemplo, para una gama

[9,3,6,2,1,7,8,5,4,0] 

pidiéndole que le dan el cuarto elemento puede producir algo así como

[2,0,1,3,8,5,6,9,7,4] 

La lista se solucionó parcialmente, lo suficiente bueno para ser capaz de decir que el cuarto elemento en orden será 3.

Por lo tanto, si quiere responder 'cuál es el cuarto más pequeño' o 'cuáles son los cuatro más pequeños', entonces std::nth_element es su amigo.

Si desea obtener los cuatro números más pequeños en orden, puede considerar usar std::partial_sort.

Answer 2

std::sort tipo todos los elementos. std::nth_elenemt no. Simplemente pone el enésimo elemento en la enésima posición, con elementos más pequeños o iguales en un lado y elementos más grandes o iguales en el otro. Se usa si desea encontrar el enésimo elemento (obviamente) o si desea los n elementos más pequeños o más grandes. Un tipo completo cumple estos requisitos.

¿Por qué no simplemente realizar una clasificación completa y obtener el enésimo elemento? Porque std::nth_element tiene el requisito de tener O (N) complejidad, mientras que std::sort es O (Nlog (N)). std::sort no puede satisfacer el requisito de complejidad de std::nth_element. Si no necesita una clasificación completa del rango, es ventajoso usarlo.

En cuanto a su ejemplo, al ejecutar código similar en GCC 4.7, que obtiene los resultados esperados:

for (int i = 0; i < 10; i++) 
    myvector.push_back(rand()%32); // make the numbers small 

    cout << myvector << "\n"; 
// nth_element around the 4th element 
    nth_element (myvector.begin(), myvector.begin()+4, myvector.end()); 
    cout << myvector << "\n"; 
    std::sort(myvector.begin(), myvector.end()); 
    cout << myvector << "\n"; 

produce

{ 7, 6, 9, 19, 17, 31, 10, 12, 9, 13 } 
{ 9, 6, 9, 7, 10, 12, 13, 31, 17, 19 } 
{ 6, 7, 9, 9, 10, 12, 13, 17, 19, 31 } 
      ^

donde yo he utilizado un encargo de impresión a ostream operator<< los resultados.

Answer 3

La implementación de std :: nth_element es el siguiente:

void _Nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred) 
{ 
    for (; _ISORT_MAX < _Last - _First;) 
     { // divide and conquer, ordering partition containing Nth 
     pair<_RanIt, _RanIt> _Mid = 
      _Unguarded_partition(_First, _Last, _Pred); 

     if (_Mid.second <= _Nth) 
      _First = _Mid.second; 
     else if (_Mid.first <= _Nth) 
      return; // Nth inside fat pivot, done 
     else 
      _Last = _Mid.first; 
     } 

    _Insertion_sort(_First, _Last, _Pred); // sort any remainder 
} 

donde ISORT_MAX define como 32.

Así que si su secuencia es Shoter de 32 elementos que sólo realiza InsertionSort en él. Por lo tanto, su secuencia corta está ordenada por completo.