In order to sort a vector we can use sort() function from the Standard Library (std::sort), which sorts the elements of a given array in ascending order (default), descending order or user-defined order.
Syntax:
The syntax of the sort() function is:
void sort( RandomIt first, RandomIt last, Compare comp );
Let's see some examples below. Sorting an array of integers in ascending order
vector<int> numbers = {11, 3, 7, 5, 2};
sort(numbers.begin(), numbers.end()); // numbers becomes [2, 3, 5, 7, 11]
Sorting an array of integers in descending order
vector<int> numbers = {11, 3, 7, 5, 2};
sort(numbers.begin(), numbers.end(), greater<int>());
Sorting an array of Strings in descending order
vector<string> names = {"Mircea", "Andy", "Xavier", "Michael", "Christina"};
sort(names.begin(), names.end(), greater<string>()); // --> ['Xavier', 'Mircea', 'Michael', 'Christina', 'Andy']
Sort with custom function (comparator):
sort() function supports a basic comparison function that we can use to specify how we want to sort:
bool compare(int a, int b) {
return a < b;
}
This can be written as a lambda function (nameless function we can easily pass to sort()) as follows:
[](int a, int b) -> bool {
return a < b;
}
We can make it even shorter by dropping the return statement since sort() will expect a bool. Also we can generalize it by changing int to auto
[](auto a, auto b) {
return a < b;
}
When the sort() function compares two values, it sends the values to the compare function, and sorts the values according to the returned value:
true then a is sorted before b.false then b is sorted before a.All we need to is using the compare function (as a lambda function) inside the sort() function:
vector<int> numbers = {3, 23, 12};
// using the short version of the lambda function
sort(numbers.begin(), numbers.end(), [](auto a, auto b) { return a < b; }); // --> 3, 12, 23
To demonstrate a basic example, let’s assume the requirement for ordering a specific list is the length of the strings in the list, shortest to longest. We will be using the size() method of each string to compare them.
vector<string> words = {"banana", "pie", "Washington", "book"};
sort(words.begin(), words.end(), [](auto a, auto b) -> a.size() < b.size()); // --> ['pie', 'book', 'banana', 'Washington']
Example: sorting array of pairs
Let's say we want to sort an array, where each element is another array consisting of two numbers.
vector<vector<int>> pairs = {{1, 5}, {12, 5}, {10, 1}, {1, 3}};
sort(pairs.begin(), pairs.end(), [](auto a, auto b) {
// in case the first values of each pair are equal,
// compare them using their second values
if (a[0] == b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
});
// pairs --> [[1, 3], [1, 5], [10, 1], [12, 5]]
Time Complexity:
Sorting an array via Arrays.sort() takes O(n * log n * C) time, where C is the time taken to compare two elements from the array.
It takes O(1) (constant time) to compare two numbers, therefore sorting an array of numbers takes O(n log n).
However, it takes O(L) to compare two strings, therefore sorting an array of strings takes O(n * log n * L), where L is the average length of the strings.
Space Complexity:
The sort() method sorts the elements of an array in place (transforms the array directly, using no auxiliary data structure), so the extra space used for this is O(1).
Assignment
Follow the Coding Tutorial and let's sort some arrays.
Hint
Look at the examples above if you get stuck.
Sorting is a fundamental operation in computer science and programming. It involves arranging data in a particular order, typically ascending or descending. Sorting is crucial for optimizing the efficiency of other algorithms that require sorted data, such as search algorithms. Common scenarios where sorting is useful include organizing data for display, preparing data for binary search, and simplifying complex data processing tasks.
Before diving into advanced sorting techniques, it's essential to understand the basic concepts. Sorting algorithms rearrange elements in a list or array based on a comparison function. The most common comparison functions are those that sort in ascending or descending order. Understanding these basics is crucial because they form the foundation for more complex sorting operations.
The key concepts in sorting include:
Applying these concepts involves using the std::sort function in C++, which provides a flexible and efficient way to sort arrays and vectors.
Let's explore some examples to understand how sorting works in different contexts:
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> numbers = {11, 3, 7, 5, 2};
std::sort(numbers.begin(), numbers.end());
for (int num : numbers) {
std::cout << num << " ";
}
return 0;
}
// Output: 2 3 5 7 11
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<std::string> names = {"Mircea", "Andy", "Xavier", "Michael", "Christina"};
std::sort(names.begin(), names.end(), std::greater<std::string>());
for (const auto& name : names) {
std::cout << name << " ";
}
return 0;
}
// Output: Xavier Mircea Michael Christina Andy
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<std::string> words = {"banana", "pie", "Washington", "book"};
std::sort(words.begin(), words.end(), [](const auto& a, const auto& b) {
return a.size() < b.size();
});
for (const auto& word : words) {
std::cout << word << " ";
}
return 0;
}
// Output: pie book banana Washington
When working with sorting algorithms, it's essential to avoid common mistakes such as:
Best practices include writing clear and efficient comparison functions, testing with various input sizes, and understanding the underlying algorithm's complexity.
Advanced sorting techniques involve custom comparators and lambda functions. These techniques allow for more flexible and efficient sorting based on specific criteria. For example, sorting a list of pairs based on multiple conditions can be achieved using a custom comparator.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<std::vector<int>> pairs = {{1, 5}, {12, 5}, {10, 1}, {1, 3}};
std::sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
if (a[0] == b[0]) {
return a[1] < b[1];
}
return a[0] < b[0];
});
for (const auto& pair : pairs) {
std::cout << "[" << pair[0] << ", " << pair[1] << "] ";
}
return 0;
}
// Output: [1, 3] [1, 5] [10, 1] [12, 5]
Debugging sorting algorithms involves checking the correctness of the comparison function and ensuring that the array is sorted as expected. Writing test cases for various scenarios, including edge cases, is crucial. Using tools like debuggers and print statements can help identify issues in the sorting logic.
When approaching sorting problems, consider the following strategies:
Sorting is a vital skill in programming, enabling efficient data organization and processing. Mastering sorting algorithms and techniques, such as custom comparators and lambda functions, is essential for writing efficient and maintainable code. Practice regularly and explore further applications to deepen your understanding.
For further reading and practice problems, consider the following resources: