Using Sort with Arrays

sort, along with many other STL algorithms, works well with arrays. This is because the STL’s concept of an iterator is closely modelled on that of a pointer.

The STL provides two forms of sort. Both forms take an iterator pointing to the beginning of the collection to be sorted as their first argument and an iterator marking the end as their second argument. The iterator marking the end points one past the last element to be sorted. When sorting an array x, the first iterator is x, and the second iterator is x + n, where n is the length of the array.

The first form of sort takes no extra arguments. It uses the operator < for its comparisons. The second form of sort takes a function object as its third parameter, which it uses for its comparisons. The function object should return true if its first argument is less than its second. The function object may either be a function pointer or a functor, an instance of a class that overrides the () operator. An example of a functor is provided in the code below.

The major alternative to sort, other than writing your own sorting code, is C’s qsort. The STL’s sort functions offer a number of advantages over qsort including:

  • Better theoretical run time: sort is guaranteed to run in O(nlog(n)) time in the worst case whereas C’s qsort runs in O(n^2) time in the worst case.
  • Better run time in practice: C’s qsort requires a function pointer whereas the second form of sort may take a functor (and the first form in effect always does). Function calls via a function pointer are much less likely to be inlined than functor calls; the compiler tends to do a better job optimizing code using STL’s sort.
  • Less code to write: When using C’s qsort, you will almost invariably have to write your own comparison function. With STL’s sort on the other hand, if the operator < is already defined for your data type, there’s no need to do any extra coding. For example, you can sort an array of int in one line: sort(x, x + n).
  • Type-safety: C’s qsort requires you to provide a function that takes void*, which in turn requires your code to cast from void*. There is no need to do any casting when writing code to use STL’s sort.

This example code sorts an array of C-strings:

#include  //for strcmp#include  //for sort#include using namespace std;class CStringCompare {   public://Return true if s1 < s2; otherwise, return false.bool operator()(const char* s1, const char* s2) {    return strcmp(s1, s2) < 0;}};int main(int numberOfArgs, char** args) {    sort(args, args + numberOfArgs, CStringCompare());    for (int i = 0; i < numberOfArgs; ++i) {        cout << args[i] << endl;    }    return 0;}

Here's some example compilation and output:

% g++ sort_arrays.cpp% ./a.out g e s 3 c a j k b./a.out3abcegjks%
Share the Post:
Share on facebook
Share on twitter
Share on linkedin


The Latest

Top 5 B2B SaaS Marketing Agencies for 2023

In recent years, the software-as-a-service (SaaS) sector has experienced exponential growth as more and more companies choose cloud-based solutions. Any SaaS company hoping to stay ahead of the curve in this quickly changing industry needs to invest in effective marketing. So selecting the best marketing agency can mean the difference

technology leadership

Why the World Needs More Technology Leadership

As a fact, technology has touched every single aspect of our lives. And there are some technology giants in today’s world which have been frequently opined to have a strong influence on recent overall technological influence. Moreover, those tech giants have popular technology leaders leading the companies toward achieving greatness.

iOS app development

The Future of iOS App Development: Trends to Watch

When it launched in 2008, the Apple App Store only had 500 apps available. By the first quarter of 2022, the store had about 2.18 million iOS-exclusive apps. Average monthly app releases for the platform reached 34,000 in the first half of 2022, indicating rapid growth in iOS app development.