Welcome to this insightful session, where our aim is to master the complexities of the illustrious applications of sorting algorithms. Today's voyage links two problems: "Find the K-th smallest element in a List" and "Count the Number of Inversions in a List". These problems mirror practical scenarios, and the efficient techniques used to solve them provide valuable demonstrations of the application of sorting algorithms. By solving these two problems, we'll see how Quick Sort and Merge Sort knowledge applies here and helps provide efficient implementations for both questions.

Let's dive into these captivating problems!

Our first problem presents a list of integers and the number k. The challenge is finding the k-th smallest element in that given list. To further elucidate, k starts from 1, so for k = 1, you are seeking to find the smallest element; if k = 2, you're searching for the second smallest element, and so on. By the conclusion of this lesson, you'll be highly skilled at performing this task!

Sorting steps in here to offer an efficient solution! The Quick Sort algorithm, a splendid application of divide and conquer, can solve this problem more efficiently. By selecting the right pivot for partitioning, the input list is divided into two parts: a left partition, which contains elements less than the pivot, and a right partition, which includes elements greater than the pivot.

If the pivot's position after elements are repositioned is the same as k, we have the k-th smallest element. If k is less than the pivot's position, the task is carried forward on the left partition; otherwise, on the right partition.

Our C++ solution mirrors this efficient approach as follows. Firstly, we define the partition procedure, the same way we do it in the quicksort:

#include <vector>
#include <utility> // For std::swap

int partition(std::vector<int>& arr, int start, int end) {
    int pivot = arr[start];
    int i = start;

    for (int j = start + 1; j <= end; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i], arr[start]);
    return i;
}

Then, we define the findKthSmallest function, essentially working as quicksort, but chasing a different goal:

#include <iostream>
#include <vector>
#include <climits> // For INT_MIN and INT_MAX

int kthSmallest(std::vector<int>& arr, int start, int end, int k);

int findKthSmallest(std::vector<int>& numbers, int k) {
    if (numbers.empty() || numbers.size() < k)
        return INT_MIN;
    return kthSmallest(numbers, 0, numbers.size() - 1, k);
}

int kthSmallest(std::vector<int>& arr, int start, int end, int k) {
    if (k > 0 && k <= end - start + 1) {
        int pos = partition(arr, start, end);

        if (pos - start == k - 1) {
            return arr[pos];
        }

        if (pos - start > k - 1) {
            return kthSmallest(arr, start, pos - 1, k);
        }

        return kthSmallest(arr, pos + 1, end, k - pos + start - 1);
    }

    return INT_MAX;
}

int main() {
    std::vector<int> numbers = {1, 7, 2, 4, 2, 1, 6};
    std::cout << findKthSmallest(numbers, 5) << std::endl;  // It should print 4
    return 0;
}

After we form the partitions, we compare the pivot's position to k. If the positions match, our pivot is the k-th smallest element. If our k is smaller, we look at the left partition; otherwise, the right one.

Our second problem entails a list of integers; your task is to deduce the number of inversions in the list.

An inversion is a pair of elements where the larger element appears before the smaller one. In other words, if we have two indices i and j, where i < j and the element at position i is greater than the element at position j (numbers[i] > numbers[j]), we have an inversion.

For example, for numbers = {4, 2, 1, 3}, there are four inversions: (4, 2), (4, 1), (4, 3), and (2, 1).

First, let's define a supportive struct to store our counter for each subarray:

#include <vector>

struct Result {
    std::vector<int> sorted;
    long inversions;

    Result(std::vector<int> sorted, long inversions)
        : sorted(sorted), inversions(inversions) {}
};

Then, implement the merge sort that keeps track of the number of inversions:

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

Result mergeAndCountInversions(const std::vector<int>& left, const std::vector<int>& right);

Result countInversions(std::vector<int> arr) {
    if (arr.size() <= 1) {
        return Result(arr, 0);
    }

    size_t middle = arr.size() / 2;
    std::vector<int> left(arr.begin(), arr.begin() + middle);
    std::vector<int> right(arr.begin() + middle, arr.end());

    Result leftResult = countInversions(left);
    Result rightResult = countInversions(right);
    Result result = mergeAndCountInversions(leftResult.sorted, rightResult.sorted);

    return Result(result.sorted, leftResult.inversions + rightResult.inversions + result.inversions);
}

Result mergeAndCountInversions(const std::vector<int>& left, const std::vector<int>& right) {
    std::vector<int> merged(left.size() + right.size());
    size_t i = 0, j = 0;
    long inversions = 0;

    for (size_t k = 0; k < merged.size(); ++k) {
        if (i < left.size() && (j >= right.size() || left[i] <= right[j])) {
            merged[k] = left[i++];
        } else {
            merged[k] = right[j++];
            inversions += left.size() - i;
        }
    }
    return Result(merged, inversions);
}

int main() {
    std::vector<int> numbers = {4, 2, 1, 3};
    Result res = countInversions(numbers);
    std::cout << "Number of inversions: " << res.inversions << std::endl;  // It should print 4
    return 0;
}

While performing the merge in Merge Sort, we have added an additional counter to track inversions. If we come across an element in the right array that is smaller than an element in the left, we increment the counter by the number of items remaining in the left array. These all form inversions as per our problem's definition.

During today's lesson, we thoroughly inspected the advanced applications of Quick Sort and Merge Sort algorithms through the dissection of two exciting problems. We went from recognizing the issues, proposing naïve methods, progressing towards efficient approaches, and executing the C++ solutions.

You're now ready to flex those coding muscles! We have covered a substantial amount of theory and strongly advocate that real-world application solidifies the lessons learned. Be prepared for the forthcoming exercises, where you'll apply the logic imbibed in this session to similar problems. Let's get hands-on!