Cod sursa(job #2172278)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 15 martie 2018 15:54:36
Problema Sortare prin comparare Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

int v[500005], n;

int pivot(int st, int dr)
{
    int l = st, r = dr, x, piv = st+rand()%(dr-st+1);
    //swap(v[l], v[piv]);
    x = v[l];
    while(l < r){
        while(l < r && v[r] >= x)
            --r;
        v[l] = v[r];
        while(l < r && v[l] <= x)
            ++l;
        v[r] = v[l];
    }
    v[l] = x;
    return l;
}

void quick(int st, int dr)
{
    int p = pivot(st, dr);
    if(p-1 > st)
        quick(st, p-1);
    if(p+1 < dr)
        quick(p+1, dr);
}

int main()
{
    ifstream fin ("algsort.in");
    ofstream fout ("algsort.out");
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    srand(time(NULL));
    quick(1, n);
    for (int i = 1; i <= n; ++i)
        fout << v[i] << " ";
    return 0;
}