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.

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:
XDR solutions

The Benefits of Using XDR Solutions

Cybercriminals constantly adapt their strategies, developing newer, more powerful, and intelligent ways to attack your network. Since security professionals must innovate as well, more conventional endpoint detection solutions have evolved

AI is revolutionizing fraud detection

How AI is Revolutionizing Fraud Detection

Artificial intelligence – commonly known as AI – means a form of technology with multiple uses. As a result, it has become extremely valuable to a number of businesses across

AI innovation

Companies Leading AI Innovation in 2023

Artificial intelligence (AI) has been transforming industries and revolutionizing business operations. AI’s potential to enhance efficiency and productivity has become crucial to many businesses. As we move into 2023, several

data fivetran pricing

Fivetran Pricing Explained

One of the biggest trends of the 21st century is the massive surge in analytics. Analytics is the process of utilizing data to drive future decision-making. With so much of

kubernetes logging

Kubernetes Logging: What You Need to Know

Kubernetes from Google is one of the most popular open-source and free container management solutions made to make managing and deploying applications easier. It has a solid architecture that makes

ransomware cyber attack

Why Is Ransomware Such a Major Threat?

One of the most significant cyber threats faced by modern organizations is a ransomware attack. Ransomware attacks have grown in both sophistication and frequency over the past few years, forcing

data dictionary

Tools You Need to Make a Data Dictionary

Data dictionaries are crucial for organizations of all sizes that deal with large amounts of data. they are centralized repositories of all the data in organizations, including metadata such as