Sorting is an essential task in everyday life and Mathematics too. Most of the time, you have to sort objects or numbers in ascending or descending order, or in even an odd series. It all depends on how you want to arrange your numbers or objects. The sort function in C++ helps in the sorting process by providing a Sort() function in STL, the Standard Template Library. STL is a library that consists of predefined functions and data structure which makes it user-friendly. STL also consists of container classes and algorithms and iterators.
Learn more about the basics of Sort Function in C++ here :
- What is Sort Function in C++?
- Sort Algorithm
- Types of Sort function
- Sorting Integral Data Types
- Sort using a Function Object
- Sorting using the Lambda Expression
- Insertion Sort
- Bubble Sort
- Selection Sort
What is Sort Function in C++?
Sort is an in-built function in a C++ STL ( Standard Template Library). This function is used to sort the elements in the range in ascending or descending order.
Sort Function Syntax:
default (1)
template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);
custom (2)
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
Sort Algorithm
Before we know more about Sort () in STL, there are a few important points we need to know about Sort ().
- In C++ STL, we have a sort function which can sort in increasing and decreasing order.
- Not only integral but you can sort user-defined data too using this function.
- Internally it uses IntroSort, which is a combination of QuickSort, HeapSort and InsertionSort.
(This is important as it occurs internally and no one knows about it.)
- By default, it uses QuickSort, but if QuickSort is doing unfair partitioning and taking more than N*logN time, it switches to HeapSort. When the array size becomes very small, it switches to InsertionSort.
(This conversion and checking occurs internally and is not very popular to people)
- We can use parallel execution policy for better performance.
(To invoke this policy all you have to do is pass only one parameter which is std::sort(std::execution::par, Vec.begin(),Vec.end() );
You have to mention the start and the end, and it will take care of the rest. You don’t have to do any multithreading coding to get a good result.
Note: There are a few situations where you cannot use parallel execution policy when you have data arrays. There are so many other algorithms in the algorithm section of STL for it. You can also do parallel processing.)
If you want a faster result or have data in a large amount, you can use parallel processing for sorting.
Whenever you use the Sort (), there is not only one sort function like quick sort or some other sort function under the function. There are different sorting algorithms. Depending upon the type of data you enter and the circumstances, it picks the right sorting algorithms and sorts your data.
Types of Sort Function
There are four different methods or types of how we can use the Sort ().
- Sorting integral data types
- Sorting user-defined data types
- Sort using a function object
- Sort using the lambda expression
Sorting Integral Data Types
In this type, you will use integral data types such as 1,2 and so on or in other words, the whole numbers.
Example Program:
#include <iostream>
#include <algorithm>
#include <vector>
#include <execution>
Using namespace std;
int main()
{
std::vector<int> Vec{5,3,6,2,7,4,1,8,2,9};
std::sort(std::execution::par, Vec.begin(),Vec.end());
for(auto elm:Vec)
{
cout << elm << “ ”;
}
return 0;
}
Output:
1 2 3 4 5 6 7 8 9Sorting user-defined data types
This type is an important one where you have a collection of objects depending on your class’s parameter.
If you want to sort all the objects in your array or vector,
Example Program:
class Point{
public:
int x;
int y;
Point (int x=0, int y=0): x(x), y(y) {}
bool operator < (const Point& p1){
return ( x+y ) < (p1.x + p1.y);
}
};
int main()
{
std::vector<Point> Vec {{1,2},{3,1},{0,1}};
std::sort (Vec.begin(), Vec.end());
for ( auto e: Vec)
{
Cout << e.x <<” “<< e.y << endl;
}
return 0;
}
Explanation:
The class point is a user-defined data type. We used the ‘less than’ operator (“<”) in the form of operator overloading. A sort compares one element with another element, it takes one element and compares using ‘less than’ operator, and then it takes the next element. Consider “A” is an object of the class Point, and B is also the same class’s object. Since A<B, the operator is now overloaded so that internally the sort function compares one of the objects if it is less than another object which will call the “Bool operator” function internally and the logic to sort. Here it is x, and that should be added and checked. It checks if the addition of both x and y is less than the sum of another object’s x and y.
Consider ‘1’ and ‘2’ is an object, and ‘3’, and ‘1’ is an object. Now, the addition of ‘1’ and ‘2’ is ‘3’. Furthermore, the addition of ‘3’ and ‘1’ is ‘4’. While comparing, ‘3’ is less than ‘4’ so the objects ‘1’ and ‘2’ will be placed first, and the process goes on till it is sorted out.
Output:
0 1
1 2
3 1
Note: If you want to sort your objects or collection in descending order, then you have to overload the greater than the operator and give std::greater<Type>() as the third parameter in sort function.
Example:
Sort(Vec.begin(), Vec.end(), std::greater <Point>());
Sort using a Function Object
This method uses a function object to sort.
Example:
struct{
bool operator () (int a, int b) const{
return a<b;
}
} customLess;
int main(){
std::vector<int> Vec{5,4,6,7,3,2,8,1}
std::sort(Vec.begin(), Vec.end().customLess);
for(auto elm: Vec){
cout<< elm<<” “;
}
Explanation:
‘customLess’ is a pointer that we use in this example. It is called within the round brackets as a function when it is called it gets redirected to the struct block, and the sort function begins.
Output:
1 2 3 4 5 6 7 8
Sorting using the Lambda Expression
In this type, you will directly inject the function into the places where the object is called. You can use the function body directly instead of creating a separate function block to do the expression and calling it in the main function. We can directly add them to the main function itself.
Example Program:
int main()
{
std::vector<int> Vec{5,4,7,6,2,8,9,1,3};
std::sort ( Vec.begin(), Vec.end(), [](int a, int b) { return a<b; });
for (auto elm: Vec){
cout << elm << ” “;
}
return 0;
}
Output:
1 2 3 4 5 6 7 8 9
Apart from using Sort () function, few other sorting methods are done manually by writing a code for it. These methods are mostly used in array sets.
These methods are:
- Bubble sort
- Insertion sort
- Selection sort
- Merge sort
- Quicksort
- Heapsort
Let’s see a few of the sorting methods.
1. Insertion Sort
Insertion sort is a simple in-place comparison-based sorting algorithm.
It maintains a sub-array (sub-list) which is always sorted and is built one element at a time. It selects each element and inserts it at its sorted position in the sorted sub-array.
Example:
void insertionSort( int A[],int n)
{
int i,value, index;
for(i=1;i<n;i++)
{
value = A[i];
index=i;
while(index>0 && A[index-1]
{
A[index]=A[index-1];
index=index-1;
}
A[index]=value;
}
}
Explanation:
Considering an array named A, it holds six elements as such
| 5 | 2 | 3 | 1 | 6 | 4 |
We know that the index number always starts from 0.
We start with the first element. Initially, the sorted sub-array has 0 elements. When we insert the first element, it will be placed in the sorted position. It selects each element one by one. The variable “i’ is useful for transversal within the array.Also, we use the variables “value” and “index” . Value is used to store the value of the selected element, and the index is used to insert the element in a sorted sub-array. The variable “index” contains the index of the selected element. Each element in array A is compared with the elements in the sorted sub-array. After each comparison, it shifts all the greater elements than the selected element to one position to the right. Then it inserts the selected element at its sorted position. This process repeats till the array is sorted.
2. Bubble Sort
Bubble sort is a simple comparison-based algorithm, where each pair of adjacent elements are compared and swapped if they are not in the right position.
Example Program:
void Bubblesort (int A[[], int n)
{
int k, i, temp, flag;
For ( k=1;k<n; k++)
{
Flag =0;
For (i=0; i< n-k; i++)
{
If (A[i]>A[i+1])
{
temp=A[i];
A[i]=A[i+1};
A[i+1]=temp;
flag=1;
}
}
if(flag==0)
break;
}
}
Explanation:
N is the number of elements in the array, K represents the past number where the range of K is 1to n-1. The elements are compared with the adjacent elements starting from index number 0 till index “n-k”, which means in every index, “n-k” comparison is made. After each comparison, if the left element is greater than the element on the right, their positions interchange or else it will move to the next pair. After each pass, the greater element will be added to its sorted position. This process is repeated till the array is sorted out.
3. Selection Sort
Selection sort is also a simple in-place comparison-based sorting algorithm.
Example Program:
int selectionSort (int A[], int n)
{
int i, j, small, temp;
for(i=0;i<n-1;i++)
{
small=i;
for (j=i+1; j< n; j++)
{
if (A[j] < A[small])
small=j;
}
temp=A[i];
A[i] =A[small];
A[small] =temp;
}
}
Explanation:
We divide the array of elements that require sorting into two sub-arrays: ‘Sorted’ (left) and ‘Unsorted’ (right). We consider the whole array as ‘unsorted’ in the beginning. The array is then sorted element by element. As the sorting happens, the sorted subarray’s size increases and the unsorted subarray size decreases. The leftmost element of the unsorted subarray is selected, and it gets swapped with the smallest element of the unsorted sub-array.
To understand better, let’s see with an example.
| 3 | 2 | 5 | 1 | 4 |
Consider this array to be ‘unsorted’, we select the leftmost element in the ‘unsorted’ subarray using the variable “i”. We have to find the smallest element in the unsorted subarray and swap it with the leftmost element. To find the smallest element, we use the variable ‘small”. The variable “small” stores the index of the smallest element. It is then equated to “i”.
Initially, “i” and “small” have the index 0 assigned to it. Another variable “j” is in usage to loop through the array to find the smallest element. At every iteration, there is a comparison of the value at “small” and the value at “j”. Suppose the value at “j’ is smaller than the value at “small”. In that case, the index of the element is stored in “small”. This process repeats till we reach the end of the array.
We swap the value at “i” and “small”. Hence, the “small” value is stored, and it becomes part of the sorted sub-array. We repeat the procedure, over and over again, and each time we sort the value in “small”, the value of “I” increments by ‘1’ every time to select the leftmost element.
Final Output:
| 1 | 2 | 3 | 4 | 5 |
This brings us to the end of the blog about Sort function in C++. We hope this helps you to up-skill easily in the journey of C++. To learn more about such concepts, check out the courses at Great Learning Academy.
Also, if you are preparing for Interviews, check out these Interview Questions for C++ to ace it like a pro.
