0

Complexity of std::nth_element shoule be O(n). But I just found that the array has been sorted after applying nth_element on it.

My compiler is VC 10.0 The output is :

5778 31610 23991 29586 28160 13739 14583 25240 17362 23487 8027 14287 29770 24131 28491 1993 29247 4865 23674 22591
1993 4865 5778 8027 13739 14287 14583 17362 22591 23487 23674 23991 24131 25240 28160 28491 29247 29586 29770 31610

and my code is 

int main() {
  srand(time(0));
  vector<int> v(20);
  generate(v.begin(), v.end(), []() {return rand();});
  copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  cout << "\n";

  nth_element(v.begin(), v.begin() + 4, v.end());
  copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  cout << "\n";
  return 0;
}
Cong Ma
  • 1,241
  • 1
  • 11
  • 20
  • O(n) in the range [v.begin(), v.end()) **on average**. – 101010 Dec 09 '16 at 23:15
  • your output is not really sorted - `nth_element` only does *partial sorting*, like one step of quicksort, pivoting around the nth element – Ap31 Dec 09 '16 at 23:20

0 Answers0