Sorting is one of the most basic and useful functions applied to data. It aims at arranging data in a particular fashion, which can be increasing or decreasing as per the requirements. There is a builtin function in C++ STL by the name of ‘sort()’ which allows us to perform sorting algorithm easily. In this article we will be exploring Sort Function In C++,
Following Pointers will be covered in this article:
- Sort() function
- Example- To sort data in ascending order
- Example – To sort data in descending order
- Partial_sort
Moving on with this article on Sort function in C++
Sort() function
It is a built-in function of algorithm header file it is used to sort the containers like an array, vectors in a specified order. Internally this function is implemented as Quick-sort
Quicksort is a divide and conquer algorithm. Quicksort first divides a large list of elements into two smaller sub-lists: the lower elements and the higher elements. Quicksort then recursively sort the sub-lists.
The steps are as follows:
1. Pick a random element(usually the last element), called a pivot, from the list.
2. Reorder the list in a way such that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it and equal values can go either way this is process is called partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements, again select a pivot in sub-list and divide them.
The base case of the recursion is lists of size zero or one, which never need to be sorted and thus by combining them we sort our list.
Quicksort is faster in practice than other O(n log n) algorithms such as Insertion Sort or Bubble sort. Quicksort can be implemented with an in-place partitioning algorithm which means the entire sort can be done with only O(log n) additional space. Quicksort is not a stable sort.
Its complexity is as follows:
Best Case – O(n log n)
Worst Case – O(n^2)
Average Case – O(n log n)
Syntax:
sort(first, last);
Here,
first – is the index (pointer) of the first element in the range to be sorted.
last – is the index (pointer) of the last element in the range to be sorted.
For example, we want to sort elements of an array ‘arr’ from 1 to 10 position, we will use sort(arr, arr+10) and it will sort 10 elements in Ascending order.
Return value
None
Complexity
The average of a sort complexity is N*log2 (N), where N = last – first.
Data range
The object in the range [first, last) are modified.
Exceptions
The overloads with a template parameter that is named as ExecutionPolicy report errors as follows:
If the algorithm fails to allocate memory, std::bad_alloc is thrown as an exception.
If the execution of a function invoked as part of the algorithm it throws an exception std::terminate.
Moving on with this article on Sort function in C++
Example – To sort data in ascending order:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int array[] = {10, 35, 85, 93, 62, 77, 345, 43, 2, 10};
int n = sizeof(array)/sizeof(array[0]);
// 'sizeof' gives the size of total array i.e. size of each character * no. of characters
// so to get no. of characters
// we divide the sizeof(array) with the size of any one character of the array
// here it is array[0]
sort(array, array+n);
cout << "nArray after sorting using "
"default sort is : n";
for (int i = 0; i < n; ++i)
cout << array[i] << " ";
return 0;
}
Output :
Explanation
From the above example, we see that sort() function by default sorts an array in ascending order.
Moving on with this article on Sort function in C++
Example – To sort data in descending order:
To sort the data of array in descending order we need to introduce a third parameter that is used to specify the order in which elements are to be sorted. We can use “greater()” function to sort the data in descending order.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int array[] = {41, 53, 4, 459, 60, 7, 23, 4, 232, 10};
int n = sizeof(array)/sizeof(array[0]);
sort(array, array+n, greater<int>());
cout << "Array after sorting : n";
for (int i = 0; i < n; ++i)
cout << array[i] << " ";
return 0;
}
Output:
Explanation
Here sort() function does a comparison in a way that puts greater element before.
Moving on with this article on Sort function in C++
Partial_sort
C++ STL provides us with a partial sorting function, the function is similar to sort() function but unlike the sort() function it is not used to sort the entire range rather it is used to sort only a sub-part of it. It sorts the elements in the range of [first, last), in such a way that the elements before middle element are sorted in ascending order, whereas the elements after middle are left as it is.
It can be used to find the largest element if we use a function object to sort for the first position
Example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector<int> vec = { 10, 45, 60, 78, 23, 21, 30 };
vector<int>::iterator iptr;
partial_sort(vec.begin(), vec.begin() + 1, vec.end(),
greater<int>());
iptr = vec.begin();
cout << "The largest element is = " << *iptr;
return 0;
}
Output:
Explanation:
The above code can be used to find the greatest number in a series, to find the smallest number in series we just need to remove the greater<int> command.
Thus we have come to an end of this article on ‘Sort Function in C++’. If you wish to learn more, check out the Java Training by Edureka, a trusted online learning company. Edureka’s Java J2EE and SOA training and certification course are designed to train you for both core and advanced Java concepts along with various Java frameworks like Hibernate & Spring.
Got a question for us? Please mention it in the comments section of this blog and we will get back to you as soon as possible.