
Category: algorithms  Component type: function 
template <class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class StrictWeakOrdering> void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
The two versions of sort differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
int A[] = {1, 4, 2, 8, 5, 7}; const int N = sizeof(A) / sizeof(int); sort(A, A + N); copy(A, A + N, ostream_iterator<int>(cout, " ")); // The output is " 1 2 4 5 7 8".
[1] Stable sorting is sometimes important if you are sorting records that have multiple fields: you might, for example, want to sort a list of people by first name and then by last name. The algorithm stable_sort does guarantee to preserve the relative ordering of equivalent elements.
[2] Earlier versions of sort used the quicksort algorithm (C. A. R. Hoare, Comp. J. 5, 1962), using a pivot chosen by median of three (R. C. Singleton, CACM 12, 1969). Quicksort has O(N log(N)) average complexity, but quadratic worstcase complexity. See section 5.2.2 of Knuth for a discussion. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. AddisonWesley, 1975.) The current implementation of sort, however, uses the introsort algorithm (D. R. Musser, "Introspective Sorting and Selection Algorithms", Software Practice and Experience 27(8):983, 1997.) whose worst case complexity is O(N log(N)). Introsort is very similar to medianofthree quicksort, and is at least as fast as quicksort on average.
Contact Us  Site Map  Trademarks  Privacy  Using this site means you accept its Terms of Use 
Copyright © 2009  2017 Silicon Graphics International. All rights reserved. 