Sorting Stability and When to Use Which Sort in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Stable Sort on Structs

Given the following C++ code that sorts a vector of structs by the 'value' field using a stable sort, what will be the printed output?

DSA C++

struct Item {
    int id;
    int value;
};

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<Item> items = {{1, 5}, {2, 3}, {3, 5}, {4, 2}};
    std::stable_sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.value < b.value;
    });
    for (const auto& item : items) {
        std::cout << item.id << "-" << item.value << " ";
    }
    return 0;
}

A 4-2 2-3 1-5 3-5

B 4-2 2-3 3-5 1-5

C 2-3 4-2 1-5 3-5

D 2-3 4-2 3-5 1-5

💡 Hint

Stable sort keeps the original order of equal elements.

The stable sort arranges items by their 'value' in ascending order. For items with the same 'value', their original order is preserved. Here, items with value 5 are {1,5} then {3,5}, so they remain in that order after sorting.

🧠 Conceptual

intermediate

When to Prefer Stable Sorts?

Which scenario best explains when you should prefer a stable sorting algorithm over an unstable one?

A When you need to maintain the relative order of records with equal keys after sorting.

B When you want the fastest possible sorting regardless of order of equal elements.

C When sorting small arrays where stability does not matter.

D When you want to sort in descending order only.

💡 Hint

Think about preserving order of equal items.

Stable sorts keep the original order of equal elements, which is important when the order carries meaning, such as sorting by multiple keys in sequence.

❓ Predict Output

advanced

Output of Unstable Sort on Same Data

What is a possible output of the following C++ code using std::sort (which is not guaranteed to be stable) on the same data as before?

DSA C++

struct Item {
    int id;
    int value;
};

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<Item> items = {{1, 5}, {2, 3}, {3, 5}, {4, 2}};
    std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.value < b.value;
    });
    for (const auto& item : items) {
        std::cout << item.id << "-" << item.value << " ";
    }
    return 0;
}

A 2-3 4-2 1-5 3-5

B 4-2 2-3 3-5 1-5

C 4-2 2-3 1-5 3-5

D 1-5 3-5 2-3 4-2

💡 Hint

Unstable sort may reorder equal elements arbitrarily.

std::sort is not guaranteed to be stable, so items with equal 'value' may appear in any order. One possible output is with the two items of value 5 swapped.

🧠 Conceptual

advanced

Choosing Sorting Algorithm Based on Data Size and Stability

You have a large dataset that must be sorted by multiple keys, preserving the order of previous sorts. Which sorting approach is best?

A Use a stable sort once on the most important key only.

B Use an unstable sort once on the most important key only.

C Use a stable sort multiple times, starting from the least important key to the most important key.

D Use an unstable sort multiple times on all keys.

💡 Hint

Think about preserving order across multiple keys.

Sorting multiple keys by repeated stable sorts from least to most important key preserves the order of previous keys, achieving a multi-key sort.

🔧 Debug

expert

Why Does This Sorting Code Fail to Preserve Order?

Consider this C++ code snippet that attempts to sort a vector of pairs by the second element while preserving the original order of pairs with equal second elements. Why does it fail to preserve order?

DSA C++

std::vector<std::pair<int,int>> v = {{1,2}, {2,1}, {3,2}, {4,1}};
std::sort(v.begin(), v.end(), [](auto& a, auto& b) {
    return a.second < b.second;
});
for (auto& p : v) {
    std::cout << "(" << p.first << "," << p.second << ") ";
}

A Because the output loop is missing a newline.

B Because the lambda comparator is incorrect and does not compare properly.

C Because the vector is not initialized correctly.

D Because std::sort is not stable, it can reorder pairs with equal second elements arbitrarily.

💡 Hint

Check if the sorting algorithm preserves order of equal keys.

std::sort is not stable, so it does not guarantee to keep the original order of elements with equal keys. To preserve order, std::stable_sort should be used.