Jump to content

Talk:Sort (C++)

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
  1. include <iostream>
#include <algorithm>

int main() {
  int array[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30 };
  int elements = sizeof(array) / sizeof(int); 
  std::sort(a, a + elements);
  for (int i = 0; i < elements; ++i) std::cout << array[i] << ' ';
  return 0;
}

a is not defined here. What is it supposed to be? --Abdull 12:21, 23 June 2006 (UTC)[reply]

-- Looks like it should be "array"... I'm fixing it. Dlong 04:42, 28 July 2006 (UTC) --[reply]

Example needed

I'm a newb cpp prog (taking a course in college). The optional third argument function compare has no example given. I believe it's supposed to go like this:


bool compr(stuff a, ...., etc b) {

   //stuff 

}

....
sort(a.begin(),a.end(),compr);


Can someone who knows what the real way to do it is put the example in? --128.113.193.67 09:45, 15 September 2006 (UTC)[reply]

Something like this, depending on your data type: bool compr(stuff a, stuff b) { return a < b; } --Spoon! 06:15, 15 October 2007 (UTC)[reply]

Referneces

[edit]

Does anyone have the references for the speed of implementation, including practical examples. We could generate them by ourselves, but that would be WP:OR.... 121.44.5.248 (talk) 13:43, 1 June 2008 (UTC)[reply]

Renaming this article to follow a consistent convention

[edit]

Hi, I am currently considering renaming this article to conform to a common convention for C++ Standard Library components. The full discussion can be found here. decltype 09:47, 6 March 2009 (UTC)[reply]

Algorithmic complexity

[edit]

In the paragraph about comparison between C++ sort and C qsort it's said that sort's worst-case complexity is O(N log N). This may be true for the SGI implementation, but other implementations may still have a worst-case complexity of O(N * N). Or is this a general implementation requirement for sort()? At least Bjarne Stroustrup mentions O(N * N) as the limit in "The C++ Programming Language", Special edition.

See also http://www.cplusplus.com/reference/algorithm/sort.html —Preceding unsigned comment added by Ctrlw (talkcontribs) 17:42, 19 March 2009 (UTC)[reply]

Absolutely correct, except that it's not explicitly stated what the worst-case complexity of sort is. The average complexity is N log N. I have corrected the article in this regard. decltype (talk) 02:41, 20 March 2009 (UTC)[reply]
The first referenced document does say what the worst-case complexity of sort is. The definition of sort on page 911 says, "Complexity: O(N log(N)) (where N == last - first) comparisons." And indeed that's what this article says, that complexity is O(N log(N)). But the definition of 'Complexity' on page 444 says, "Complexity requirements specified in the library clauses are upper bounds". So I'm going to change the article to replace that is. DavidForthoffer (talk) 00:41, 16 July 2022 (UTC)[reply]