Reading time: 45 minutes | Coding time: 20 minutes

Although one can sort a vector manually using one of the many available sorting algorithms, using a function from the C++ STL(Standard Template Library) can make the job easier.

The function used is the std::sort defined in the algorithm header. This sort() uses the introsort algorithm which is a hybrid sorting algorithm that uses quick sort, heap sort and insertion sort. It begins with quicksort, it switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted and it switches to insertion sort when the number of elements is below some threshold. This combines the good parts of the three algorithms, with practical performance comparable to quicksort on typical data sets and worst-case O(nlogn) runtime due to the heap sort. Since the three algorithms it uses are comparison sorts, it is also a comparison sort.

The basic syntax of this function is:

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

and the class definition is as follows:

template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);
    
template <class RandomAccessIterator, class Compare>    
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

The sort(), sorts from first to last index.

The different ways to sort a vector in C++ are:

• Ascending order
• Descending order
• Custom comparison function
• Using a lambda to sort
• Sorting only specific elements in a vector
  • basic method
  • std::nth_element()
  • std::nth_element() + comp
• 2D matrix
  • sort a specific row
  • sort a specific column

We will, now, go through each technique in detail.

1) Ascending order

The basic syntax is:

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

Go through this example to understand the process:

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

int main() 
{ 
vector<int> v{ 12, 56, 33, 2, 10, 5, 7 }; 

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

cout << "Sorted vector is \n"; 
for (int i=0; i<v.size(); i++) 
    cout << v[i] << " "; 

return 0; 
} 

Output

Sorted vector is
2 5 7 10 12 33 56

The sort() also takes a third parameter to change the order of the numbers

2) Descending order

greater<int>() can be used, as the third parameter to sort the vector in a decreasing order. It will be used as:

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

Go through this example to understand the process:

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

int main() 
{ 
    vector<int> v{ 12, 56, 33, 2, 10, 5, 7 };   
    sort(v.begin(), v.end(), greater<int>());  
    cout << "Sorted vector is \n"; 
    for (int i=0; i<v.size(); i++) 
        cout << v[i] << " ";   
    return 0; 
}

Output

Sorted vector is
56 33 12 10 7 5 2

Using a comp function

This is a user defined comparator function, where the user can define the way they want to sort the data. We can use the same function to sort the vector in a decreasing order without using the greater<int>()

The syntax is as follows:

bool cmp(int a, int b)
{
    return a>b;
}

sort(v.begin(), v.end() , cmp);

Go through this example to understand the process:

#include <iostream> 
#include <algorithm> 
using namespace std; 
bool cmp(int a, int b)
{
    return a>b;
}
int main() 
{ 
    vector<int> v{ 12, 56, 33, 2, 10, 5, 7 }; 
    sort(v.begin(), v.end() , cmp); 
    cout << "Sorted vector is \n"; 
    for (int i=0; i<v.size(); i++) 
        cout << v[i] << " "; 
    return 0; 
}

Output

Sorted vector is
56 33 12 10 7 5 2

This cmp becomes extremely useful when one has to compare a vector of pairs, or any such combinational data types.

Using a lambda to sort

With C++ 11 we can pass lambda to a sort function. In the given example we simply sorted the data in decreasing order but without passing a third argument, we passed the lambda that took care of it.

Lambda is an inline function that can be used for short snippets of code that are not going to be reused. The return type of this function is evaluated by the compiler. It is used as follows:

