C++/STL Algorithms Sorting/sort

Материал из C\C++ эксперт
Перейти к: навигация, поиск

Sort all element in an array

<source lang="cpp">

/* The following code example is taken from the book

* "The C++ Standard Library - A Tutorial and Reference"
* by Nicolai M. Josuttis, Addison-Wesley, 1999
*
* (C) Copyright Nicolai M. Josuttis 1999.
* Permission to copy, use, modify, sell and distribute this software
* is granted provided this copyright notice appears in all copies.
* This software is provided "as is" without express or implied
* warranty, and with no claim as to its suitability for any purpose.
*/
  1. include <iostream>
  2. include <algorithm>
  3. include <functional>
  4. include <iterator>

using namespace std; int main() {

   int coll[] = { 5, 6, 2, 4, 1, 3 };
   // sort beginning with the second element
   sort (coll, coll+6);
   // print all elements
   copy (coll, coll+6,
         ostream_iterator<int>(cout," "));
   cout << endl;

} /* 1 2 3 4 5 6

*/        
   
 </source>


Sort a string array with sort()

<source lang="cpp">

  1. include <iostream>
  2. include <algorithm>
  3. include <string>

using namespace std; int main() {

  string words[5] = { "ABCD", "BCDEF", "CERF","DERT", "EFRE"};
  string*   where;
  where = find(words, words + 5, "CD");
  
  cout << *++where << endl;                
  
  sort(words, words + 5);
  
  where = find(words, words + 5, "ER");
  cout << *++where << endl;              

}


 </source>


Sort a subset of the container

<source lang="cpp">

  1. include <cstdlib>
  2. include <iostream>
  3. include <vector>
  4. include <functional>
  5. include <algorithm>

using namespace std; void show(const char *msg, vector<int> vect); int main() {

 vector<int> v(10);
 for(unsigned i=0; i < v.size(); i++)
   v[i] = rand() % 100;
 show("Original order:", v);
 sort(v.begin()+2, v.end()-2);
 show("sorting elements v[2] to v[7] into natural order:", v);
 return 0;

} void show(const char *msg, vector<int> vect) {

 cout << msg << endl;
 for(unsigned i=0; i < vect.size(); ++i)
   cout << vect[i] << endl;
 

}


 </source>


Sort a vector and print out the sorted elements

<source lang="cpp">

/* The following code example is taken from the book

* "The C++ Standard Library - A Tutorial and Reference"
* by Nicolai M. Josuttis, Addison-Wesley, 1999
*
* (C) Copyright Nicolai M. Josuttis 1999.
* Permission to copy, use, modify, sell and distribute this software
* is granted provided this copyright notice appears in all copies.
* This software is provided "as is" without express or implied
* warranty, and with no claim as to its suitability for any purpose.
*/
  1. include <iostream>
  2. include <vector>
  3. include <algorithm>

using namespace std; int main() {

   vector<int> coll;
   vector<int>::iterator pos;
   // insert elements from 1 to 6 in arbitrary order
   coll.push_back(2);
   coll.push_back(5);
   coll.push_back(4);
   coll.push_back(1);
   coll.push_back(6);
   coll.push_back(3);
   // sort all elements
   sort (coll.begin(), coll.end());
   // print all elements
   for (pos=coll.begin(); pos!=coll.end(); ++pos) {
       cout << *pos << " ";
   }

}

/* 

1 2 3 4 5 6

*/       
   
 </source>


Sort a vector into ascending order of id members

<source lang="cpp">

  1. include <iostream>
  2. include <cassert>
  3. include <vector>
  4. include <algorithm>
  5. include <functional>

using namespace std; class MyClass : public binary_function<MyClass, MyClass, bool> { public:

 int id;
 bool operator()(const MyClass& x, const MyClass& y) const {
    return x.id >= y.id;
 }
 friend ostream& operator<<(ostream& o, const MyClass& x) {
   o << x.id;
   return o;
 }

}; int main() {

 vector<MyClass> vector1(100);
 for (int i = 0; i != 100; ++i)
   vector1[i].id = 100 - i - 1;
 sort(vector1.begin(), vector1.end(), not2(MyClass()));
 for (int k = 0; k != 100; ++k)
   cout << vector1[k].id << " ";
 return 0;

} /* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 8

3 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 "

*/        
   
 </source>


Sort elements in deque

<source lang="cpp">

/* The following code example is taken from the book

* "The C++ Standard Library - A Tutorial and Reference"
* by Nicolai M. Josuttis, Addison-Wesley, 1999
*
* (C) Copyright Nicolai M. Josuttis 1999.
* Permission to copy, use, modify, sell and distribute this software
* is granted provided this copyright notice appears in all copies.
* This software is provided "as is" without express or implied
* warranty, and with no claim as to its suitability for any purpose.
*/
  1. include <iostream>
  2. include <vector>
  3. include <deque>
  4. include <list>
  5. include <set>
  6. include <map>
  7. include <string>
  8. include <algorithm>
  9. include <iterator>
  10. include <functional>
  11. include <numeric>

/* PRINT_ELEMENTS()

* - prints optional C-string optcstr followed by
* - all elements of the collection coll
* - separated by spaces
*/

template <class T> inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="") {

   typename T::const_iterator pos;
   std::cout << optcstr;
   for (pos=coll.begin(); pos!=coll.end(); ++pos) {
       std::cout << *pos << " ";
   }
   std::cout << std::endl;

} /* INSERT_ELEMENTS (collection, first, last)

* - fill values from first to last into the collection
* - NOTE: NO half-open range
*/

template <class T> inline void INSERT_ELEMENTS (T& coll, int first, int last) {

   for (int i=first; i<=last; ++i) {
       coll.insert(coll.end(),i);
   }

} using namespace std; int main() {

   deque<int> coll;
   INSERT_ELEMENTS(coll,1,9);
   INSERT_ELEMENTS(coll,1,9);
   PRINT_ELEMENTS(coll,"on entry: ");
   // sort elements
   sort (coll.begin(), coll.end());
   PRINT_ELEMENTS(coll,"sorted:   ");

} /* on entry: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 sorted: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

*/        
   
 </source>


Sort elements reversely with custom function

<source lang="cpp">

/* The following code example is taken from the book

* "The C++ Standard Library - A Tutorial and Reference"
* by Nicolai M. Josuttis, Addison-Wesley, 1999
*
* (C) Copyright Nicolai M. Josuttis 1999.
* Permission to copy, use, modify, sell and distribute this software
* is granted provided this copyright notice appears in all copies.
* This software is provided "as is" without express or implied
* warranty, and with no claim as to its suitability for any purpose.
*/
  1. include <iostream>
  2. include <vector>
  3. include <deque>
  4. include <list>
  5. include <set>
  6. include <map>
  7. include <string>
  8. include <algorithm>
  9. include <iterator>
  10. include <functional>
  11. include <numeric>

/* PRINT_ELEMENTS()

* - prints optional C-string optcstr followed by
* - all elements of the collection coll
* - separated by spaces
*/

template <class T> inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="") {

   typename T::const_iterator pos;
   std::cout << optcstr;
   for (pos=coll.begin(); pos!=coll.end(); ++pos) {
       std::cout << *pos << " ";
   }
   std::cout << std::endl;

} /* INSERT_ELEMENTS (collection, first, last)

* - fill values from first to last into the collection
* - NOTE: NO half-open range
*/

template <class T> inline void INSERT_ELEMENTS (T& coll, int first, int last) {

   for (int i=first; i<=last; ++i) {
       coll.insert(coll.end(),i);
   }

} using namespace std; int main() {

   deque<int> coll;
   INSERT_ELEMENTS(coll,1,9);
   INSERT_ELEMENTS(coll,1,9);
   PRINT_ELEMENTS(coll,"on entry: ");
   // sorted reverse
   sort (coll.begin(), coll.end(),    // range
         greater<int>());             // sorting criterion
   PRINT_ELEMENTS(coll,"sorted >: ");

} /* on entry: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 sorted >: 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1

*/
       
   
 </source>


Sorting user-defined class

<source lang="cpp">

  1. include <algorithm>
  2. include <functional>
  3. include <iostream>
  4. include <vector>

using namespace std; class MyClass {

  public:
  MyClass( int num_points = 0 );
  bool operator<( const MyClass& rhs ) const;
  int num_points() const;
  void print() const;
  private:
  vector<float> data_;

}; inline MyClass::MyClass( int num_points ): data_( num_points ){} inline bool MyClass::operator<( const MyClass& rhs ) const {

  return num_points() < rhs.num_points(); 

} inline int MyClass::num_points() const {

  return static_cast<int>( data_.size() ); 

} inline void MyClass::print() const{

  cout << "\nThis experiment has " << num_points() << " data points";

} bool less_than_iterator( const vector<MyClass>::iterator i,const vector<MyClass>::iterator j ); // evaluate *i < *j int main( ) {

  vector<MyClass> v;
  int num_v = 3;
  v.reserve( num_v );
  v.push_back( MyClass( 3 ) );
  v.push_back( MyClass( 9 ) );
  v.push_back( MyClass( 5 ) );
  for_each( v.begin(), v.end(),mem_fun_ref( &MyClass::print ) );
  vector< vector<MyClass>::iterator > iterators( v.size() );
  vector< vector<MyClass>::iterator >::iterator j = iterators.begin();
  vector<MyClass>::iterator i = v.begin();
  vector<MyClass>::iterator v_end = v.end();
  while( i != v_end )
     *j++ = i++;
  sort( iterators.begin(), iterators.end(), less_than_iterator );
  vector< vector<MyClass>::iterator >::iterator iterators_end = iterators.end();
  for( j = iterators.begin(); j != iterators_end; ++j )
     (*j)->print();
  for_each( v.begin(), v.end(), mem_fun_ref( &MyClass::print ) );

} bool less_than_iterator( const vector<MyClass>::iterator i,const vector<MyClass>::iterator j ) {

  return *i < *j;   

}


 </source>


Sort into descending order by using greater

<source lang="cpp">

  1. include <cstdlib>
  2. include <iostream>
  3. include <vector>
  4. include <functional>
  5. include <algorithm>

using namespace std; void show(const char *msg, vector<int> vect); int main() {

 vector<int> v(10);
 for(unsigned i=0; i < v.size(); i++)
   v[i] = rand() % 100;
 show("Original order:", v);
 sort(v.begin(), v.end(), greater<int>());
 show("Order after sorting into descending order:", v);
 return 0;

} void show(const char *msg, vector<int> vect) {

 cout << msg << endl;
 for(unsigned i=0; i < vect.size(); ++i)
   cout << vect[i] << endl;

}


 </source>


Sort part of the elements in an array

<source lang="cpp">

/* The following code example is taken from the book

* "The C++ Standard Library - A Tutorial and Reference"
* by Nicolai M. Josuttis, Addison-Wesley, 1999
*
* (C) Copyright Nicolai M. Josuttis 1999.
* Permission to copy, use, modify, sell and distribute this software
* is granted provided this copyright notice appears in all copies.
* This software is provided "as is" without express or implied
* warranty, and with no claim as to its suitability for any purpose.
*/
  1. include <iostream>
  2. include <algorithm>
  3. include <functional>
  4. include <iterator>

using namespace std; int main() {

   int coll[] = { 5, 6, 2, 4, 1, 3 };
   // sort beginning with the second element
   sort (coll+3, coll+6);
   // print all elements
   copy (coll, coll+6,ostream_iterator<int>(cout," "));
   cout << endl;

}

/* 

5 6 2 1 3 4

*/       
   
 </source>


Sort random number

<source lang="cpp">

  1. include <iostream>
  2. include <algorithm>

using namespace std; const int N = 5; int main() {

  int    d[N], i, *e = d + N;
  for (i = 0; i < N; ++i){
     d[i] = rand();
  }   
  sort(d, e);
  for (i = 0; i < N; ++i){
     cout << d[i];
  }   

}


 </source>


Sort the entire container

<source lang="cpp">

  1. include <cstdlib>
  2. include <iostream>
  3. include <vector>
  4. include <functional>
  5. include <algorithm>

using namespace std; void show(const char *msg, vector<int> vect); int main() {

 vector<int> v(10);
 for(unsigned i=0; i < v.size(); i++)
   v[i] = rand() % 100;
 show("Original order:", v);
 sort(v.begin(), v.end());
 show("Order after sorting into natural order:", v);
 return 0;

} void show(const char *msg, vector<int> vect) {

 cout << msg << endl;
 for(unsigned i=0; i < vect.size(); ++i)
   cout << vect[i] << endl;

}


 </source>


Use custom function and sort to sort strings by length

<source lang="cpp">

/* The following code example is taken from the book

* "The C++ Standard Library - A Tutorial and Reference"
* by Nicolai M. Josuttis, Addison-Wesley, 1999
*
* (C) Copyright Nicolai M. Josuttis 1999.
* Permission to copy, use, modify, sell and distribute this software
* is granted provided this copyright notice appears in all copies.
* This software is provided "as is" without express or implied
* warranty, and with no claim as to its suitability for any purpose.
*/
  1. include <iostream>
  2. include <vector>
  3. include <deque>
  4. include <list>
  5. include <set>
  6. include <map>
  7. include <string>
  8. include <algorithm>
  9. include <iterator>
  10. include <functional>
  11. include <numeric>

