Detalles internos de std::sort() en C++

La clasificación es una de las funciones más básicas aplicadas a los datos. Significa organizar los datos de una manera particular, que puede ser creciente o decreciente. Hay una función integrada en C++ STL con el nombre de sort(). 

std::sort() es una función genérica en la biblioteca estándar de C++, para hacer una clasificación comparativa.  

Sintaxis: 

sort(startaddress, endaddress, comparator)

where:
startaddress: the address of the first element of the array
endaddress: the address of the last element of the array
comparator: the comparison to be done with the array. 
            This argument is optional. 

Ejemplo:

// C++ program to demonstrate
// behaviour of sort() in STL.
 
#include <bits/stdc++.h>
using namespace std;
   
int main()
{
    int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
   
    sort(arr, arr+n);
   
    cout << "\nArray after sorting using "
         "default sort is : \n";
 
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
   
    return 0;
}

Array after sorting using default sort is : 
0 1 2 3 4 5 6 7 8 9

Complejidad del tiempo

• Mejor caso: O (N log N)
• Caso Promedio- O(N log N)
• Peor caso: O (N log N)

donde, N = número de elementos a ordenar. 

Algoritmos usados ​​por sort()

El algoritmo utilizado por sort() es IntroSort . Introsort, que es un algoritmo de clasificación híbrido, utiliza tres algoritmos de clasificación para minimizar el tiempo de ejecución, Quicksort , Heapsort y Insertion Sort . En pocas palabras, es el mejor algoritmo de clasificación que existe. Es un algoritmo de clasificación híbrido, lo que significa que utiliza más de un algoritmo de clasificación como rutina. 

/* A Program to sort the array using Introsort.
  The most popular C++ STL Algorithm- sort()
  uses Introsort. */
 
#include<bits/stdc++.h>
using namespace std;
 
// A utility function to swap the values pointed by
// the two pointers
void swapValue(int *a, int *b)
{
    int *temp = a;
    a = b;
    b = temp;
    return;
}
 
/* Function to sort an array using insertion sort*/
void InsertionSort(int arr[], int *begin, int *end)
{
    // Get the left and the right index of the subarray
    // to be sorted
    int left = begin - arr;
    int right = end - arr;
 
    for (int i = left+1; i <= right; i++)
    {
        int key = arr[i];
        int j = i-1;
 
       /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
        while (j >= left && arr[j] > key)
        {
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = key;
   }
 
   return;
}
 
// A function to partition the array and return
// the partition point
int* Partition(int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element
 
    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            // increment index of smaller element
            i++;
 
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (arr + i + 1);
}
 
 
// A function that find the middle of the
// values pointed by the pointers a, b, c
// and return that pointer
int *MedianOfThree(int * a, int * b, int * c)
{
    if (*a < *b && *b < *c)
        return (b);
 
    if (*a < *c && *c <= *b)
        return (c);
 
    if (*b <= *a && *a < *c)
        return (a);
 
    if (*b < *c && *c <= *a)
        return (c);
 
    if (*c <= *a && *a < *b)
        return (a);
 
    if (*c <= *b && *b <= *c)
        return (b);
}
 
// A Utility function to perform intro sort
void IntrosortUtil(int arr[], int * begin,
                  int * end, int depthLimit)
{
    // Count the number of elements
    int size = end - begin;
 
      // If partition size is low then do insertion sort
    if (size < 16)
    {
        InsertionSort(arr, begin, end);
        return;
    }
 
    // If the depth is zero use heapsort
    if (depthLimit == 0)
    {
        make_heap(begin, end+1);
        sort_heap(begin, end+1);
        return;
    }
 
    // Else use a median-of-three concept to
    // find a good pivot
    int * pivot = MedianOfThree(begin, begin+size/2, end);
 
    // Swap the values pointed by the two pointers
    swapValue(pivot, end);
 
   // Perform Quick Sort
    int * partitionPoint = Partition(arr, begin-arr, end-arr);
    IntrosortUtil(arr, begin, partitionPoint-1, depthLimit - 1);
    IntrosortUtil(arr, partitionPoint + 1, end, depthLimit - 1);
 
    return;
}
 
/* Implementation of introsort*/
void Introsort(int arr[], int *begin, int *end)
{
    int depthLimit = 2 * log(end-begin);
 
    // Perform a recursive Introsort
    IntrosortUtil(arr, begin, end, depthLimit);
 
      return;
}
 
// A utility function ot print an array of size n
void printArray(int arr[], int n)
{
   for (int i=0; i < n; i++)
       printf("%d ", arr[i]);
   printf("\n");
}
 
// Driver program to test Introsort
int main()
{
    int arr[] = {3, 1, 23, -9, 233, 23, -313, 32, -9};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Pass the array, the pointer to the first element and
    // the pointer to the last element
    Introsort(arr, arr, arr+n-1);
    printArray(arr, n);
 
    return(0);
}

-313 -9 -9 1 3 23 23 32 233

La biblioteca C estándar proporciona qsort() que se puede usar para ordenar una array. Como sugiere el nombre, la función usa el algoritmo QuickSort para ordenar la array dada 

Es mejor usar sort() en lugar de qsort() porque: 

1. sort() no usa punteros vacíos inseguros como qsort().
2. qsort() realiza una gran cantidad de llamadas de función para la función de comparación en comparación con sort().
3. El código C++ con sort() es relativamente más rápido que el código con qsort().

Artículo detallado: Comparación de sort() con qsort()