stl:algorithm:sort

sort

Syntax:

    #include <algorithm>
    void sort( random_iterator start, random_iterator end );
    void sort( random_iterator start, random_iterator end, StrictWeakOrdering cmp );

The sort() algorithm sorts the elements in the range [start,end) into ascending order. If two elements are equal, there is no guarantee what order they will be in.

If the strict weak ordering function object cmp is given, then it will be used to compare two objects instead of the < operator.

The algorithm behind sort() is the introsort algorithm. sort() runs in O(N log (N)) time (average and worst case) which is faster than polynomial time but slower than linear time.

Note that sort() will only work with random access iterators. So you cannot use sort() on the iterators of a “list” (linked list); you should use list's own sort method to sort it instead.

For example, the following code sorts a vector of integers into ascending order:

   vector<int> v;
   v.push_back( 23 );
   v.push_back( -1 );
   v.push_back( 9999 );
   v.push_back( 0 );
   v.push_back( 4 );
 
   cout << "Before sorting: ";
   for( unsigned int i = 0; i < v.size(); i++ ) {
     cout << v[i] << " ";
   }
   cout << endl;
 
   sort( v.begin(), v.end() );
 
   cout << "After sorting: ";
   for( unsigned int i = 0; i < v.size(); i++ ) {
     cout << v[i] << " ";
   }
   cout << endl;

When run, the above code displays this output:

   Before sorting: 23 -1 9999 0 4
   After sorting: -1 0 4 23 9999

Alternatively, the following code uses the sort() function to sort a normal array of integers, and displays the same output as the previous example:

   int array[] = { 23, -1, 9999, 0, 4 };
   unsigned int array_size = 5;
 
   cout << "Before sorting: ";
   for( unsigned int i = 0; i < array_size; i++ ) {
     cout << array[i] << " ";
   }
   cout << endl;
 
   sort( array, array + array_size );
 
   cout << "After sorting: ";
   for( unsigned int i = 0; i < array_size; i++ ) {
     cout << array[i] << " ";
   }
   cout << endl;

This next example shows how to use sort() with a user-specified comparison function. The function cmp is defined to do the opposite of the < operator. When sort() is called with cmp used as the comparison function, the result is a list sorted in descending, rather than ascending, order:

   bool cmp( int a, int b ) {
     return a > b;
   }
 
   ...
 
   vector<int> v;
   for( int i = 0; i < 10; i++ ) {
     v.push_back(i);
   }
 
   cout << "Before: ";
   for( int i = 0; i < 10; i++ ) {
     cout << v[i] << " ";
   }
   cout << endl;
 
   sort( v.begin(), v.end(), cmp );
 
   cout << "After: ";
   for( int i = 0; i < 10; i++ ) {
     cout << v[i] << " ";
   }
   cout << endl;