Skip to content. Skip to navigation

ICTP Portal

Sections
You are here: Home Manuals on-line PGI Compiler pgC_lib sort
Personal tools
Document Actions

sort



Click on the banner to return to the class reference home page.

sort


Algorithm

Summary

Templated algorithm for sorting collections of entities.

Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

Synopsis

#include <algorithm>

template <class RandomAccessIterator>
void sort (RandomAccessIterator first, 
           RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, 
           RandomAccessIterator last, Compare comp);

Description

The sort algorithm sorts the elements in the range [first, last) using either the less than (<) operator or the comparison operator comp. If the worst case behavior is important stable_sort or partial_sort should be used.

Complexity

sort performs approximately NlogN, where N equals last - first, comparisons on the average.

Example

//
// sort.cpp
//
 #include <vector>
 #include <algorithm>
 #include <functional>
 #include <iostream.h>

 struct associate
 {
   int num;
   char chr;

   associate(int n, char c) : num(n), chr(c){};
   associate() : num(0), chr('\0'){};
 };

 bool operator<(const associate &x, const associate &y)
 {
   return x.num < y.num;
 }

 ostream& operator<<(ostream &s, const associate &x)
 {
   return s << "<" << x.num << ";" << x.chr << ">";
 }


 int main ()
 {
   vector<associate>::iterator i, j, k;

   associate arr[20] = 
        {associate(-4, ' '), associate(16, ' '),
         associate(17, ' '), associate(-3, 's'),
         associate(14, ' '), associate(-6, ' '),
         associate(-1, ' '), associate(-3, 't'),
         associate(23, ' '), associate(-3, 'a'),
         associate(-2, ' '), associate(-7, ' '),
         associate(-3, 'b'), associate(-8, ' '),
         associate(11, ' '), associate(-3, 'l'),
         associate(15, ' '), associate(-5, ' '),
         associate(-3, 'e'), associate(15, ' ')};


   // Set up vectors
   vector<associate> v(arr, arr+20), v1((size_t)20), 
                 v2((size_t)20);

   // Copy original vector to vectors #1 and #2
   copy(v.begin(), v.end(), v1.begin());
   copy(v.begin(), v.end(), v2.begin());

   // Sort vector #1
   sort(v1.begin(), v1.end());

   // Stable sort vector #2
   stable_sort(v2.begin(), v2.end());

   // Display the results
   cout << "Original    sort      stable_sort" << endl;
   for(i = v.begin(), j = v1.begin(), k = v2.begin();
       i != v.end(); i++, j++, k++)
   cout << *i << "     " << *j << "     " << *k << endl;

   return 0;
 }

Output :
Original    sort      stable_sort
<-4; >     <-8; >     <-8; >
<16; >     <-7; >     <-7; >
<17; >     <-6; >     <-6; >
<-3;s>     <-5; >     <-5; >
<14; >     <-4; >     <-4; >
<-6; >     <-3;e>     <-3;s>
<-1; >     <-3;s>     <-3;t>
<-3;t>     <-3;l>     <-3;a>
<23; >     <-3;t>     <-3;b>
<-3;a>     <-3;b>     <-3;l>
<-2; >     <-3;a>     <-3;e>
<-7; >     <-2; >     <-2; >
<-3;b>     <-1; >     <-1; >
<-8; >     <11; >     <11; >
<11; >     <14; >     <14; >
<-3;l>     <15; >     <15; >
<15; >     <15; >     <15; >
<-5; >     <16; >     <16; >
<-3;e>     <17; >     <17; >
<15; >     <23; >     <23; >

Warning

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

See Also

stable_sort, partial_sort, partial_sort_copy


©Copyright 1996, Rogue Wave Software, Inc.


Powered by Plone This site conforms to the following standards: