Why Sorting Matters and How It Unlocks Other Algorithms in DSA C++ - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sorting and Searching in a Sorted Array

What is the output of the following C++ code that sorts an array and then performs a binary search for the number 7?

DSA C++

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {10, 3, 7, 1, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    sort(arr, arr + n);
    bool found = binary_search(arr, arr + n, 7);
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl << (found ? "Found" : "Not Found") << endl;
    return 0;
}

A

10 3 7 1 9 
Found

B

1 3 7 9 10 
7

C

1 3 7 9 10 
Not Found

D

1 3 7 9 10 
Found

💡 Hint

Remember that std::sort sorts the array in ascending order and binary_search requires a sorted array.

The array is sorted to 1 3 7 9 10. Then binary_search finds 7 in the sorted array, so it prints 'Found'.

🧠 Conceptual

intermediate

Why Sorting Helps in Finding Duplicates

Why does sorting an array first make it easier to find duplicates?

A Because sorting changes the values of elements to unique ones.

B Because sorting removes duplicates automatically.

C Because after sorting, duplicates will be next to each other, so we only need to check adjacent elements.

D Because sorting splits the array into two halves, making duplicates impossible.

💡 Hint

Think about how duplicates appear in a sorted list.

Sorting arranges equal elements next to each other, so checking neighbors is enough to find duplicates efficiently.

🔧 Debug

advanced

Identify the Error in Merge Sort Implementation

What error does the following C++ merge sort code produce when run?

DSA C++

