На этом шаге мы рассмотрим алгоритмы, осуществляющие частичную сортировку с копированием.

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

  RandomAccessIterator
  partial_sort_copy (InputIterator sourceBeg, InputIterator sourceEnd,
                     RandomAccessIterator destBeg,
                     RandomAccessIterator destEnd)

  RandomAccessIterator
  partial_sort_copy (InputIterator sourceBeg, InputIterator sourceEnd,
                     RandomAccessIterator destBeg,
                     RandomAccessIterator destEnd,
                     BinaryPredicate op)

Обе формы являются объединениями алгоритмов сору() и partial_sort().

Обе формы копируют элементы из интервала [sourceBeg,sourceEnd) в приемный интервал [destBeg,destEnd).

Количество упорядоченных и скопированных элементов равно минимальному количеству элементов в исходном и приемном интервалах.

Обе формы возвращают позицию за последним скопированным элементом в приемном интервале (то есть позицию первого элемента, который не был скопирован).

Если количество элементов в приемном интервале [destBeg,destEnd) больше либо равно количеству элементов в источнике [sourceBeg,sourceEnd), то алгоритм копирует и сортирует все элементы источника. В этом случае он работает как комбинация алгоритмов сору() и sort().

Сложность от линейной до n*log(n) (примерно numberOfElements*log(numberOfSortedElements) сравнений).

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

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

#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> coll1;
  vector<int> coll6(6);      // Инициализация 6 элементами
  vector<int> coll30(30);    // Инициализация 30 элементами

  INSERT_ELEMENTS(coll1,3,7);
  INSERT_ELEMENTS(coll1,2,6);
  INSERT_ELEMENTS(coll1,1,5);
  PRINT_ELEMENTS(coll1,"Исходная коллекция:\n");

  // Копирование упорядоченных элементов coll1 в coll6
  vector<int>::iterator pos6;
  pos6 = partial_sort_copy (coll1.begin(), coll1.end(),
                            coll6.begin(), coll6.end());

  // Вывод всех скопированных элементов
  cout << ToRus("Вывод всех скопированных элементов:\n");
  copy (coll6.begin(), pos6,
        ostream_iterator<int>(cout," "));
  cout << endl;

  // Копирование упорядоченных элементов coll1 в coll30
  vector<int>::iterator pos30;
  pos30 = partial_sort_copy (coll1.begin(), coll1.end(),
                             coll30.begin(), coll30.end(),
                             greater<int>());

  // Вывод всех скопированных элементов
  cout << ToRus("Вывод всех скопированных упорядоченных элементов:\n");
  copy (coll30.begin(), pos30,
        ostream_iterator<int>(cout," "));
  cout << endl;


  getch();
  return 0;
}

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

Текст этого примера можно взять здесь.

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

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

При первом вызове partial_sort_copy() приемник содержит только шесть элементов, поэтому алгоритм ограничивается копированием шести элементов и возвращает конец coll6. При втором вызове partial_sort_copy() все элементы coll1 копируются в coll30; места для них достаточно, поэтому копирование и сортировка выполняются со всеми элементами.

На следующем шаге мы рассмотрим разбиение по n-му элементу.

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