# Cod sursa(job #2381569)

Utilizator Data 17 martie 2019 01:04:43 Sortare prin comparare 60 cpp-64 done Arhiva educationala 1.51 kb
``````#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

ifstream f("algsort.in");
ofstream g("algsort.out");

int choosePiv(vector<int> &v, int left, int right)
{
int a = left + rand() % (right - left + 1),
b = left + rand() % (right - left + 1),
c = left + rand() % (right - left + 1);

if (v[a] > v[b])
swap(v[a], v[b]);
if (v[a] > v[c])
swap(v[a], v[c]);
if (v[b] > v[c])
swap(v[b], v[c]);

return b;
}

int pivSwap(vector<int> &v, int left, int right)
{
if (left >= right)
return -1;

int pivPos = choosePiv(v, left, right);

swap(v[right], v[pivPos]);

int i = left, j = right - 1;
while (i <= j)
{
int pivVal = v[right];
if (v[i] > pivVal && v[j] < pivVal)
swap(v[i], v[j]);
else
{
if (v[i] <= pivVal)
++i;
if (v[j] >= pivVal)
--j;
}
}

// put pivot in its place
swap(v[i], v[right]);

return i;
}

void qsort(vector<int> &v, int left, int right)
{
srand(time(0));

int pivIndex = pivSwap(v, left, right);

if(pivIndex != -1)
qsort(v, left, pivIndex - 1),
qsort(v, pivIndex + 1, right);
}

int main()
{
int n, x;
vector<int> v;

f >> n;
while (n--)
f >> x,
v.push_back(x);

qsort(v, 0, v.size() - 1);

for (auto x : v)
g << x << ' ';

return 0;
}``````