#include <iostream>
using namespace std;

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    for(int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for(int j = 0; j < n2; j++)
        R[j] = arr[m + j];
    int i = 0, j = 0, k = l;
    while(i < n1 && j < n2) {
        if(L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while(i < n1) arr[k++] = L[i++];
    while(j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if(l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

A The code compiles but outputs an unsorted array.

B Compilation error because variable-length arrays are not allowed in standard C++.

C Runtime error due to accessing out-of-bounds in array R.

D Logical error: merge function merges incorrectly causing infinite recursion.

💡 Hint

Check the declarations of arrays L and R inside merge function.

Standard C++ does not allow variable-length arrays like int L[n1]; This causes compilation error.

🚀 Application

advanced

Using Sorting to Find the Intersection of Two Arrays

Given two unsorted arrays, which approach correctly finds their intersection using sorting?

A Sort both arrays, then use two pointers to find common elements in O(n log n + m log m) time.

B Sort only the first array, then for each element in second array, do a linear search in the first array.

C Sort the second array, then use binary search for each element of the first array in the second array.

D Sort both arrays, then merge them into one sorted array to get the intersection.

💡 Hint

Think about how two sorted arrays can be traversed efficiently.

Sorting both arrays allows using two pointers to find common elements efficiently without repeated searching.

❓ Predict Output

expert

Output of Counting Inversions Using Merge Sort

What is the output of the following C++ code that counts the number of inversions in an array using merge sort?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

long long merge(vector<int>& arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    vector<int> L(n1), R(n2);
    for(int i = 0; i < n1; i++) L[i] = arr[l + i];
    for(int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    long long inv_count = 0;
    while(i < n1 && j < n2) {
        if(L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
            inv_count += (n1 - i);
        }
    }
    while(i < n1) arr[k++] = L[i++];
    while(j < n2) arr[k++] = R[j++];
    return inv_count;
}

long long mergeSort(vector<int>& arr, int l, int r) {
    long long inv_count = 0;
    if(l < r) {
        int m = l + (r - l) / 2;
        inv_count += mergeSort(arr, l, m);
        inv_count += mergeSort(arr, m + 1, r);
        inv_count += merge(arr, l, m, r);
    }
    return inv_count;
}

int main() {
    vector<int> arr = {2, 4, 1, 3, 5};
    long long result = mergeSort(arr, 0, arr.size() - 1);
    cout << result << endl;
    return 0;
}

A

3

B

4

C

2

D

5

💡 Hint

Count pairs (i, j) where i < j and arr[i] > arr[j].

The inversions are (2,1), (4,1), (4,3) totaling 3 inversions.

Practice

1. Why is sorting an important step before applying many algorithms in data structures?

easy

A. Because sorting changes the data type to integers

B. Because sorting arranges data to make searching and merging easier and faster

C. Because sorting deletes duplicate elements automatically

D. Because sorting encrypts the data for security

Solution

1. Step 1: Understand the role of sorting

   Sorting arranges data in order, which helps algorithms like binary search or merge to work efficiently.

2. Step 2: Identify benefits of sorting

   Sorted data allows faster searching and easier merging because elements are in a predictable order.

3. Final Answer:

   Because sorting arranges data to make searching and merging easier and faster -> Option B

4. Quick Check:

   Sorting helps algorithms work faster = C [OK]

Hint: Sorting organizes data to speed up other algorithms [OK]

Common Mistakes:

• Thinking sorting removes duplicates automatically
• Confusing sorting with data encryption
• Believing sorting changes data types

2. Which of the following is the correct C++ syntax to sort an integer vector named nums in ascending order?

easy

A. nums.sort();

B. sort(nums, 0, nums.size());

C. sort(nums.begin(), nums.end());

D. sort(nums.begin(), nums.end(), greater<int>());

Solution

1. Step 1: Recall C++ STL sort syntax

   The standard way to sort a vector is using sort(nums.begin(), nums.end());.

2. Step 2: Check other options

   nums.sort(); is invalid because vectors don't have a sort() method. sort(nums, 0, nums.size()); is incorrect syntax. sort(nums.begin(), nums.end(), greater<int>()); sorts in descending order, not ascending.

3. Final Answer:

   sort(nums.begin(), nums.end()); -> Option C

4. Quick Check:

   Use STL sort with begin and end iterators = B [OK]

Hint: Use sort with begin() and end() for vectors [OK]

Common Mistakes:

• Trying to call sort as a vector method
• Using wrong parameters for sort
• Confusing ascending and descending order syntax

3. What will be the output of the following C++ code?

std::vector<int> v = {4, 2, 5, 1};
sort(v.begin(), v.end());
for (int x : v) std::cout << x << " ";

medium

A. 1 4 2 5

B. 5 4 2 1

C. 4 2 5 1

D. 1 2 4 5

Solution

1. Step 1: Understand the initial vector

   The vector starts as {4, 2, 5, 1}.

2. Step 2: Apply sort in ascending order

   After sorting, the vector becomes {1, 2, 4, 5}.

3. Step 3: Print elements in order

   The loop prints each element followed by a space: "1 2 4 5 "

4. Final Answer:

   1 2 4 5 -> Option D

5. Quick Check:

   Sorted vector prints in ascending order = A [OK]

Hint: Sorting arranges numbers from smallest to largest [OK]

Common Mistakes:

• Assuming sort reverses order
• Printing original vector without sorting
• Confusing ascending with descending order

4. The following code is intended to sort a vector nums but it causes a compilation error. What is the error?

std::vector<int> nums = {3, 1, 4};
sort(nums, nums + nums.size());

medium

A. Incorrect use of pointers with vector; should use iterators

B. Vectors cannot be sorted using sort function

C. Missing semicolon after vector declaration

D. sort requires a comparison function as third argument

Solution

1. Step 1: Identify the error in sort parameters

   The code uses nums and nums + nums.size(), which is invalid for vectors because vectors do not support pointer arithmetic.

2. Step 2: Correct usage for vector sorting

   We should use iterators: sort(nums.begin(), nums.end()); to sort a vector.

3. Final Answer:

   Incorrect use of pointers with vector; should use iterators -> Option A

4. Quick Check:

   Use iterators, not pointers, to sort vectors = A [OK]

Hint: Use begin() and end() iterators to sort vectors [OK]

Common Mistakes:

• Trying to use pointer arithmetic on vectors
• Forgetting vector uses iterators, not raw pointers
• Assuming sort always needs a third argument

5. You have two sorted arrays: A = {1, 3, 5} and B = {2, 4, 6}. Which approach best uses sorting to merge them into a single sorted array C efficiently?

hard

A. Use two pointers to merge A and B into C without extra sorting

B. Add elements of B to A and sort A repeatedly after each insertion

C. Sort A and B separately again before merging

D. Concatenate A and B, then sort the combined array

Solution

1. Step 1: Understand the arrays are already sorted

   Both A and B are sorted, so we can merge them efficiently without sorting again.

2. Step 2: Use two-pointer merge technique

   Using two pointers, one for each array, we compare elements and build C in sorted order in O(n) time.

3. Step 3: Avoid unnecessary sorting

   Concatenating and sorting or sorting repeatedly is less efficient than merging sorted arrays directly.

4. Final Answer:

   Use two pointers to merge A and B into C without extra sorting -> Option A

5. Quick Check:

   Merge sorted arrays with two pointers = D [OK]

Hint: Merge sorted arrays with two pointers, no extra sorting [OK]

Common Mistakes:

• Sorting concatenated arrays unnecessarily
• Sorting arrays again before merging
• Sorting after each insertion causing inefficiency