#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
template <class BidirectionalIterator>
void duplex_selection_sort(BidirectionalIterator first, BidirectionalIterator last);
int main(int argc, char *argv[])
{
using namespace std;
vector<int> array0, array1, array2;
ostream_iterator<int> output(cout, " ");
for(int i = 1; i <= 10; i++)
{
array0.push_back(i);
array1.push_back(i);
array2.insert(array2.begin(), i);
}
random_shuffle(array0.begin(), array0.end());
cout << "before sort" << endl;
copy(array0.begin(), array0.end(), output);
cout << endl;
copy(array1.begin(), array1.end(), output);
cout << endl;
copy(array2.begin(), array2.end(), output);
cout << endl;
duplex_selection_sort(array0.begin(), array0.end());
duplex_selection_sort(array1.begin(), array1.end());
duplex_selection_sort(array2.begin(), array2.end());
cout << "\nafter sort" << endl;
copy(array0.begin(), array0.end(), output);
cout << endl;
copy(array1.begin(), array1.end(), output);
cout << endl;
copy(array2.begin(), array2.end(), output);
cout << endl;
return EXIT_SUCCESS;
}
template <class BidirectionalIterator>
void duplex_selection_sort(BidirectionalIterator first, BidirectionalIterator last) {
BidirectionalIterator min, max;
while(last > first) {
min = max = first;
for(BidirectionalIterator i = first; i != last; i++) {
if(*min > *i)
min = i;
if(*max < *i)
max = i;
}
if(last - 1 != min)
std::iter_swap(max, last - 1);
std::iter_swap(min, first);
first++;
last--;
}
}