Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
33.
Алгоритм stable_sort
Прототипы
template <typename RandomAccessIterator>
void stable_sort(RandomAccessIterator first,
RandomAccessIterator last);
template <typename RandomAccessIterator,typename Compare>
void stable_sort(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
Алгоритм stable_sort реализован при помощи версии сортировки слиянием. Алгоритм stable_sort сортирует элементы в диапазоне [first;last), гарантируя при этом относительного порядка эквивалентных элементов.
Время работы stable_sort равно O(NlogN) или O(N(logN)2), в зависимости от доступности дополнительной памяти для работы алгоритма. Если имеется дополнительная память для как минимум N/2 элементов, время работы равно O(NlogN).
Алгоритм merge
Прототипы
template <typename InputIterator1,typename InputIterator2,
typename OutputIterator>
OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template <typename InputIterator1,typename InputIterator2,
typename OutputIterator,typename Compare>
OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
Алгоритм merge сливает два отсортированных диапазона [first1;last1) и [first2;last2) в диапазон [result;result+N), где N=N1+N2, N1=last1-first1, а N2=last2-first2. Алгоритм устойчив, т.е. эквивалентные элементы из первого диапазона всегда предшествуют элементам из второго диапазона. Алгоритм merge возвращает result+N. Результат алгоритма merge не определен, если результирующий диапазон перекрывается с любым из исходных диапазонов.
Временная сложность линейная. В алгоритме выполняется не более N сравнений.
Алгоритм inplace_merge
Прототипы
template <typename BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template <typename BidirectionalIterator,typaname Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last,
Compare comp);
Алгоритм inplace_merge сливает два отсортированных последовательных диапазона [first;middle) и [middle;last), размещая результат в диапазоне [first;last). Слияние устойчиво.
Временная сложность зависит от доступной дополнительной памяти. Если имеется дополнительная память для N=last-first элементов, время работы составляет O(N), в противном случае оно равно O(NlogN). В алгоритме выполняется не более N сравнений.
Рассмотрим пример программы на использование алгоритмов stable_sort, merge, inplace_merge.
#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
#include<list>
using namespace std;
//функциональный класс
class comp{
public:
//критерий сравнения x и y
bool operator()(int x,int y)
{return x%5<y%5;}
};
int main()
{ const int n=10;
//создаем вектор целых чисел
//и заполняем его
vector<int> vec(n);
ostream_iterator<int> out(cout," ");
for(int i=0;i<n;++i)
vec[i]=i;
cout<<"vec:\n";
copy(vec.begin(),vec.end(),out);
cout<<endl<<endl;
//создаем дек целых чисел
// и заполняем его
deque<int> dec(2*n);
for(int i=0;i<2*n;++i)
dec[i]=2*i;
cout<<"dec:\n";
copy(dec.begin(),dec.end(),out);
cout<<endl<<endl;
//создаем список из 19 элементов
list<int> l1(19);
//с помощью алгоритма merge объединяем часть
//вектора с частью дека
// и помещение результата в список
merge(vec.begin(),vec.begin()+9,dec.begin()+3,dec.begin()+13,l1.begin());
cout<<"List:\n";
copy(l1.begin(),l1.end(),out);
cout<<endl<<endl;
vector<int> vec1(5),vec2(5),vec3(10);
for(int i=0;i<5;++i)
{ vec1[i]=2*i;
vec2[i]=1+2*i;
}
for(int i=0;i<5;++i)
{ vec3[i]=vec1[i];
vec3[i+5]=vec2[i];
}
cout<<"Vec3 before sort:\n";
copy(vec3.begin(),vec3.end(),out);
cout<<endl<<endl;
//Слияние двух отсортированных половин вектора vec3
//на месте, для получения
//отсортированного вектора vec3
//с помощью алгоритма inplace_merge
inplace_merge(vec3.begin(),vec3.begin()+5,vec3.end());
cout<<"Vec3 after sort:\n";
copy(vec3.begin(),vec3.end(),out);
cout<<endl<<endl;
//Сортировка с помощью алгоритма stable_sort
random_shuffle(vec3.begin(),vec3.end());
cout<<"Before sort:\n";
copy(vec3.begin(),vec3.end(),out);
cout<<endl<<endl;
//сортируем по возрастанию остатка от деления на 5
stable_sort(vec3.begin(),vec3.end(),comp());
cout<<"After sort:\n";
copy(vec3.begin(),vec3.end(),out);
cout<<endl<<endl;
}