How to Sorting in C++ Standard Template Library (STL)

1. Use the sort() Function to Sort Array or STL Containers in C++
2. Sort the Array in Descending Order in C++
3. Use the partial_sort() Function to Sort a Part of an Array or Vector
4. User-Defined or Custom Sort Using the sort() Function in C++
5. Use the is_sorted() Method in C++
6. Time Complexity of Sorting Algorithms

In this tutorial, we’ll learn about a widely used C++ function called sort(). We’ll also look at other functions which are related to sorting.

To sort data in C++, we write our algorithm and apply it to data, or we can use the built-in function sort() present in C++ STL. The sort() function is defined in the algorithm header file.

This function uses the IntroSort algorithm, a hybrid sorting algorithm that uses three sorting algorithms, Quicksort, Heapsort, and Insertion sort, to minimize the running time.

This function sorts the elements of the given range.

Syntax:

sort(start iterator, end iterator, compare_function)

This sorts the elements in the range defined by the start iterator and end iterator in ascending order by default (this is the default compare_function).

Use the sort() Function to Sort Array or STL Containers in C++

Sorting is one of the fundamental operations which is performed on data. We arrange data increasing, decreasing, or user-defined (custom sort) manner.

We can sort an array or STL containers like vector, set, map, etc., in C++ using the sort() function.

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

int main() {
  int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};

  // array size
  int n = sizeof(arr) / sizeof(arr[0]);

  vector<int> v{35, 67, 11, -9, 7, -22};  // vector

  cout << "The array  after sorting is : \n";

  sort(arr, arr + n);
  sort(v.begin(), v.end());  // sorting vector

  for (int i = 0; i < n; ++i) cout << arr[i] << " ";

  cout << endl;

  cout << "The vector after sorting is : \n";
  for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}

Output:

The array  after sorting is :
0 1 2 3 4 5 6 7 8 9
The vector after sorting is :
-22 -9 7 11 35 67

The items are arranged in ascending order by default.

Sort the Array in Descending Order in C++

To sort array or containers present in C++ STL in decreasing order, we have to pass a third parameter called greater<type>() in the sort() function. This function performs comparison so that elements at the end are sorted in descending order.

The Type refers to the type of array or container we are using, int, float, or string type.

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

int main() {
  int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};

  // array size
  int n = sizeof(arr) / sizeof(arr[0]);

  vector<int> v{35, 67, 11, -9, 7, -22};  // vector

  cout << "The array  after sorting is : \n";

  sort(arr, arr + n, greater<int>());
  sort(v.begin(), v.end(), greater<int>());  // sorting vector

  for (int i = 0; i < n; ++i) cout << arr[i] << " ";

  cout << endl;

  cout << "The vector after sorting is : \n";
  for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}

Output:

The array  after sorting is :
9 8 7 6 5 4 3 2 1 0
The vector after sorting is :
67 35 11 7 -9 -22

Use the partial_sort() Function to Sort a Part of an Array or Vector

We can use partial_sort() to sort just some part of an array. This method is nothing but a variant of the original sort method.

Syntax:

partial_sort(first, middle, last)

It re-arranges the elements in the range (first, last) so that the elements before the middle are sorted in ascending order and the elements after the middle are left without any specific order.

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

int main() {
  vector<int> vr{35, 67, 11, -9, 7, -22};  // vector

  cout << "The vector after partial sorting is : \n";

  partial_sort(vr.begin(), vr.begin() + 2, vr.end());

  for (int i = 0; i < vr.size(); ++i) cout << vr[i] << " ";
}

Output:

The vector after partial sorting is :
-22 -9 67 35 11 7

We can observe that only the first two elements are sorted remaining are just present in some random order.

User-Defined or Custom Sort Using the sort() Function in C++

As long as we want to sort the data in ascending or descending order, we can use this function, but there are times when we want the data to be sorted in a user-defined manner.

Here we have to write our custom sort function, which we will be passing as the third parameter in the sort() function.

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

bool myfunction(string x, string y) { return x.size() < y.size(); }

int main() {
  string str[] = {"a", "abc", "ba", "abcd"};
  int n = 4;

  sort(str, str + n);  // normal sort function
  cout << "Array after sorting : \n";
  for (int i = 0; i < n; ++i) cout << str[i] << " ";

  cout << endl;

  sort(str, str + n, myfunction);
  cout << "Array after user defined sorting : \n";
  for (int i = 0; i < n; ++i) cout << str[i] << " ";
}

Output:

Array after sorting :
a abc abcd ba
Array after user defined sorting :
a ba abc abcd

The first sort method sorts the array of strings lexicographically ascending order by default. The second sort method sorts the strings based on their length, i.e., the condition we have mentioned in our custom compare function named myfunction.

Use the is_sorted() Method in C++

If we want to check whether the given range of data is sorted or not, we can use this method.

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

int main() {
  vector<int> v{35, 67, 11, -9, 7, -22};  // vector

  cout << is_sorted(v.begin(), v.end());
}

Output:

0

Since the vector is not sorted, we get the output as 0, meaning false.

Time Complexity of Sorting Algorithms

The sort() has a time complexity of O(NlogN), where N is the number of elements on which the sort() function is applied.