Lesson 4
Exploring Sorting Techniques in C++
Lesson Introduction and Overview

Hello, and welcome back! Our journey today takes us into the sorting universe in C++. We will learn about and utilize the built-in sorting function from the C++ Standard Library: std::sort. This tool significantly simplifies the task of sorting in C++. Let's get started!

Understanding Sorting and Its Importance

Sorting refers to arranging data in a specific order, which enhances the efficiency of search or merge operations on data. In real life, we sort books alphabetically or clothes by size. Similar concepts apply in programming, where sorting large lists of data is essential for more effective analysis.

C++ offers a built-in sorting method: std::sort, found in the <algorithm> header. Here's a demonstration of how we use this method:

Sorting of Primitive Types and Objects

Sorting with std::sort makes sorting arrays and vectors straightforward. Let's see it in action!

Sorting Arrays of Primitives

C++
1#include <iostream> 2#include <algorithm> 3 4int main() { 5 int arr[] = {4, 1, 3, 2}; 6 std::sort(arr, arr + 4); 7 for (int i = 0; i < 4; ++i) { 8 std::cout << arr[i] << " "; 9 } 10 // Output: 1 2 3 4 11 return 0; 12}

Sorting Vectors of Strings

C++
1#include <iostream> 2#include <vector> 3#include <algorithm> 4 5int main() { 6 std::vector<std::string> inventory = { "Bananas", "Pears", "Apples", "Dates" }; 7 std::sort(inventory.begin(), inventory.end()); 8 for (const auto& item : inventory) { 9 std::cout << item << std::endl; 10 } 11 12 // Output: 13 // Apples 14 // Bananas 15 // Dates 16 // Pears 17 return 0; 18}

As you can see, sorting in C++ is as simple as that!

More Complex Sorting Problem

C++ allows us to define custom sorting logic using lambda expressions. Let's sort a vector of students by their grades, with alphabetical sorting applied in the event of ties in grades. First, let's define the Student class:

C++
1#include <iostream> 2#include <vector> 3#include <algorithm> 4 5class Student { 6public: 7 std::string Name; 8 int Grade; 9 10 Student(std::string name, int grade) : Name(name), Grade(grade) {} 11 12 friend std::ostream& operator<<(std::ostream& os, const Student& s) { 13 os << s.Name << ":" << s.Grade; 14 return os; 15 } 16};
Custom Sorting with Lambda Expressions

Here's how we perform custom sorting using lambda expressions in C++:

C++
1int main() { 2 std::vector<Student> students = { 3 {"Alice", 85}, 4 {"Bob", 90}, 5 {"Charlie", 90} 6 }; 7 8 std::sort(students.begin(), students.end(), 9 [](const Student& s1, const Student& s2) { 10 if (s1.Grade != s2.Grade) return s1.Grade > s2.Grade; 11 return s1.Name < s2.Name; 12 } 13 ); 14 15 for (const auto& student : students) { 16 std::cout << student << ", "; 17 } 18 // Output: Bob:90, Charlie:90, Alice:85 19 return 0; 20}

In the example above, we create a std::vector<Student> and sort it using a custom comparison defined via a lambda expression. The lambda compares Student objects first based on their grades in descending order and, in the event of a tie, compares their names in alphabetical order. The std::sort function uses this custom logic to determine the order of elements.

Applying Reverse Order in Sorting

To sort students by grades in ascending order but names in descending order in the case of ties, you can adjust the lambda expression:

C++
1int main() { 2 std::vector<Student> students = { 3 {"Alice", 85}, 4 {"Bob", 90}, 5 {"Charlie", 90} 6 }; 7 8 std::sort(students.begin(), students.end(), 9 [](const Student& s1, const Student& s2) { 10 if (s1.Grade != s2.Grade) return s1.Grade < s2.Grade; 11 return s1.Name > s2.Name; 12 } 13 ); 14 15 for (const auto& student : students) { 16 std::cout << student << ", "; 17 } 18 // Output: Alice:85, Charlie:90, Bob:90 19 return 0; 20}

Here, the custom comparison sorts the grades in ascending order while sorting names in descending order when the grades are the same.

Lesson Summary and Next Steps

Well done! You've learned how sorting functions in C++ work and have utilized C++'s built-in sorting functions.

In our future lessons, we'll delve deeper into sorting and tackle more intricate problems, such as finding the K-th largest number. So, stay tuned and get ready to sort your way to success! Happy coding!

Enjoy this lesson? Now it's time to practice with Cosmo!
Practice is how you turn knowledge into actual skills.