#include <iostream>
#include <vector>
using namespace std;
template <class T>
vector<T> sort(vector<T> input) {
if (input.size() < 2)
return input;
// definiujemy przedział
auto first = input.begin();
auto last = input.end()-1;
// tak długo jak przedział jest prawidłowy (co najmniej dwa elementy)
while (first < last) {
if (*first > *last)
std::swap(*first, *last);
for (auto iter = first; iter<=last; iter++) {
if (*iter < *first) // najmniejszy element idzie na początek przedziału
std::swap(*iter, *first);
else if (*iter > *last) // największy element idzi na koniec przedziału
std::swap(*iter, *last);
}
// zmniejszamy przedział
++first;
--last;
}
return input;
}
int main()
{
vector<int> array = { 3, 8, 2, 9, 6, 5, 4, 12};
array = sort<int>(array);
for (vector<int>::iterator m = array.begin(); m != array.end(); ++m) cout << " " << *m;
return 0;
}
