22

Does anyone know both the expected running times and worst case running times for different implementations of std::nth_element? I use this algorithm nearly every day.

I'm specifically interested in the STL versions shipping with the recent Microsoft Compilers, but any information on this topic is helpful.

Please note that this is not a duplicate of this question. I understand which algorithms exist, but I'm interested in which implementations use which algorithms.

For background, there are well-known algorithms to do this. One is O(n) average case and O(n log n) worst case, one is O(n) worst case but slow in practice (median of medians). Also note that there is talk of interesting implementation strategies to get worst-case O(n) running times that are fast in practice. The standard says that this must be at worse O(n) average time.

Community
  • 1
  • 1
Chris A.
  • 6,817
  • 2
  • 25
  • 43
  • The standard says *Complexity: Linear on average.* Did you look up the header for the implementation? That can be a start. – dirkgently Jun 17 '12 at 02:11
  • Good point, I'm clarifying the question based on this. – Chris A. Jun 17 '12 at 02:14
  • A related [bug](https://connect.microsoft.com/VisualStudio/feedback/details/184518/incorrect-implementation-of-c-stl-nth-element-algorithm) where you may get some idea about the optimizations in VS. – dirkgently Jun 17 '12 at 02:18
  • Oh yeah, I've seen some implementations that below a certain length, just sort the array because it's fast enough. In my opinion, this is a boundary case and doesn't violate O(n) average case because of the definition of O(n) complexity necessarily being only meaningful for large n. – Chris A. Jun 17 '12 at 02:22
  • @dirkgently In other words, this isn't a bug at all. – Chris A. Jun 17 '12 at 02:31
  • It *is* marked as *Not a defect*. I just wanted you to take a look at it since you said you wanted some ideas about VS's implementation. – dirkgently Jun 17 '12 at 02:33

3 Answers3

18

The expected running time is O(N) The worst case running time for most implemententations is O(N * N) because most implementations use QuickSelect and it could be that QuickSelect runs into bad partitions. That is true for Microsoft VS2008, VS2010 & VS2012.

Now with the new ISO C++ 2011 standard, the complexity for std::sort has been tightened up - it is guaranteed to be O(N * log N) and has no worse case as David Musser's IntroSort is used: - use QuickSort and if parts of the array experience bad partitioning, swap to heapsort.

Ideally exactly the same should apply std::nth_element but the ISO C++ 2011 standard has not tightened up the complexity requirements. So std::nth_element could be O(N * N) in the worst case. This could be because in David Musser's original paper (see here) he did not mention what algorithm should be swapped to if QuickSelect goes bad.

In the worst case, the median-of-medians using groups of 5 could be used (I have seen a paper the recommended groups of 7 but cannot find it). So a quality implementation of std::nth_element could use QuickSelect and swap to median-of-medians if partitioning goes bad. This would guarantee O(N) behaviour. QuickSelect can be improved by using sampling making the worst case unlikely but not impossible.

SJHowe
  • 756
  • 5
  • 11
  • Great answer, I just now saw it. When you say "and has no worse case as David Musser's IntroSort is used: - use QuickSort and if parts of the array experience bad partitioning, swap to heapsort." you mean the worst case is O(N*log N) right? Or did I misunderstand? – Chris A. Oct 21 '14 at 23:20
  • IntraSelect : Uses QuickSelect and swaps to Median-of-Medians in groups of 5 elements if QS goes bad. Average and Worse case would be O(N). MIcrosoft do not check for badness and swap to M-of-M, therefore their nth_element could be O(N * N) in worse case last time I looked at VS2012. I have yet to see VS2013 code. – SJHowe Feb 02 '15 at 18:27
  • IntraSort : Uses QuickSort and swaps to HeapSort if QS goes bad. Average and Worse case would be O(N * log N). – SJHowe Feb 02 '15 at 18:28
  • 1
    "most implementations use QuickSelect" -- [GCC has used introselect (quickselect+heap select) since 4.2](https://github.com/gcc-mirror/gcc/commit/eab56c687196ef861da5130375728c796dd83f10#diff-263a3dc9c2d61114ffb9a72c204fa465). MSVS 2015 and 2017 still use pure quickselect though (and I know MS was what OP was most interested in). I haven't fully grokked [LLVM's](https://github.com/llvm-mirror/libcxx/blob/ed6c20e48d547bdda5c68ba1b8f79a16916683ab/include/algorithm#L5068) but it looks like it might be a pure quickselect. -- C++17 tightens up the time complexity on forms with an `ExecutionPolicy`. – ZachB Sep 08 '18 at 01:53
  • ZachB: Unfortunately heap select is not O(N). Therefore this choice is not great. I complained to GCC and had a bugzilla bug report on it. Median-of-median's in groups of 5 is O(N). So ideally Intraselect should do QuickSelect and if it goes bad, swap to M-of-M's. The ISO C++ 17 does not demand it, so no compiler vendor is doing more than offering QuickSelect (with no other algorithm if it goes bad). – SJHowe Sep 13 '18 at 11:56
8

The implementation in GCC 4.7 uses introspective selection by David Musser (here you have his paper giving details on introsort and introselect). According to those documents the worst-case execution time is O(n).

chappjc
  • 30,359
  • 6
  • 75
  • 132
betabandido
  • 18,946
  • 11
  • 62
  • 76
  • [This gcc bugzilla](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968) is probably relevant because it claims that the current implementation in libstdc++ doesn't meet the complexity requirements of the standard. – Dave Johansen Mar 16 '15 at 15:20
  • 3
    This is plain wrong. The worst case is O(n log n). It is written on the same wikipedia entry that you linked. – Nate Dec 07 '15 at 14:46
  • GCC uses introselect, but it's a version that is O(n log n). Some versions of introselect have O(n) worst-case. – ZachB Sep 08 '18 at 01:55
  • David Musser's original paper **never** said what algorithm should be used if quickselect goes bad. But if the median-of-medians algorithm is used in groups >= 5, then you can guarantee that Intraselect can be no worse than O(n). gcc bugzilla I complained at, as heapselect is **not** O(n). So a quality nth_element should use quickselect and median-of-medians for selection if quickselect goes bad. That would guarantee O(n). – SJHowe Sep 10 '18 at 17:18
0

cppreference says, first it sorts and then finds the nth element, but by this way average should be O(n log n) (by comparison based sorting algorithms), but they wrote average is O(n), seems incorrect except using sorting like radix sort, ... but because it has generic comparison based input, seems it's impossible to use radix sort or any other sort which is not comparison based. anyway, using fast sorting algorithms is better than using normal selection algorithm in practice (both memory and average time).

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
  • 2
    No, it says `std::nth_element` __partially__ sorts the range `[first,last)` so the `nth` element is in its correct place _as if_ the entire range was fully sorted. What it does is closer to a recursive partition than a full sort. – Blastfurnace Jun 17 '12 at 10:25
  • @SaeedAmiri It's certainly not a full sort. I [wrote an Stack Overflow tag wiki](http://stackoverflow.com/tags/nth-element/info) for `nth_element` which I think describes the output conditions succinctly. – Chris A. Jun 17 '12 at 10:40
  • @Blastfurnace, It partially sorts but still this sorting takes **O(n logn)** in **average**, if it's hard to see this, tell me, I'll add the proof. – Saeed Amiri Jun 18 '12 at 06:49
  • @ChrisA. Yes it partially sorts, but this doesn't affect the average case, when I reference to the specific link, sure I know what they wrote. – Saeed Amiri Jun 18 '12 at 06:54
  • The C++ standard guarantees that a compliant `std::nth_element` implementation has linear complexity on average, not O(n log n). If you disagree then take it up with ISO/IEC JTC1/SC22/WG21. – Blastfurnace Jun 18 '12 at 07:04
  • If want to refer to the published Standard it's section 25.4.2 paragraph 3. – Blastfurnace Jun 18 '12 at 07:15
  • @Blastfurnace, please provide some link (direct link), Also if God say something this will be done in O(n) with mentioned algorithm, God is wrong, so before downvoting 1. provide logical reason 2. at least show your reference with direct link (it's not my task to search what are you talking about). – Saeed Amiri Jun 22 '12 at 10:35
  • My reference is the [ISO C++ Standards Committee](http://www.open-std.org/jtc1/sc22/wg21/). You can download a draft copy of the [language standard at this link](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf). The `std::nth_element` reference is in section 25.4.2, starting on page 879. You can also read about the _quickselect_ and _introselect_ algorithms [here on Wikipedia](http://en.wikipedia.org/wiki/Selection_algorithm). – Blastfurnace Jun 22 '12 at 11:57
  • I just wanted to add that I'm not the downvoter. Have a nice day. – Blastfurnace Jun 22 '12 at 11:57
  • @Blastfurnace, Thanks, I'll read your reference and will update my answer by what I read and what I can prove. – Saeed Amiri Jun 23 '12 at 20:52
  • Blastfurnace, Saeed : Don't agree with either of you. nth_element does not sort, instead it partitions many times, zooming in on the nth element, discarding ranges . elements below the nth element are smaller or equal but in any order, elements above the nth element are larger or equal but in any order. CPPReference is incorrect when it says it "sorts", it partitions. Sorting, asymptotically, would not guarantee the complexity requirment of O(N). It maybe that some implementations use insertion sort for the last few elements which does not break the complexity requirements. – SJHowe Apr 29 '16 at 10:30