На этом шаге мы рассмотрим использование алгоритма sort().

    STL поддерживает несколько алгоритмов, предназначенных для сортировки элементов в интервалах. Кроме полной сортировки существует несколько разновидностей частичной сортировки. Если их результат вас устроит, лучше использовать эти алгоритмы, потому что обычно они работают более эффективно. Ассоциативные контейнеры сортируют свои элементы автоматически. Однако обычно эффективнее однажды выполнить сортировку элементов, а не хранить их в упорядоченном виде постоянно.

Сортировка всех элементов

    Для выполнения сортировки можно использовать следующие алгоритмы:

  void
  sort (RandomAccessIterator beg, RandomAccessIterator end)

  void
  sort (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)

  void
  stable_sort (RandomAccessIterator beg, RandomAccessIterator end)

  void
  stable_sort (RandomAccessIterator beg, RandomAccessIterator end, 
               BinaryPredicate op)

    Первые формы sort() и stable_sort() сортируют все элементы интервала [beg,end) оператором <.

    Вторые формы sort() и stable_sort() сортируют все элементы интервала, используя в качестве критерия сортировки бинарный предикат op(elem1,elem2).

    Предикат ор не должен изменять свое состояние во время вызова.

    Отличие sort() от stable_sort() заключается в том, что stable_sort() сохраняет относительный порядок следования равных элементов.

    Алгоритмы не могут использоваться со списками, потому что списки не поддерживают итераторы произвольного доступа. Впрочем, для сортировки эле-ментов в списках определена специальная функция sort() (смотри 204 шаг).

    Алгоритм sort() гарантирует хорошее среднее быстродействие (n*log(n)). Тем не менее если в вашей ситуации особенно важно избежать худших случаев, используйте алгоритм partial_sort() или stable_sort(). Сравнительный анализ алгоритмов сортировки приводится на 260 шаге.

    Сложность:

• sort() - в среднем n*log(n) (примерно numberOfElements*log(numberOfElements) сравнений);
• stable_sort() - n*log(n) при наличии дополнительной памяти (numberOfElements*log(numberOfElements)), n*log(n)*log(n) в противном случае (numberOfElements*log(numberOfElements)² сравнений).

    Пример использования алгоритма sort():

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iterator>
#include "algostuff.hpp"

#include <conio.h> //необходимо для getch()

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;

std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

int main()
{
  deque<int> coll;

  INSERT_ELEMENTS(coll,1,9);
  INSERT_ELEMENTS(coll,1,9);

  PRINT_ELEMENTS(coll,"Исходная коллекция:\n");

  // Сортировка элементов
  sort (coll.begin(), coll.end());

  PRINT_ELEMENTS(coll,"Сортировка по возрастанию:\n");

  // Сортировка в обратном порядке
  sort (coll.begin(), coll.end(),    // Интервал
        greater<int>());             // Критерий сортировки

  PRINT_ELEMENTS(coll,"Сортировка по убыванию:\n");


  getch();
  return 0;
}

//---------------------------------------------------------------------------

    Результат выполнения программы выглядит так:

Рис.1. Результат работы приложения

    На следующем шаге мы продолжим изучение этого вопроса.

Предыдущий шаг Содержание Следующий шаг