Cod sursa(job #3172787)

Utilizator eu_stiu_infoFerseta Matei eu_stiu_info Data 21 noiembrie 2023 11:10:09
Problema Sortare prin comparare Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
///Quicksort
#include <fstream>
#include <algorithm>
#include <time.h>
#include <stdlib.h>

using namespace std;

void qsort(int v[], int begin, int end)
{
    int pivot = v[begin+rand() % (end-begin+1)];
    int b=begin,e=end;
    while (v[b]<pivot)
        b++;
    while (v[e]>pivot)
        e--;
    while (b<e)
    {
        swap(v[b],v[e]);
        do
            b++;
        while (v[b]<pivot);

        do
            e--;
        while (v[e]>pivot);
    }
    if (begin<e)
        qsort(v,begin,e);
    if (e+1<end)
        qsort(v,e+1,end);
}

int n,v[500001];

ifstream fin("algsort.in");
ofstream fout ("algsort.out");

int main()
{
    fin >> n;
    for (int i=1;i<=n;i++)
    {
        fin>>v[i];
    }
    qsort(v,0,n);
    for (int i=1;i<=n;i++)
    {
        fout<<v[i]<<' ';
    }
    return 0;
}