/* PRINT_ELEMENTS()

* - prints optional C-string optcstr followed by
* - all elements of the collection coll
* - separated by spaces
*/

template <class T> inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="") {

   typename T::const_iterator pos;
   std::cout << optcstr;
   for (pos=coll.begin(); pos!=coll.end(); ++pos) {
       std::cout << *pos << " ";
   }
   std::cout << std::endl;

} /* INSERT_ELEMENTS (collection, first, last)

* - fill values from first to last into the collection
* - NOTE: NO half-open range
*/

template <class T> inline void INSERT_ELEMENTS (T& coll, int first, int last) {

   for (int i=first; i<=last; ++i) {
       coll.insert(coll.end(),i);
   }

} using namespace std; bool lessLength (const string& s1, const string& s2) {

   return s1.length() < s2.length();

} int main() {

   vector<string> coll1;
   vector<string> coll2;
   // fill both collections with the same elements
   coll1.push_back ("1xxx");
   coll1.push_back ("2x");
   coll1.push_back ("3x");
   coll1.push_back ("4x");
   coll1.push_back ("5xx");
   coll1.push_back ("6xxxx");
   coll1.push_back ("7xx");
   coll1.push_back ("8xxx");
   coll1.push_back ("9xx");
   coll1.push_back ("10xxx");
   coll1.push_back ("11");
   coll1.push_back ("12");
   coll1.push_back ("13");
   coll1.push_back ("14xx");
   coll1.push_back ("15");
   coll1.push_back ("16");
   coll1.push_back ("17");
   coll2 = coll1;
   PRINT_ELEMENTS(coll1,"on entry:\n ");
   // sort (according to the length of the strings)
   sort (coll1.begin(), coll1.end(),           // range
         lessLength);                          // criterion
   stable_sort (coll2.begin(), coll2.end(),    // range
                lessLength);                   // criterion
   PRINT_ELEMENTS(coll1,"\nwith sort():\n ");
   PRINT_ELEMENTS(coll2,"\nwith stable_sort():\n ");

}

/* 

on entry:

1xxx 2x 3x 4x 5xx 6xxxx 7xx 8xxx 9xx 10xxx 11 12 13 14xx 15 16 17

with sort():

17 2x 3x 4x 16 15 13 12 11 9xx 7xx 5xx 8xxx 14xx 1xxx 10xxx 6xxxx

with stable_sort():

2x 3x 4x 11 12 13 15 16 17 5xx 7xx 9xx 1xxx 8xxx 14xx 6xxxx 10xxx
*/       
   
 </source>


Using an in-place generic sort algorithm

<source lang="cpp">

  1. include <iostream>
  2. include <algorithm>
  3. include <cassert>

using namespace std; int main() {

 int a[1000];
 int i;
 
 for (i = 0; i < 1000; ++i) 
   a[i] = 1000 - i - 1;
 sort(&a[0], &a[1000]);
 for (i = 0; i < 1000; ++i) 
   assert (a[i] == i);
 
 return 0;

}


 </source>


Using the generic sort algorithm with a binary predicate: greater

<source lang="cpp">

  1. include <iostream>
  2. include <algorithm>
  3. include <cassert>
  4. include <functional>

using namespace std; int main() {

 int a[100];
 int i;
 for (i = 0; i < 100; ++i)
   a[i] = i;
 random_shuffle(&a[0], &a[100]);
 for (i = 0; i < 100; ++i)
   cout <<  a[i] << " ";
 cout <<"\n\n\n\n";
 // Sort into descending order:
 sort(&a[0], &a[100], greater<int>());
 for (i = 0; i < 100; ++i)
   cout <<  a[i] << " ";
 return 0;

} /* 12 1 9 98 96 27 58 82 86 90 18 62 32 40 71 51 91 41 94 17 8 47 64 66 65 7 6 76 5

99 77 81 54 35 56 39 25 3 87 16 61 68 14 13 24 55 97 19 20 59 75 33 21 28 78 15
50 34 36 44 83 38 46 60 84 95 57 22 37 23 70 89 31 79 73 92 11 2 88 42 30 52 72
53 67 29 85 43 74 69 45 26 93 10 48 80 0 63 49 4

99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73

72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 4

6 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 "

*/        
   
 </source>