nth_element

Artículo
06/09/2015

Las particiones un intervalo de elementos, correctamente situando el enésimoelemento de la secuencia en el intervalo de modo que todos los elementos delante de menor o igual que él y todos los elementos que lo siguen en la secuencia se mayor o igual que.

template<class RandomAccessIterator> 
   void nth_element( 
      RandomAccessIterator _First,  
      RandomAccessIterator _Nth,  
      RandomAccessIterator _Last 
   ); 
template<class RandomAccessIterator, class BinaryPredicate> 
   void nth_element( 
      RandomAccessIterator _First,  
      RandomAccessIterator _Nth,  
      RandomAccessIterator _Last, 
      BinaryPredicate _Comp 
   );

Parámetros

_First
Un iterador de acceso aleatorio que dirige la posición del primer elemento del intervalo que se va a crear particiones.
_Nth
Un iterador de acceso aleatorio que dirige la posición del elemento correctamente que se ordenará en el límite de la partición.
_Last
Un iterador de acceso aleatorio que dirige la posición una más allá del último elemento en el intervalo que se va a crear particiones.
_Comp
Objeto definido por el usuario de la función de predicado que define el criterio de comparación que se completará por los elementos sucesivos del orden. Un predicado binario acepta dos argumentos y devuelve true cuando se cumple y false cuando no se cumple.

Comentarios

El intervalo hace referencia debe ser válido; todos los punteros deben ser dereferenceable y dentro de la secuencia la posición última es accesible de primera por el aumento.

El algoritmo de nth_element no garantiza que los elementos en los sub- intervalos cualquier lado del enésimoelemento están ordenados. Crea por lo menos garantías que partial_sort, que ordena los elementos del intervalo debajo de algún elemento elegido, y puede utilizarse como alternativa más rápida a partial_sort cuando la clasificación de rango inferior no se requiere.

Los elementos son equivalentes, pero son iguales no necesariamente, si hay alguno es menor que otro.

El promedio de una complejidad de ordenación es lineal con respecto al _Last – _First.

Ejemplo

// alg_nth_elem.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>      // For greater<int>( )
#include <iostream>

// Return whether first element is greater than the second
bool UDgreater ( int elem1, int elem2 ) {
   return elem1 > elem2;
}

int main() {
   using namespace std;
   vector <int> v1;
   vector <int>::iterator Iter1;

   int i;
   for ( i = 0 ; i <= 5 ; i++ )
      v1.push_back( 3 * i );

   int ii;
   for ( ii = 0 ; ii <= 5 ; ii++ )
      v1.push_back( 3 * ii + 1 );

   int iii;
   for ( iii = 0 ; iii <= 5 ; iii++ )
      v1.push_back( 3 * iii +2 );

   cout << "Original vector:\n v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;

   nth_element(v1.begin( ), v1.begin( ) + 3, v1.end( ) );
   cout << "Position 3 partitioned vector:\n v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;

   // To sort in descending order, specify binary predicate
   nth_element( v1.begin( ), v1.begin( ) + 4, v1.end( ),
          greater<int>( ) );
   cout << "Position 4 partitioned (greater) vector:\n v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;
   
   random_shuffle( v1.begin( ), v1.end( ) );
   cout << "Shuffled vector:\n v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;

   // A user-defined (UD) binary predicate can also be used
   nth_element( v1.begin( ), v1.begin( ) + 5, v1.end( ), UDgreater );
   cout << "Position 5 partitioned (UDgreater) vector:\n v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;
}

Resultados del ejemplo

Original vector:
 v1 = ( 0 3 6 9 12 15 1 4 7 10 13 16 2 5 8 11 14 17 )
Position 3 partitioned vector:
 v1 = ( 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 )
Position 4 partitioned (greater) vector:
 v1 = ( 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 )
Shuffled vector:
 v1 = ( 5 16 8 15 17 6 10 0 13 2 9 12 3 4 7 1 11 14 )
Position 5 partitioned (UDgreater) vector:
 v1 = ( 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 )