// How std::nth_element Works
// Purpose: Rearranges elements so that:
// The element at the nth position is the same as if the range were fully sorted.
// All elements before it are less than or equal to it.
// All elements after it are greater than or equal to it.
#include <iostream>
#include <vector>
#include <algorithm> // Required for std::nth_element
int main() {
std::vector<int> nums = {9, 2, 7, 4, 8, 3, 5};
// Find the 3rd smallest element (index 2 in 0-based indexing)
size_t n = 2;
std::nth_element(nums.begin(), nums.begin() + n, nums.end());
std::cout << "The 3rd smallest element is: " << nums[n] << "\n";
// Show partially ordered array
std::cout << "Vector after nth_element: ";
for (int num : nums) {
std::cout << num << " ";
}
}
/*
run:
Maximum sum = 26
*/
