Standard C library provides qsort function that can be used for sorting an array. Following is the prototype of qsort() function.
// 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*));
It requires a pointer to the array, the number of elements in the array, the size of each element and a comparator function. We have discussed qsort comparator in detail here.
C++ Standard Library provides a similar function sort() that originated in the STL. We have discussed C++ sort here. Following are prototypes of C++ sort() function.
// 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);
The order of equal elements is not guaranteed to be preserved. C++ provides std::stable_sort that can be used to preserve order.
Comparison to qsort and sort()
1. Implementation details:
As the name suggests, qsort function uses QuickSort algorithm to sort the given array, although the C standard does not require it to implement quicksort.
C++ sort function uses introsort which is a hybrid algorithm. Different implementations use different algorithms. The GNU Standard C++ library, for example, uses a 3-part hybrid sorting algorithm: introsort is performed first (introsort itself being a hybrid of quicksort and heap sort) followed by an insertion sort on the result.
2. Complexity :
The C standard doesn’t talk about its complexity of qsort. The new C++11 standard requires that the complexity of sort to be O(Nlog(N)) in the worst case. Previous versions of C++ such as C++03 allow possible worst case scenario of O(N^2). Only average complexity was required to be O(N log N).
3. Running time:
STL’s sort ran faster than C’s qsort, because C++’s templates generate optimized code for a particular data type and a particular comparison function.
STL’s sort runs 20% to 50% faster than the hand-coded quicksort and 250% to 1000% faster than the C qsort library function. C might be the fastest language but qsort is very slow.
When we tried to sort one million integers on C++14, Time taken by C qsort() was 0.247883 sec and time taken by C++ sort() was only 0.086125 sec
Time taken by C qsort() - 0.247883 Time taken by C++ sort() - 0.086125
C++ sort() is blazingly faster than qsort() on equivalent data due to inlining. sort() on a container of integers will be compiled to use std::less
STL’s sort works for all data types and for different data containers like C arrays, C++ vectors, C++ deques, etc and other containers that can be written by the user. This kind of flexibility is rather difficult to achieve in C.
Compared to qsort, the templated sort is more type-safe since it does not require access to data items through unsafe void pointers, as qsort does.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above