
/**//**
* QUICKSORT : sort
* void sort(iterator beg, iterator end);
* void sort(iterator beg, iterator end, compare cmp); <algorithm>
*/
#include <iostream>
#include <iterator>
#include <algorithm>
#include <numeric>
using namespace std;
int Partition(int *a, int lhs, int rhs)

{
int key = a[rhs];
int i = lhs - 1;
for (int j = lhs; j < rhs; ++j)
if (a[j] <= key) swap(a[++i], a[j]);
swap(a[++i], a[rhs]);
return i;
}
void QuickSort(int *a, int lhs, int rhs)

{
if (lhs < rhs)
{
int mid = Partition(a, lhs, rhs);
QuickSort(a, lhs, mid - 1);
QuickSort(a, mid + 1, rhs);
}
}
int main()

{
int a[100];
for (int i = 0; i < 100; ++i) a[i] = i;
random_shuffle(a, a + 100);
copy(a, a + 100, ostream_iterator<int>(cout, " ")); cout << endl << endl;
QuickSort(a, 0, 99);
copy(a, a + 100, ostream_iterator<int>(cout, " ")); cout << endl;
system("pause");
return 0;
}


