C++

Sorting C++ Vectors

The C++ vector is like an array with member functions (methods). The vector’s length can be increased or be decreased in the program execution. The vector has many member functions. Among all these member functions, non-sorts the vector. However, C++ has a library called the algorithm library. This library has a lot of general-purpose algorithmic functions. One of these is the sort() function. This function can be used to sort C++ containers such as the vector. All values of a vector are values of the same type.

A programmer can write his own sort() function. However, the sort() function from the algorithm library is likely to perform better than what the ordinary programmer writes.

The sort() function can sort the values of a vector in ascending order or in descending order. To sort a vector, the algorithm library has to be included. The vector library also has to be included. The beginning of the program should be something like:

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

The vector is actually a class, from which vector objects can be created. With the above top-section of the program, a vector to be sorted, can be created as follows:

vector <char> vtr = {'Z', 'X', 'C', 'V', 'B', 'N', 'M', 'A', 'S', 'D'};

The name of the class is a vector. The name of the instantiated object is vtr.

In this tutorial, sorting coding is done in the C++ main() function. This tutorial explains how to sort a C++ vector using the above vector, vtr.

Article Content

Default Sorting

Default sorting sorts in ascending order. The syntax for this is:

template<class RandomAccessIterator>

void sort(RandomAccessIterator first, RandomAccessIterator last);

Sorting the Whole Vector

The following code sorts the whole vector:

sort(vtr.begin(), vtr.end());

for (int i=0; i<vtr.size(); i++)

cout<<vtr[i]<<", ";

cout<<endl;

The unsorted list is:

Z, X, C, V, B, N, M, A, S, D

The sorted list is:

A, B, C, D, M, N, S, V, X, Z,

which is correct. If sorting is not correct, then the fault is that of the programmer and not that of the sort() function.

The RandomAccessIterator is intrinsic. vtr.begin() returns an iterator that points to the first element, and vtr.end() returns another iterator of the same type that points just after the last element. So there is no need to instantiate a vector indicating, RandomAccessIterator. In this way, the whole list is sorted.

Sorting a Range in Ascending Order

The unsorted list above has ten elements with indexes:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

To sort only the elements from position 4, which is index, 3 = 4 – 1, to position 9, which is index, 8 = 9 – 1, add 3 to vtr.begin() to have the first iterator, and then add 8 to vtr.begin() to have the last iterator, for the sort() function. The 9th element of index 8 will not be included in the sorting. That is, the last element indicated in the chosen range, is excluded for sorting. The following code illustrates this:

sort(vtr.begin() + 3, vtr.begin() + 8);

for (int i=0; i<vtr.size(); i++)

cout<<vtr[i]<<", ";

cout<<endl;

The unsorted list is:

Z, X, C, V, B, N, M, A, S, D
[/c]c
The sorted list is:
[cc lang="text" width="100%" height="100%" escaped="true" theme="blackboard" nowrap="0"]
Z, X, C, A, B, M, N, V, S, D,

The elements at positions 4, 5, 6, 7, 8 have been sorted. The element at the 9th position has not been included in the sort. These positions correspond to indexes 3, 4, 5, 6, 7. The element at index 8 has not been included in the sort.

So, to sort a range, identify the first and last elements in the range, not necessarily of the whole list. Add the index of the first element to the begin() iterator. Add the index of the last element, still to the begin() iterator. Remember that the last element for the range will not be included in the sort, but the first element for the range will be included.

Adding an index to an iterator is possible because adding a number is the same as incrementing the iterator that same number of times. Incrementing an iterator once makes it a point to the next element.

Sorting in Descending Order

The syntax is:

template<class RandomAccessIterator, class Compare>

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
[/c]
This differs from the above syntax with the presence of “Compare comp”. comp is a function pointer or a function object. comp actually decides whether the sorting should be ascending or descending. Its absence is the default case, which means descending.
<h3>Sorting the Whole List in Descending Order</h3>
The following code sorts the whole above vector in descending order:
[cc lang="c" width="100%" height="100%" escaped="true" theme="blackboard" nowrap="0"]
sort(vtr.begin(), vtr.end(), greater<char>());

for (int i=0; i<vtr.size(); i++)

cout<<vtr[i]<<", ";

cout<<endl;

The unsorted list is:

Z, X, C, V, B, N, M, A, S, D

The vector sorted in descending order is:

Z, X, V, S, N, M, D, C, B, A,

Note the use of “greater<char>()” in the place of comp.

The opposite of greater<char>() is less<char>(), which is the default (ascending), and does not have to be typed.

Sorting a Range in Descending Order

