C++ Tutorial/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;

}</source> 

1 2 3 4 5 6

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 << " ";
   }

}</source> 

1 2 3 4 5 6

Sort a vector into ascending order of id members

<source lang="cpp">#include <iostream>

  1. include <cassert>
  2. include <vector>
  3. include <algorithm>
  4. 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;

}</source> 

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 "

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:   ");

}</source> 

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

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 >: ");

}</source> 

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

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;

}</source> 

5 6 2 1 3 4

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 ");

}</source> 

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

Using an in-place generic sort algorithm

<source lang="cpp">#include <iostream>

  1. include <algorithm>
  2. 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">#include <iostream>

  1. include <algorithm>
  2. include <cassert>
  3. 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;

}</source> 

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
Источник — «http://cppe.ru/index.php?title=C%2B%2B_Tutorial/STL_Algorithms_Sorting/sort&oldid=2734»