sort

Синтаксис:

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

Алгоритм sort() сортирует элементы диапазона [start,end) по возрастанию. Если элементы равны, нет гарантии сохранения исходного порядка.

Если нужна повышенная точность, вводится упорядочивающая функция-объект cmp, которая используется для сравнения двух объектов вместо оператора <.

Алгоритм сортировки sort() - алгоритм introsort (объединение quicksort и heapsort). sort() работает за время O(N log(N)) (в среднем и худшем случае). Это быстрее полиномиального времени, но медленнее линейного времени.

Обратите внимание, что sort() работает только с итераторами случайного доступа. Поэтому вы не можете использовать sort() для итераторов списков "list" (связанных списков). Для работы со списками нужно использовать собственный метод списка [[cpp/../list/sort | ../list/sort]] для сортировки.

Например, следующий код сортирует вектор по возрастанию:

   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;

Вывод:

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

Следующий код использует sort() для сортировки массива целых чисел и производит аналогичный предыдущему примеру вывод:

   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;

Следующий пример показывает, как использовать sort() с определенной пользователем функцией сравнения. Функция cmp определена для использования вместо оператора <. Когда sort() вызывается с использованием функции cmp для сравнения, результатом является список, отсортированный по убыванию:

   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;

Смотрите также: binary_search, merge, partial_sort, partial_sort_copy, stable_sort, c/other/qsort