Sorting Stability and When to Use Which Sort in DSA C++ - Build from Scratch

Sorting Stability and When to Use Which Sort

📖 Scenario: You work in a small bookstore that keeps track of books by their title and year of publication. You want to sort the books by year but keep the order of books with the same year as they were originally added. This is called a stable sort. You will learn how to create a list of books, choose a sorting method, and see how stability affects the order.

🎯 Goal: Build a program that stores a list of books with their titles and years, then sorts them by year using a stable sorting method. You will see how the order of books with the same year stays the same after sorting.

📋 What You'll Learn

Create a list of books with exact titles and years

Create a variable to hold the number of books

Use a stable sorting method to sort books by year

Print the sorted list showing title and year

💡 Why This Matters

🌍 Real World

Sorting books or products by attributes like year or price while keeping the original order of items with the same attribute is common in inventory and catalog management.

💼 Career

Understanding stable sorting helps in software development roles involving data processing, UI lists, and any scenario where order preservation matters.

1

Create the list of books

Create a struct Book with title (string) and year (int). Then create a vector<Book> called books with these exact entries: {"The Hobbit", 1937}, {"1984", 1949}, {"Animal Farm", 1945}, {"Brave New World", 1932}, {"Fahrenheit 451", 1953}, {"The Catcher in the Rye", 1951}, {"Lord of the Flies", 1954}, {"The Great Gatsby", 1925}, {"To Kill a Mockingbird", 1960}, {"The Hobbit", 1937} (note the duplicate title with same year).

DSA C++

// Define struct Book and create vector books with given entries
// Your code here

Hint

Use struct to define Book with title and year. Then create a std::vector<Book> with the exact books listed.

2

Create a variable for the number of books

Create an int variable called n and set it to the size of the books vector using books.size().

DSA C++

#include 
#include 
#include 

struct Book {
    std::string title;
    int year;
};

int main() {
    std::vector books = {
        {"The Hobbit", 1937},
        {"1984", 1949},
        {"Animal Farm", 1945},
        {"Brave New World", 1932},
        {"Fahrenheit 451", 1953},
        {"The Catcher in the Rye", 1951},
        {"Lord of the Flies", 1954},
        {"The Great Gatsby", 1925},
        {"To Kill a Mockingbird", 1960},
        {"The Hobbit", 1937}
    };
    // Create int n to hold number of books
    // Your code here

Hint

Use int n = books.size(); to get the number of books.

3

Sort the books by year using a stable sort

Use std::stable_sort with a lambda function to sort the books vector by the year field in ascending order. The lambda should take two Book references called a and b and return a.year < b.year.

DSA C++

#include 
#include 
#include 
#include 

struct Book {
    std::string title;
    int year;
};

int main() {
    std::vector books = {
        {"The Hobbit", 1937},
        {"1984", 1949},
        {"Animal Farm", 1945},
        {"Brave New World", 1932},
        {"Fahrenheit 451", 1953},
        {"The Catcher in the Rye", 1951},
        {"Lord of the Flies", 1954},
        {"The Great Gatsby", 1925},
        {"To Kill a Mockingbird", 1960},
        {"The Hobbit", 1937}
    };
    int n = books.size();
    // Use std::stable_sort with lambda to sort books by year
    // Your code here

Hint

Use std::stable_sort with a lambda that compares a.year and b.year.

4

Print the sorted list of books

Use a for loop with variable i from 0 to n - 1 to print each book's title and year in the format: Title: [title], Year: [year].

DSA C++

#include 
#include 
#include 
#include 

struct Book {
    std::string title;
    int year;
};

int main() {
    std::vector books = {
        {"The Hobbit", 1937},
        {"1984", 1949},
        {"Animal Farm", 1945},
        {"Brave New World", 1932},
        {"Fahrenheit 451", 1953},
        {"The Catcher in the Rye", 1951},
        {"Lord of the Flies", 1954},
        {"The Great Gatsby", 1925},
        {"To Kill a Mockingbird", 1960},
        {"The Hobbit", 1937}
    };
    int n = books.size();
    std::stable_sort(books.begin(), books.end(), [](const Book& a, const Book& b) {
        return a.year < b.year;
    });
    // Print each book's title and year
    // Your code here

Hint

Use a for loop from 0 to n - 1 and print each book's title and year with std::cout.