Clasificación en la biblioteca de plantillas estándar(STL) de C++

1. Use la función sort() para ordenar matrices o contenedores STL en C++
2. Ordenar el array en orden descendente en C++
3. Use la función partial_sort() para ordenar una parte de un array o vector
4. Clasificación personalizada o definida por el usuario mediante la función sort() en C++
5. Usa el método is_sorted() en C++
6. Complejidad temporal de los algoritmos de clasificación

En este tutorial, aprenderemos sobre una función de C++ ampliamente utilizada llamada sort(). También veremos otras funciones relacionadas con la clasificación.

Para ordenar datos en C++, escribimos nuestro algoritmo y lo aplicamos a los datos, o podemos usar la función integrada sort() presente en C++ STL. La función sort() se define en el archivo de cabecera algorithm.

Esta función utiliza el algoritmo IntroSort, un algoritmo de clasificación híbrido que utiliza tres algoritmos de clasificación, Quicksort, Heapsort y Insertion sort, para minimizar el tiempo de ejecución.

Esta función ordena los elementos del rango dado.

Sintaxis:

sort(start iterator, end iterator, compare_function)

Esto ordena los elementos en el rango definido por el iterador de inicio y el iterador final en orden ascendente de forma predeterminada (esta es la función de comparación predeterminada).

Use la función sort() para ordenar matrices o contenedores STL en C++

La clasificación es una de las operaciones fundamentales que se realiza sobre los datos. Organizamos los datos de manera creciente, decreciente o definida por el usuario (clasificación personalizada).

Podemos ordenar un array o contenedores STL como vector, set, map, etc., en C++ usando la función sort().

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};

  // array size
  int n = sizeof(arr) / sizeof(arr[0]);

  vector<int> v{35, 67, 11, -9, 7, -22};  // vector

  cout << "The array  after sorting is : \n";

  sort(arr, arr + n);
  sort(v.begin(), v.end());  // sorting vector

  for (int i = 0; i < n; ++i) cout << arr[i] << " ";

  cout << endl;

  cout << "The vector after sorting is : \n";
  for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}

Producción :

The array  after sorting is :
0 1 2 3 4 5 6 7 8 9
The vector after sorting is :
-22 -9 7 11 35 67

Los elementos se organizan en orden ascendente de forma predeterminada.

Ordenar el array en orden descendente en C++

Para ordenar arrays o contenedores presentes en C++ STL en orden decreciente, tenemos que pasar un tercer parámetro llamado greater<type>() en la función sort(). Esta función realiza una comparación para que los elementos al final se clasifiquen en orden descendente.

El Tipo se refiere al tipo de arreglo o contenedor que estamos usando, tipo int, float o string.

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};

  // array size
  int n = sizeof(arr) / sizeof(arr[0]);

  vector<int> v{35, 67, 11, -9, 7, -22};  // vector

  cout << "The array  after sorting is : \n";

  sort(arr, arr + n, greater<int>());
  sort(v.begin(), v.end(), greater<int>());  // sorting vector

  for (int i = 0; i < n; ++i) cout << arr[i] << " ";

  cout << endl;

  cout << "The vector after sorting is : \n";
  for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}

Producción :

The array  after sorting is :
9 8 7 6 5 4 3 2 1 0
The vector after sorting is :
67 35 11 7 -9 -22

Use la función partial_sort() para ordenar una parte de un array o vector

Podemos usar partial_sort() para ordenar solo una parte de un array. Este método no es más que una variante del método de clasificación original.

Sintaxis:

partial_sort(first, middle, last)

Reorganiza los elementos en el rango (first, last) para que los elementos antes del medio se clasifiquen en orden ascendente y los elementos después del medio se dejen sin ningún orden específico.

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  vector<int> vr{35, 67, 11, -9, 7, -22};  // vector

  cout << "The vector after partial sorting is : \n";

  partial_sort(vr.begin(), vr.begin() + 2, vr.end());

  for (int i = 0; i < vr.size(); ++i) cout << vr[i] << " ";
}

Producción :

The vector after partial sorting is :
-22 -9 67 35 11 7

Podemos observar que solo los primeros dos elementos están ordenados, los restantes están presentes en algún orden aleatorio.

Clasificación personalizada o definida por el usuario mediante la función sort() en C++

Siempre que queramos ordenar los datos en orden ascendente o descendente, podemos usar esta función, pero hay momentos en los que queremos que los datos se ordenen de una manera definida por el usuario.

Aquí tenemos que escribir nuestra función de ordenación personalizada, que pasaremos como tercer parámetro en la función sort().

#include <algorithm>
#include <iostream>
using namespace std;

bool myfunction(string x, string y) { return x.size() < y.size(); }

int main() {
  string str[] = {"a", "abc", "ba", "abcd"};
  int n = 4;

  sort(str, str + n);  // normal sort function
  cout << "Array after sorting : \n";
  for (int i = 0; i < n; ++i) cout << str[i] << " ";

  cout << endl;

  sort(str, str + n, myfunction);
  cout << "Array after user defined sorting : \n";
  for (int i = 0; i < n; ++i) cout << str[i] << " ";
}

Producción :

Array after sorting :
a abc abcd ba
Array after user defined sorting :
a ba abc abcd

El primer método de clasificación clasifica el array de cadenas en orden lexicográfico ascendente de forma predeterminada. El segundo método de clasificación clasifica las cadenas en función de su longitud, es decir, la condición que hemos mencionado en nuestra función de comparación personalizada llamada myfunction.

Usa el método is_sorted() en C++

Si queremos verificar si el rango de datos dado está ordenado o no, podemos usar este método.

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  vector<int> v{35, 67, 11, -9, 7, -22};  // vector

  cout << is_sorted(v.begin(), v.end());
}

Producción :

0

Dado que el vector no está ordenado, obtenemos la salida como 0, que significa false.

Complejidad temporal de los algoritmos de clasificación

El sort() tiene una complejidad temporal de O(NlogN), donde N es el número de elementos sobre los que se aplica la función sort().