Sort Function in Cpp in Particular Order
In this article, you will be learning about the sort function which can be used to sort data in any given range like arrays or vectors.
The sort function generally takes two parameters, the first parameter is the pointer pointing to the start of the range or the element from which the sorting needs to begin, and the second parameter is the length up to which we want the array/vector to be sorted. The third parameter is an optional one and can be used for different implementations of the sort function.
NOTE: By default, the sort function sorts the elements in ascending order.
Using the sort function to sort an Array
Let’s look at an example of how to use the sort function.
Example:
// C++ program to demonstrate default behaviour of
// sort() in STL.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
/*Here we take two parameters, the beginning of the
array and the length n up to which we want the array to
be sorted*/
sort(arr, arr + n);
cout << "\nArray after sorting using "
"default sort is : \n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;
}
Output:
Array after sorting using default sort is :
0 1 2 3 4 5 6 7 8 9
Let’s once again go through the code to better understand it.
We used the sizeof() function to find the number of elements in the array.
We did it by dividing the size of the array by the size of the individual elements of that array.
int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
int n = sizeof(arr) / sizeof(arr[0]);Then we used the sort() function to sort the array. As you have read, the first parameter is the pointer pointing to the starting element in the array and the second one is the number of elements that we want to sort.
/*Here we take two parameters, the beginning of the
array and the length n up to which we want the array to
be sorted*/
sort(arr, arr + n);How to sort in descending order?
As you have already read the sort function takes another optional parameter. We can use the “greater()” function as the third parameter that will help to sort the elements in descending order. What the function does is it compares the elements in a way that puts greater elements before the smaller elements.
Let’s look at an example to understand this,
For example,
// C++ program to demonstrate descending order sort using
// greater<>().
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n, greater<int>());
cout << "Array after sorting : \n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;
}
Output:
Array after sorting :
9 8 7 6 5 4 3 2 1 0 How do we sort elements in a given range?
To sort elements in a given range we need to pass the range as a parameter the first one which will be the start of the range and the second one will be the end of the range.
Below is the implementation of the above case:
// C++ program to demonstrate sort()
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = { 0, 1, 5, 8, 9, 6, 7, 3, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
// Sort the elements which lies in the range of 2 to
// (n-1)
sort(arr + 2, arr + n);
cout << "Array after sorting : \n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;
}
Output
Array after sorting :
0 1 2 3 4 5 6 7 8 9 How to sort in a particular order?
To sort the elements in a particular order we will define our own comparator function and pass it as the third parameter to the sort function. This “comparator” function returns a value that is convertible to bool, which basically tells us whether the passed “first” argument should be placed before the passed “second: argument or not.
For example,
// A C++ program to demonstrate
// STL sort() using
// our own comparator
#include <bits/stdc++.h>
using namespace std;
// An interval has a start
// time and end time
struct Interval {
int start, end;
};
// Compares two intervals
// according to starting times.
bool compareInterval(Interval i1, Interval i2)
{
return (i1.start < i2.start);
}
int main()
{
Interval arr[]
= { { 6, 8 }, { 1, 9 }, { 2, 4 }, { 4, 7 } };
int n = sizeof(arr) / sizeof(arr[0]);
// sort the intervals in increasing order of
// start time
sort(arr, arr + n, compareInterval);
cout << "Intervals sorted by start time : \n";
for (int i = 0; i < n; i++)
cout << "[" << arr[i].start << "," << arr[i].end
<< "] ";
return 0;
}
Output
Intervals sorted by start time :
[1,9] [2,4] [4,7] [6,8] The time complexity of sort() is:
- Best Case – O(N log N)
- Average Case – O(N log N)
- Worst Case – O(N log N)
Space Complexity: May use O(log N) auxiliary space.
That is all for this article. Happy Coding!
