Talk:Sort (C++)

C/C++ Low‑importance

	This article is within the scope of WikiProject C/C++, a collaborative effort to improve the coverage of C and C++ topics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.C/C++Wikipedia:WikiProject C/C++Template:WikiProject C/C++C/C++ articles
Low	This article has been rated as Low-importance on the importance scale.

Computing: Software Low‑importance

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles
Low	This article has been rated as Low-importance on the project's importance scale.
	This article is supported by WikiProject Software (assessed as Low-importance).

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 (talk • contribs) 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]