Sorting in C++

In order to sort a vector we can use sort() function from the Standard Library (std::sort), which sorts the elements of a given array in ascending order (default), descending order or user-defined order.

Syntax:

The syntax of the sort() function is:

void sort( RandomIt first, RandomIt last, Compare comp );

Let's see some examples below. Sorting an array of integers in ascending order

vector<int> numbers = {11, 3, 7, 5, 2};

sort(numbers.begin(), numbers.end()); // numbers becomes [2, 3, 5, 7, 11]

Sorting an array of integers in descending order

vector<int> numbers = {11, 3, 7, 5, 2};

sort(numbers.begin(), numbers.end(), greater<int>());

Sorting an array of Strings in descending order

vector<string> names = {"Mircea", "Andy", "Xavier", "Michael", "Christina"};

sort(names.begin(), names.end(), greater<string>());  // --> ['Xavier', 'Mircea', 'Michael', 'Christina', 'Andy']

Sort with custom function (comparator):

sort() function supports a basic comparison function that we can use to specify how we want to sort:

bool compare(int a, int b) {
    return a < b;
}

This can be written as a lambda function (nameless function we can easily pass to sort()) as follows:

[](int a, int b) -> bool {
    return a < b;
}

We can make it even shorter by dropping the return statement since sort() will expect a bool. Also we can generalize it by changing int to auto

[](auto a, auto b) {
    return a < b;
}

When the sort() function compares two values, it sends the values to the compare function, and sorts the values according to the returned value:

• If the result is true then a is sorted before b.
• If the result is false then b is sorted before a.

All we need to is using the compare function (as a lambda function) inside the sort() function:

vector<int> numbers = {3, 23, 12};

// using the short version of the lambda function
sort(numbers.begin(), numbers.end(), [](auto a, auto b) { return a < b; }); // --> 3, 12, 23

To demonstrate a basic example, let’s assume the requirement for ordering a specific list is the length of the strings in the list, shortest to longest. We will be using the size() method of each string to compare them.

vector<string> words = {"banana", "pie", "Washington", "book"};

sort(words.begin(), words.end(), [](auto a, auto b) -> a.size() < b.size()); // --> ['pie', 'book', 'banana', 'Washington']

Example: sorting array of pairs

Let's say we want to sort an array, where each element is another array consisting of two numbers.

vector<vector<int>> pairs = {{1, 5}, {12, 5}, {10, 1}, {1, 3}};

sort(pairs.begin(), pairs.end(), [](auto a, auto b) {
    // in case the first values of each pair are equal,
    // compare them using their second values
    if (a[0] == b[0]) {
        return a[1] - b[1];
    }
    return a[0] - b[0];
});
// pairs --> [[1, 3], [1, 5], [10, 1], [12, 5]]

Time Complexity:

Sorting an array via Arrays.sort() takes O(n * log n * C) time, where C is the time taken to compare two elements from the array.

It takes O(1) (constant time) to compare two numbers, therefore sorting an array of numbers takes O(n log n).

However, it takes O(L) to compare two strings, therefore sorting an array of strings takes O(n * log n * L), where L is the average length of the strings.

Space Complexity:

The sort() method sorts the elements of an array in place (transforms the array directly, using no auxiliary data structure), so the extra space used for this is O(1).

Assignment
Follow the Coding Tutorial and let's sort some arrays.

Hint
Look at the examples above if you get stuck.