A range can be sorted in descending order as well as in ascending order. The following code sorts the 4th to the 9th element without including the 9th element; and descending.

sort(vtr.begin() + 3, vtr.begin() + 8, greater<char>());

for (int i=0; i<vtr.size(); i++)

cout<<vtr[i]<<", ";

cout<<endl;

The unsorted list is:

Z, X, C, V, B, N, M, A, S, D

The vector with its chosen range, sorted in descending order, is:

Z, X, C, V, N, M, B, A, S, D,

Custom Compare Function

The following program has custom compare function for ascending sort:

    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;

    vectorvtr = {'Z', 'X', 'C', 'V', 'B', 'N', 'M', 'A', 'S', 'D'};

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

    int main()
    {
        sort(vtr.begin(), vtr.end(), compare);

        for (int i=0; i<vtr.size(); i++)
cout<<vtr[i]<<", ";
cout<<endl;

        return 0;
    }

The function to do the comparison is called compare. It returns a bool. It has two parameters, a and b, of the same type, as the vector element type. It returns true if a is less than b and false otherwise. The name of this function is the third argument of the sort() function call. In this program, compare is the same as less<char>(). Some other names instead of compare can be used.

The unsorted list is:

Z, X, C, V, B, N, M, A, S, D

The sorted list is:

A, B, C, D, M, N, S, V, X, Z,

Of course the custom compare function can be used for a range. The following program illustrates this:

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

vectorvtr = {'Z', 'X', 'C', 'V', 'B', 'N', 'M', 'A', 'S', 'D'};

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

int main()
{
    sort(vtr.begin() + 3, vtr.begin() + 8, compare);

    for (int i=0; i<vtr.size(); i++)
cout<<vtr[i]<<", ";
cout<<endl;

    return 0;
}

The unsorted list is:

Z, X, C, V, B, N, M, A, S, D

The sorted list is:

Z, X, C, A, B, M, N, V, S, D,

The compare function can be coded for descending. The following program illustrates this:

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

vectorvtr = {'Z', 'X', 'C', 'V', 'B', 'N', 'M', 'A', 'S', 'D'};

bool compare (char a, char b) {
    return (a > b);
}

int main()
{
    sort(vtr.begin(), vtr.end(), compare);

    for (int i=0; i<vtr.size(); i++)
cout<<vtr[i]<<", ";
cout<<endl;

    return 0;
}

Just change (a < b) to (a > b).

The unsorted list is:

Z, X, C, V, B, N, M, A, S, D

The sorted list is:

Z, X, V, S, N, M, D, C, B, A,

The custom compare function can be used for a range, in descending order. The following program illustrates this:

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

vectorvtr = {'Z', 'X', 'C', 'V', 'B', 'N', 'M', 'A', 'S', 'D'};

bool compare (char a, char b) {
    return (a > b);
}

int main()
{
    sort(vtr.begin()+3, vtr.begin()+8, compare);

    for (int i=0; i<vtr.size(); i++)
cout<<vtr[i]<<", ";
cout<<endl;

    return 0;
}

The unsorted list is:

Z, X, C, V, B, N, M, A, S, D

The vector with its chosen range, sorted in descending order, is:

Z, X, C, V, N, M, B, A, S, D,

Other Data Types

Other data types can be sorted using their types. For example, if the int data type is to be sorted, then “int” would be used to create the vector and in the inbuilt or custom compare function. If the data type is in a library, then the library header has to be included in the program, as for the case of the string below:

#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

using namespace std;

vectorvtr = {"Ze", "Xe", "Ce", "Ve", "Be", "Ne", "Me", "Ae", "Se", "De"};

int main()
{
    sort(vtr.begin(), vtr.end(), greater());

    for (int i=0; i<vtr.size(); i++)
cout<<vtr[i]<<", ";
cout<<endl;

    return 0;
}

The unsorted list is:

Ze, Xe, Ce, Ve, Be, Ne, Me, Ae, Se, De

The sorted list is:

Ze, Xe, Ve, Se, Ne, Me, De, Ce, Be, Ae,

Conclusion

C++ comes with the algorithm library that has a sort() function. This function takes two or three arguments in its normal use. The first argument is wherein the vector-list, the sort should start. The second argument is wherein the vector-list, the sort should end. The third argument determines whether sorting is to be done in ascending order or in descending order.

About the author

Chrysanthus Forcha

Discoverer of mathematics Integration from First Principles and related series. Master’s Degree in Technical Education, specializing in Electronics and Computer Software. BSc Electronics. I also have knowledge and experience at the Master’s level in Computing and Telecommunications. Out of 20,000 writers, I was the 37th best writer at devarticles.com. I have been working in these fields for more than 10 years.