英文:
How can I sort value by std::nth_element function?
问题
以下是代码的翻译部分：
实际上，我正在尝试获取部分排序的值。在这里，我使用了`std::nth_element`函数，但它未给我期望的结果。
#include <bits/stdc++.h>
using namespace std;
void print(vector<int> data)
{
for(int i : data)
cout << i << " ";
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r+", stdin);
freopen("output.txt", "w+", stdout);
#endif
vector<int> v({5,7,4,2,8,6,1,9,0,3});
auto middle = v.begin() + v.size() / 2;
nth_element(v.begin(), middle, v.end(), greater<int>());
print(v);
}
期望的结果是：
9 8 7 6 5 4 1 2 0 3
但我得到的结果是：
6 7 9 8 5 4 1 2 0 3
英文:
Actually, I am trying to get values that are partially sorted. I used std::nth_element function, here, but it is not giving me the expected result.
#include <bits/stdc++.h>
using namespace std;
void print(vector<int>data)
{
for(int i:data)
cout<<i<<" ";
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r+", stdin);
freopen("output.txt", "w+", stdout);
#endif
vector<int> v({5,7,4,2,8,6,1,9,0,3});
auto middle=v.begin()+v.size()/2;
nth_element(v.begin(), middle ,v.end(), greater<int>());
print(v);
}
expected result is
9 8 7 6 5 4 1 2 0 3
but I am getting this
6 7 9 8 5 4 1 2 0 3
答案1
得分: 2
nth_element是一个部分排序算法，它重新排列[first, last)范围内的元素，使得：
- 由
nth指向的元素被更改为在[first, last)排序后该位置上的元素。 - 这个新的
nth元素之前的所有元素都小于或等于这个新的nth元素之后的元素。
更正式地说，nth_element以升序部分排序范围[first, last)，以满足条件!(*j < *i)（对于(1-2)，或comp(*j, *i) == false对于(3-4))，对于范围[first, nth)中的任何i和范围[nth, last)中的任何j都成立。放置在第n个位置的元素正是如果范围被完全排序会出现在该位置上的元素。
请注意，它并没有说范围[first, nth)将被排序，也不会说范围[nth, last)将被排序，它仅保证第n个元素的位置。您可以将其视为一个分区算法。
如果您希望仅使用此函数获得完整的排序顺序，您需要多次应用它，可以递归或在循环中使用。
英文:
Let's read the description of the algorithm<sup>1</sup>, emphasis mine:
>C++
>template< class RandomIt > // (1)
>void nth_element( RandomIt first, RandomIt nth, RandomIt last );
>
>template< class RandomIt, class Compare > // (3)
>void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );
>
>
> nth_element is a partial sorting algorithm that rearranges elements in [first, last) such that:
>
> - The element pointed at by nth is changed to whatever element would occur in that position if [first, last) were sorted.
> - All of the elements before this new nth element are less than or equal to the elements after the new nth element.
>
> More formally, nth_element partially sorts the range [first, last) in ascending order so that the condition !(*j < *i) (for (1-2), or comp(*j, *i) == false for (3-4)) is met for any i in the range [first, nth) and for any j in the range [nth, last). The element placed in the nth position is exactly the element that would occur in this position if the range was fully sorted.
Note that it doesn't say that the range [first, nth) will be sorted, nor will be the range [nth, last), it only guarantees the position of the nth element. You can think of it as a partition algorithm.
If you want a complete order using only this function, you need to apply it multiple times, either recursively or in a loop.
<sup>1) https://en.cppreference.com/w/cpp/algorithm/nth_element </sup>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论