sort(v.begin(), v.end() ,
            [](const int &a, const int &b {
            return a>b; });

Go through this example to understand the process:

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

bool cmp(int a, int b)
{
    return a>b;
}

int main() 
{ 
    vector<int> v{ 12, 56, 33, 2, 10, 5, 7 };   
    sort(v.begin(), v.end() ,
            [](const int &a, const int &b {
            return a>b; }); 

    cout << "Sorted vector is \n"; 
    for (int i=0; i<v.size(); i++) 
        cout << v[i] << " "; 

    return 0;
}

Output

Sorted vector is
56 33 12 10 7 5 2

Sorting only specific elements in a vector

Ex: v = {12, 56, 33, 2, 10, 5, 7}

Syntax:

std::sort (myvector.begin(), myvector.begin()+4);           //(12 56 33 2)10 5 7
std::sort (myvector.begin()+4, myvector.end());             // 12 56 33 (2 10 5 7)

std::nth_element()

This function does not sort the entire vector, only sorts in such a way that the nth element in the vector if sorted will be in place, and all

template <class RandomAccessIterator>
  void nth_element (RandomAccessIterator first, RandomAccessIterator nth,                     RandomAccessIterator last);

with comparator function	
template <class RandomAccessIterator, class Compare>
  void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last, Compare comp);

Go through this complete example to understand the process better:

    #include <iostream> 
    #include <algorithm> 
    using namespace std; 
    int main() 
    { 
    int v[] = { 12, 56, 33, 2, 10, 5, 7}, i; 
  
    // Using std::nth_element with n as 5 
    std::nth_element(v, v + 4, v + 7); 
  
    // Since, n is 5 so 5th element should be sorted 
    for (i = 0; i < 7; ++i) { 
        cout << v[i] << " "; 
    } 
    return 0; 
    }

Output

12 5 7 2 10 33 56

Using a cmp function

The basic syntax is as follows:

std::nth_element(v, v + 4, v + 7, comp);

Go through this complete example to understand the process better:

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

bool comp(int a, int b) 
{ 
    return (a < b); 
} 
int main() 
{ 
    int v[] = { 12, 56, 33, 2, 10, 5, 7}, i; 

    // Using std::nth_element with n as 6 
    std::nth_element(v, v + 4, v + 7, comp); 

    // Since, n is 6 so 6th element should be the same 
    // as the sixth element present if we sort this array 
    // Sorted Array 
    for (i = 0; i < 7; ++i) { 
        cout << v[i] << " "; 
} 
return 0; 
}

Output

12 5 7 2 10 33 56

3) sorting a 2D vector

A 2D vector is vector of vectors. It is an matrix implemented with the help of vectors.
The syntax of the function is pretty much the same, however since the vector is 2D, we can change the order in many ways (row sorted, column sorted, size sorted etc)

sorting based on a particular row

Sorting a specific row is simple as we can directly specify row in the sort method as follows:

sort(v[row_number].begin(), v[row_number].end()); 

Go through this complete example to understand the process better:

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

int main() 
{ 

vector< vector<int> > v {{4, 2, 9}, 
                           {-4, 82, 33}, 
                           {12, 44, 0}}; 
// Number of rows; 
int m = v.size(); 

// Number of columns assuming it’s a square matrix
int n = v[0].size(); 

cout << "The Matrix before sorting 3rd row is:\n"; 
for (int i=0; i<m; i++) 
{ 
    for (int j=0; j<n ;j++) 
       cout << v[i][j] << " "; 
    cout << endl; 
} 

sort(v[2].begin(), v[2].end()); 

cout << "The Matrix after sorting 3rd row is:\n"; 
for (int i=0; i<m; i++) 
{ 
    for (int j=0; j<n ;j++) 
        cout << v[i][j] << " "; 
    cout << endl; 
} 

return 0; 
}

Output:

The Matrix before sorting 3rd row is:

4 2 9
-4 82 33 
12 44 0 

The Matrix after sorting 3rd row is:

4 2 9
-4 82 33 
0 12 44

sorting a column in 2D matrix

We can take help from the comparator function to sort a single column in a 2D matrix. The basic syntax is as follows:

bool sortByCol( const vector<int>& v1, 
           const vector<int>& v2 ) { 
 return v1[column_number] < v2[column_number]; 
}

sort(v.begin(), v.end(), sortByCol); 

Go through this example to understand the process:

#include<iostream> 
#include<vector> 
#include<algorithm>  
using namespace std; 
  bool sortByCol( const vector<int>& v1, 
           const vector<int>& v2 ) { 
 return v1[2] < v2[2]; 
}
int main() 
{ 

vector< vector<int> > v {{4, 2, 9}, 
                           {-4, 82, 33}, 
                           {12, 44, 0}}; 
// Number of rows; 
int m = v.size(); 

// Number of columns assuming it’s a square matrix
int n = v[0].size(); 

cout << "The Matrix before sorting 3rd column is:\n"; 
for (int i=0; i<m; i++) 
{ 
    for (int j=0; j<n ;j++) 
       cout << v[i][j] << " "; 
    cout << endl; 
} 

sort(v.begin(), v.end(), sortByCol); 

cout << "The Matrix after sorting 3rd column is:\n"; 
for (int i=0; i<m; i++) 
{ 
    for (int j=0; j<n ;j++) 
        cout << v[i][j] << " "; 
    cout << endl; 
} 

return 0; 
}

Output:

The Matrix before sorting 3rd row is:
4 2 9
-4 82 33 
12 44 0 

The Matrix after sorting 3rd row is:
4 2 0
-4 82 9 
12 44  33

Time Complexity

std::sort have average case linearithmic (n log n) time complexity, where n being distance between first to last.

std::nth_element(): O(n), with n being the distance between first and the last.

Applications

Sorting forms a core building block in structuring algorithms to solve the problems of data in real world by sorting the given data according to the requirements.

Question

With this, you will have the complete knowledge of sorting a vector in any way. Enjoy.