Talk:cpp/algorithm/partial sort

Is the complexity right? Why does it not depend on middle element? Which algorithm has a log^2 complexity? How can it depend on available memory?

I was almost sure the right answer in N*log (M), where M = std::distance(first, middle)

Looks like a copy-paste error (from std::stable_sort). Thank you for reporting! --Cubbi 05:51, 17 June 2013 (PDT)

Why does std::partial_sort not use quickselsort? The expected time complexity of quickselsort should be O(MlogM+N), better than the currentlt used heap version. Are there any concerns?

possible implementation

I added possible implementation assuming it is in the std namespace. If it is not, then std::iter_swap should not be called using qualified name because it defeats the purpose of it being a customization point. Instead there should be using declaration and it should be called via unqualified id, fully analogous to swap, e.g.:

template<typename RandomIt, typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>> void heap_select(RandomIt begin, RandomIt middle, RandomIt end, const Compare &comp = {}) { using std::iter_swap; // pull name into scope std::make_heap(begin, middle, comp); for (auto i = middle; i != end; ++i) if (*i < *begin) { iter_swap(begin, i); // allow to find instance through ADL or whatever sift_down(begin, middle, comp); } }

-- Pavel

The algorithm here requires the iterator to be ValueSwappable, which is specified in terms of swap on the dereferenced object, implementations cannot call other functions like iter_swap. Only the ranges versions of the algorithms may consider functions like iter_swap to be customisation points via ranges::iter_swap due to the std::indirectly_swappable concept. --Ybab321 (talk) 11:02, 22 June 2021 (PDT)

If you use qualified name std::iter_swap, overloads found only by ADL will not be called, e.g.

std::vector<int> v = { 1,2 }; std::iter_swap(v.rbegin(), v.rbegin() + 1);

calls std::iter_swap.

If you write this with using declaration like this:

std::vector<int> v = { 1,2 }; using std::iter_swap; iter_swap(v.rbegin(), v.rbegin() + 1);

std::iter_swap(std::reverse_iterator) is called which is found using ADL. I think this is the desired behavior.

If the code was inside std, neither qualification, nor using declaration would be needed.

But whatever, I'm not up for an edit war.

-- Pavel

That was exactly my point, ADL should not be performed --Ybab321 (talk) 01:58, 23 June 2021 (PDT)

Well, you seem to be right. Then std::iter_swap should probably be replaced with using std::swap; swap(); to be more illustrative and to remove potential confusion.

-- Pavel

push/pop version

No one ever will and no one ever should implement partial sort via std::push_heap/std::pop_heap because it is significantly slower than the sift down version.

-- Pavel

Useful note for anyone thinking about reimplementing a stdlib function by looking at the cppreference possible implementation instead of one of many actual stdlib implementations --Ybab321 (talk) 01:58, 23 June 2021 (PDT)

@Pavel.

The "possible implementation" sections on this site is not necessarily for the best/fastest implementations, AFAIK.

Sometimes, a sketch of the solution would be enough, IMO. Real-world implementations tend to be bulky. And the code from cppreference impl. sections is not going to be used in production anyway.

Thank you for the participation. There are a lot of places here to apply one's best efforts.--Space Mission (talk) 02:14, 23 June 2021 (PDT)

My understanding is that examples should be good examples, not some random nonsence that may potentially exist just "because it can be done", so people who don't know how it works (including beginners) and can't tell good from bad at this point have good influence on them, instead of exposing them to horrendous code. If an anti-example is presented, it should be presented as such with clearly visible warning saying "don't do this", ideally with an explanation why you shouldn't do this.

I copy-pasted code from possible implementation section on cppreference more than once, so I would assume (or at least I want to assume) that the implementation is at least good enough if not absolutely optimal. I wouldn't expect (and I don't want to expect) that an example is absolute dog shit. But thanks for pointing it out, I will watch out for that on cppreference from now on.

-- Pavel

It's unspecified whether the implementations provided here are supposed to be good w.r.t. demonstrative value, speed, space, or any other metric. But, I'm quite confident in saying they're not supposed to be polyfills for projects that don't have the standard library available. Some algorithms and other pages are simple enough that there's basically no wrong way to implement them, and so we can more-or-less meet all the above goals; but I don't believe std::partial_sort is one of them. I personally believe that cppreference (the C++ documentation website) should prioritise demonstrative value wherever a trade-off needs to be made. The "first version" implementation you've given us is OK, it's one of many options to implement a decent partial heap sort, but Space Mission's "second version" implementation has so much more intuitive value and can be understood at a glance, I think it's better for the site. If I'm completely honest though, I don't like this particular algorithm having a possible implementation whatsoever, because of it being such an open-ended problem, and I think the English is clearer than the code in both cases. --Ybab321 (talk) 04:07, 24 June 2021 (PDT)

Fair. The whole point of this excercise was to show which algorithm is typically used, and what one should expect from it, i.e. that, to be somewhat optimal, it should only be used for small constant numbers of selected elements. If implementation example is confusing (as it seems to be now), it should probably be removed.

-- Pavel