Using Sort with Arrays

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.
See also  5 Ways to Improve Customer Experience

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%

About Our Editorial Process

At DevX, we’re dedicated to tech entrepreneurship. Our team closely follows industry shifts, new products, AI breakthroughs, technology trends, and funding announcements. Articles undergo thorough editing to ensure accuracy and clarity, reflecting DevX’s style and supporting entrepreneurs in the tech sphere.

See our full editorial policy.

About Our Journalist