std::nth_element en C++ – Barcelona Geeks

std::nth_element() es un algoritmo STL que reorganiza la lista de tal manera que el elemento en la posición n es el que debería estar en esa posición si ordenamos la lista.

No ordena la lista, solo que todos los elementos que preceden al n-ésimo elemento no son mayores que él, y todos los elementos que lo siguen no son menores que él.
Tiene dos versiones, que se definen a continuación:

Comparando elementos usando “<«:
Sintaxis:

template 
void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
                  RandomAccessIterator last);

first: Random-access iterator to the first element in the list.
last: Random-access iterator to the last element in the list.
nth: Random-access iterator pointing to the position in the list, 
which should be sorted.
If it points to end, then this function will do nothing.

Return Value: Since, return type is void, so it doesnot return any value.

// C++ program to demonstrate the use of std::nth_element
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int v[] = { 3, 2, 10, 45, 33, 56, 23, 47 }, i;
  
    // Using std::nth_element with n as 5
    std::nth_element(v, v + 4, v + 8);
  
    // Since, n is 5 so 5th element should be sorted
    for (i = 0; i < 8; ++i) {
        cout << v[i] << " ";
    }
    return 0;
}

Producción:

3 2 10 23 33 56 45 47

Aquí, el quinto elemento es 33, y todos los elementos a su izquierda son más pequeños que él y todos los elementos a su derecha son más grandes que él.

Al comparar usando una función predefinida:

Sintaxis:

template 
void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
                  RandomAccessIterator last, Compare comp);

Here, first, last and nth arguments are the same as previous case.

comp: Binary function that accepts two elements in the range 
as arguments, and returns a value convertible to bool.
The value returned indicates whether the element passed as first argument is 
considered to go before the second in the specific strict weak ordering it defines.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.

Return Value: Since, its return type is void, so it doesnot return any value.

// C++ program to demonstrate the use of std::nth_element
#include <iostream>
#include <algorithm>
using namespace std;
  
// Defining the BinaryFunction
bool comp(int a, int b)
{
    return (a < b);
}
int main()
{
    int v[] = { 3, 2, 10, 45, 33, 56, 23, 47 }, i;
  
    // Using std::nth_element with n as 6
    std::nth_element(v, v + 5, v + 8, comp);
  
    // Since, n is 6 so 6th element should be the same
    // as the sixth element present if we sort this array
    // Sorted Array
    /* 2 3 10 23 33 45 47 56 */
    for (i = 0; i < 8; ++i) {
        cout << v[i] << " ";
    }
    return 0;
}

Producción:

33 2 10 23 3 45 47 56

En este código, dado que el enésimo elemento señalado por el segundo argumento en std::nth_element es el sexto elemento de la array v, esto significa que el sexto elemento en la array después de la aplicación de std::nth_element debe ser el que habría estado allí si se ordenara toda la array, es decir, 45.

Y también todos los elementos a su izquierda son menores que él o iguales a él y los elementos a su derecha son mayores que él.

Propósito de la función binaria comp: std::nth_element ordena parcialmente el rango [primero, último] en orden ascendente para que la condición, *i < *j, (para la versión 1), o comp(*i, *j) == verdadero (para la versión 2) se cumple para cualquier i en el rango [primero, enésimo) y para cualquier j en el rango [enésimo, último). Por lo tanto, comp() se usa para garantizar que todos los elementos antes de nth_element sean menores que los elementos después de nth_element.

¿Dónde podemos aplicar std::nth_element() ?

Se puede usar si queremos encontrar los primeros n números más pequeños , pero pueden estar ordenados o no.

// C++ program to find first n smallest numbers
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int v[] = { 30, 20, 10, 40, 60, 50, 70, 80 }, i;
  
    // Using std::nth_element with n as 3
    std::nth_element(v, v + 2, v + 8);
  
    // Since, n is 3 so now first three numbers will be the
    // three smallest numbers in the whole array
    // Displaying first three smallest number
    for (i = 0; i < 3; ++i) 
    {
        cout << v[i] << " ";
    }
    return 0;
}

Producción:

20 10 30

Al igual que los primeros n números más pequeños, también podemos encontrar los primeros n números más grandes , simplemente cambiando la función binaria pasada como argumento en std::nth_element.

// C++ program to find first n largest numbers
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int v[] = { 30, 20, 50, 60, 70, 10, 80, 40 }, i;
  
    // Using std::nth_element with n as 2
    std::nth_element(v, v + 1, v + 8, std::greater<int>());
  
    // Since, n is 2 so first 2 elements will be the largest
    // among all the array elements
    // Displaying First 2 elements
    for (i = 0; i < 2; ++i) 
    {
        cout << v[i] << " ";
    }
    return 0;
}

Producción:

80 70

Aquí, hemos pasado mayor() como función binaria, por lo que ahora el elemento n será el que debería estar en el lugar n si ordenamos la array dada en orden descendente, por lo que los primeros n elementos serán los primeros n elementos más grandes.

Se puede utilizar para encontrar la mediana de los elementos dados.

// C++ program to find the median of the vector
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    vector<int> v = { 3, 2, 10, 45, 33, 56, 23, 47, 60 }, i;
  
    // Using std::nth_element with n as v.size()/2 + 1
    std::nth_element(v.begin(), v.begin() + v.size() / 2, v.end());
  
    cout << "The median of the array is " << v[v.size() / 2];
  
    return 0;
}

Producción:

The median of the array is 33

Aquí la array ordenada será 2 3 10 23 33 45 47 56 60, por lo que hay 9 elementos y la mediana será el elemento del medio, es decir, el quinto elemento: 33.

Complejidad temporal de std::nth_element(): O(n), siendo n la distancia entre el primero y el último.
Artículos relacionados:

Este artículo es una contribución de Mrigendra Singh . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta