C qsort() frente a C++ sort()

La biblioteca C estándar proporciona la función qsort que se puede usar para ordenar una array. A continuación se muestra el prototipo de la función qsort().

// Sort an array of any type. The parameters are, base
// address of array, size of array and pointer to
// comparator function
void qsort (void* base, size_t num, size_t size, 
            int (*comparator)(const void*, const void*));

Requiere un puntero a la array, el número de elementos de la array, el tamaño de cada elemento y una función de comparación. Hemos discutido el comparador qsort en detalle aquí .

La biblioteca estándar de C++ proporciona una función similar sort() que se originó en STL. Hemos discutido la ordenación de C++ aquí . Los siguientes son prototipos de la función sort() de C++.

// To sort in default or ascending order.
template 
void sort(T first, T last);

// To sort according to the order specified
// by comp.
template
void sort(T first, T last, Compare comp);

No se garantiza que se conserve el orden de los elementos iguales. C++ proporciona std::stable_sort que se puede usar para preservar el orden.

Comparación con qsort y sort()
1. Detalles de implementación:
como sugiere el nombre, la función qsort usa el algoritmo QuickSort para ordenar la array dada, aunque el estándar C no lo requiere para implementar la ordenación rápida.

La función de ordenación de C++ utiliza introsort, que es un algoritmo híbrido. Diferentes implementaciones usan diferentes algoritmos. La biblioteca GNU Standard C++, por ejemplo, utiliza un algoritmo de clasificación híbrido de 3 partes: la introclasificación se realiza primero (la introclasificación en sí misma es un híbrido de clasificación rápida y clasificación en montón) seguido de una clasificación por inserción en el resultado.

2. Complejidad:
el estándar C no habla de su complejidad de qsort. El nuevo estándar C++11 requiere que la complejidad de clasificación sea O(Nlog(N)) en el peor de los casos. Las versiones anteriores de C++, como C++ 03, permiten el peor de los casos posibles de O (N ^ 2). Solo se requería que la complejidad promedio fuera O (N log N).

3. Tiempo de ejecución:
la ordenación de STL se ejecutó más rápido que la qsort de C, porque las plantillas de C++ generan código optimizado para un tipo de datos particular y una función de comparación particular.

La clasificación de STL se ejecuta entre un 20 % y un 50 % más rápido que la clasificación rápida codificada a mano y entre un 250 % y un 1000 % más rápida que la función de biblioteca C qsort. C puede ser el lenguaje más rápido pero qsort es muy lento.

Cuando intentamos clasificar un millón de enteros en C++ 14, el tiempo que tardó C qsort() fue de 0,247883 segundos y el tiempo que tardó C++ sort() fue de solo 0,086125 segundos

// C++ program to demonstrate performance of
// C qsort and C++ sort() algorithm
#include <bits/stdc++.h>
using namespace std;
  
// Number of elements to be sorted
#define N 1000000
  
// A comparator function used by qsort
int compare(const void * a, const void * b)
{
    return ( *(int*)a - *(int*)b );
}
  
// Driver program to test above functions
int main()
{
    int arr[N], dupArr[N];
  
    // seed for random input
    srand(time(NULL));
  
    // to measure time taken by qsort and sort
    clock_t begin, end;
    double time_spent;
  
    // generate random input
    for (int i = 0; i < N; i++)
        dupArr[i] = arr[i] = rand()%100000;
  
    begin = clock();
    qsort(arr, N, sizeof(int), compare);
    end = clock();
  
    // calculate time taken by C qsort function
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  
    cout << "Time taken by C qsort() - "
         << time_spent << endl;
  
    time_spent = 0.0;
  
    begin = clock();
    sort(dupArr, dupArr + N);
    end = clock();
  
    // calculate time taken by C++ sort
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  
    cout << "Time taken by C++ sort() - "
         << time_spent << endl;
  
    return 0;
}

Producción :

Time taken by C qsort() - 0.247883
Time taken by C++ sort() - 0.086125 

C++ sort() es increíblemente más rápido que qsort() en datos equivalentes debido a la inserción. sort() en un contenedor de enteros se compilará para usar std::less::operator() por defecto, que estará en línea y sort() comparará los enteros directamente. Por otro lado, qsort() realizará una llamada indirecta a través de un puntero de función para cada comparación que los compiladores no puedan optimizar.

4. Flexibilidad:
la clasificación de STL funciona para todos los tipos de datos y para diferentes contenedores de datos como arrays C, vectores C++, deques C++, etc. y otros contenedores que puede escribir el usuario. Este tipo de flexibilidad es bastante difícil de lograr en C.

5. Seguridad:
en comparación con qsort, la ordenación con plantilla es más segura, ya que no requiere acceso a elementos de datos a través de punteros vacíos inseguros, como lo hace qsort.

Referencias:
http://theory.stanford.edu/~amitp/rants/c++-vs-c
https://en.wikipedia.org/wiki/Sort_(C%2B%2B)

Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico 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.