Cod sursa(job #561659)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 20 martie 2011 23:16:33
Problema Sortare prin comparare Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb

#include<cstdio>
#include<algorithm>
using namespace std;

int A[500001],N;

void read();
void quicksort(int ,int );
void write();

int main()
{
    freopen("algsort.in","r",stdin);
    freopen("algsort.out","w",stdout);

    read();
    quicksort(1,N);
    write();
    return 0;
}

void read()
{
    int i;
    scanf("%d",&N);
    for (i=1;i<=N;++i)
        scanf("%d",&A[i]);
}

void quicksort(int in ,int sf)
{
    int mij,q,i;
    if (in<sf)
        {

            mij=rand()%(sf-in+1)+in;
            swap(A[mij],A[sf]);
            q=in-1;
            for (i=in;i<sf;++i)
                if (A[i]<A[sf])
                    swap(A[i],A[++q]);

    swap(A[++q],A[sf]);
    quicksort(in,q-1);
    quicksort(q+1,sf);
     }
}

void write()
{
    int i;
    for (i=1;i<=N;++i)
        printf("%d ",A[i]);
}