In C++, sorting vector is an essential feature in programming because it structures elements in a meaningful order, such as ascending or descending. Sorting is crucial in making algorithms more efficient. It needs pre-sorted information to use when order counts, i.e., data analysis and presenting output in a friendly format. Effective sorting can significantly enhance the performance of programs, particularly when working with large datasets.
In C++, several methods can be utilized to sort a vector. The most effective and simple method to sort the vector is by calling the sort method.
Simple Example of Sorting Vector in C++
Let us take an example to illustrate how we can sort the vector using the sort function in C++.
Example
#include <bits/stdc++.h>
using namespace std; //using standard namespace
bool compare(int x, int y) {
return x > y;
}
int main() { //main function
vector<int> v = {1, 2, 6, 8, 5};
sort(v.begin(), v.end(), compare);
for (auto i : v)
cout << i << " ";
return 0;
}
Output:
8 6 5 2 1
Explanation:
In this example, we sort a vector of integers in descending order by using a special comparison function. After that, the compare function returns true if the first number is bigger than the second, so the sort function places the elements in decreasing order from largest to smallest. The last loop prints the sorted vector: 8 6 5 2 1.
Different ways to Sorting a Vector
There are several ways in C++ by using which we can sort the vector. A few of them are as follows:
1) Using stable_sort
In C++, the stablesort function works similarly to the sort function, but the only difference is that the stablesort preserves the order of the elements if they are equal.
Syntax
It has the following syntax:
std::stable_sort(vec.begin(), vec.end());
C++ Sorting a Vector Example using stable_sort function
Let us take an example to illustrate how to sort a vector using the stable_sort function in C++.
Example
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; //using standard namespace
struct Person {
string name;
int age;
};
void printPeople(const vector<Person>& people) {
for (const auto& p : people)
cout << p.name << " (" << p.age << ")\n";
}
int main() { //main function
vector<Person> people = {
{"John", 30},
{"Alice", 25},
{"shyam", 30},
{"Michael", 25}
};
stable_sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
return a.age < b.age;
});
printPeople(people);
return 0;
}
Output:
Alice (25)
Michael (25)
John (30)
shyam (30)
Explanation:
In this example, we declare a Person struct with members' names and ages, which initiates a vector of Person instances and sorts them using stablesort according to age in ascending order. As stablesort preserves the relative order of equal elements, users who share the same age retain their initial order.
2) Using Multiset
In C++, a multiset is an ordered container that holds data in the provided sorting order. It is also possible to sort vectors using a multiset by initially pushing all elements of the vector into a multiset and then placing them back one by one.
Syntax
It has the following syntax:
std::multiset<int> ms(vec.begin(), vec.end()); // Sorted automatically
C++ Sorting a Vector Example Using Multiset
Let us take an example to illustrate to sort a vector using the multiset function in C++.
Example
#include <bits/stdc++.h>
using namespace std; //using standard namespace
int main() //main function
{
vector<int> vec = {30, 25, 30, 25, 40, 10, 50};
// Create multiset from vec
multiset<int> ms(vec.begin(), vec.end());
// Copy back all the elements frmo ms to v
vec.assign(ms.begin(), ms.end());
for (auto i : vec)
cout << i << " ";
return 0;
}
Output:
10 25 25 30 30 40 50
Explanation:
In this example, we demonstrate how to sort a vector using a multiset. First, we contain the vector<int> vec that contains unsorted elements with duplicates. By inserting its elements into a multiset, they are automatically arranged in ascending order while preserving duplicates. After that, the sorted elements are copied back to the vector using assign, and finally printed.
3) Using Bubble Sort Algorithm
In C++, bubble Sort is a naive sorting algorithm that constantly swaps consecutive elements if they are in the wrong position. After that, the cycle is continued until the vector is sorted.
C++ Sorting a Vector Example using the Bubble Sort Algorithm
Let us take an example to illustrate how to sort a vector using the Bubble Sort Algorithm in C++.
Example
#include <iostream>
using namespace std; //using standard namespace
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; ++i)
for (int j = 0; j < n-i-1; ++j)
if (arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
}
int main() { //main function
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
for (int i = 0; i < n; ++i) cout << arr[i] << " ";
return 0;
}
Output:
11 12 22 25 64
Explanation:
In this example, we sort an array using the bubble sort technique. It continuously checks for adjacent elements and swaps them if they are not in their correct order. After sorting, the array is displayed in ascending order.
4) Using a Custom Comparator
In C++, we might need to sort items according to certain conditions, such as sorting in reverse order or sorting objects. We can achieve this by providing a custom comparator function to the std::sort function.
C++ Sorting a Vector Example using the Custom Comparator
Let us take an example to illustrate how to sort a vector using the custom comparator in C++.
Example
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; //using standard namespace
bool customCompare(int a, int b) {
return a > b;
}
int main() { //main function
vector<int> v = {5, 2, 9, 1, 5, 6};
sort(v.begin(), v.end(), customCompare);
for (int x : v) cout << x << " ";
return 0;
}
Output:
9 6 5 5 2 1
Explanation:
In this example, we sort a vector in descending order with the help of a custom comparator function customCompare, which compares two elements and returns true if the first is greater than the second. After that, the std::sort function employs this comparator to sort the elements, and then the sorted vector is printed.
5) Using Lambda Expressions
In C++, lambda expressions also offer a direct way to encode anonymous functions at the site of function calls so that they may be used more easily for their intended purpose, such as customized sorting. C++ lambda expressions are especially better with the use of std::sort because we can actually specify custom sorts without having to define a special comparator function in some other portion of the source code.
C++ Sorting Vector Example Using Lambda Expressions
Let us take an instance to demonstrate how to sort a vector using the Lambda Expressions in C++.
Example
#include <iostream>
#include <vector> //for vectors container
#include <algorithm> //for sort() algorithm
using namespace std; //using standard namespace
int main() { //main function
vector<int> v = {4, 9, 3, 1, 6};
sort(v.begin(), v.end(), [](int a, int b) {
return a > b;
});
for (int x : v) cout << x << " ";
return 0;
}
Output:
9 6 4 3 1
Explanation:
In this example, we generate a vector v with a some integers. After that, it sorts the vector in descending order with the sort and a lambda expression to return true value if the first element is larger than the second. After sorting, it prints out all elements of the vector in sequence.
6) Using partial_sort
In C++, the partial_sort function is useful if we need to sort a part of the vector, such as the smallest or largest items. It partially sorts the first n elements, which leaves the remaining part of the vector in some undefined order.
C++ Sorting a Vector Example using partial_sort function
Let us take an instance to demonstrate how to sort a vector using the partial_sort function in C++.
Example
#include <iostream>
#include <vector> //for vectors container
#include <algorithm> //for sort() algorithm
using namespace std; //using standard namespace
int main() { //main function
vector<int> v = {7, 2, 9, 4, 3, 8};
partial_sort(v.begin(), v.begin() + 3, v.end());
for (int x : v) cout << x << " ";
return 0;
}
Output:
2 3 4 9 7 8
Explanation:
In this example, we use the partial_sort function to partially sort the first three smallest elements in the vector v. After that, it puts these elements in ascending order at the beginning of the vector, and the rest of the elements remain unordered.
Conclusion
In conclusion, sorting a vector is a fundamental skill because it enables data organization in an informative order. Various sorting algorithms, such as sort, stable_sort, custom comparators, lambdas, and even partial sorting, are highly flexible based on the program requirements.
C++ Sorting Vectors MCQs
1) Which of the following functions is used to sort a vector in C++?
- std::reverse
- std::sort
- std::shuffle
- std::rotate
2) Which of the following sorting methods preserves the order of equal elements in C++?
- std::sort
- std::partial_sort
- std::stable_sort
- std::multiset
3) Which of the following is a characteristic of C++ lambdas used for sorting?
- They are always slower than custom comparators.
- They allow sorting directly at the point of use without needing a separate function.
- They cannot capture variables from the outer scope.
- They only work with set.
4) What does the partial_sort function perform in C++?
- Sorts the entire vector
- Sorts the first n elements of the vector and leaves the rest unordered
- Sorts the vector in descending order
- Partially reverses the vector
5) What happens when we use a multiset to store elements in C++?
- It stores elements in any order
- It sorts elements in ascending order automatically
- It removes duplicate elements
- It stores only unique elements