-
-
Notifications
You must be signed in to change notification settings - Fork 1.5k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
typo in kth order statistic #1215
Comments
On a side note, I read up about the deterministic linear median of medians; it's pretty cool |
Also I was wondering if it's possible to implement median of medians iteratively. It seems pretty hard |
I think it would be cool to switch the code on https://cp-algorithms.com/sequences/k-th.html to median of medians I mean is anyone using the current code, noting that the stl already implements quick select? Also the stl's has a better worst case, which can matter: hacks on codeforces |
|
You seem to be correct gcc does a worst case |
another interesting point: if you do quicksort as in https://en.cppreference.com/w/cpp/algorithm/partition where you have 2 middles: and if you use median of medians to get exact median in deterministic linear time, then quicksort is now bounded by O(n log(number of distinct values)) (<= O(nlogn)) so for example, sorting |
"deterministic linear solution is implemented in C++ standard library as std::nth_elemen"
https://cp-algorithms.com/sequences/k-th.html
but I think the STL implements the nondeterministic one/deterministic nlogn one
https://github.com/gcc-mirror/gcc/blob/9693459e030977d6e906ea7eb587ed09ee4fddbd/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1913,L1933
The text was updated successfully, but these errors were encountered: