Pagini recente » Monitorul de evaluare | Cod sursa (job #302649)
Cod sursa(job #302649)
#include <stdio.h>
#include <stdlib.h>
#define NMAX 500001
int v[NMAX], N, i;
FILE *f, *g;
void read(void)
{
f = fopen("algsort.in", "r");
fscanf(f, "%d", &N);
for(register int i = 1; i <= N; i++)
fscanf(f, "%d", &v[i]);
fclose(f);
}
int cmp(const void *a, const void *b)
{
int *x = (int *)a;
int *y = (int *)b;
return *x - *y;
}
inline void swap(int &first, int &second)
{
int aux;
aux = first;
first = second;
second = aux;
}
void shell(void)
{
int sw, inj;
inj = N;
while(inj > 1)
{
inj /= 2;
do
{
sw = 1;
for( i = 1; i <= N-inj; ++i)
if(v[i] > v[i+inj])
swap(v[i], v[i+inj]), sw = 0;
}while(!sw);
}
}
void solve(void)
{
if(N < 300000)
shell();
else
qsort((void *)(v+1), N, sizeof(int), cmp);
}
void print(void)
{
g = fopen("algsort.out", "w");
for(register int i = 1; i <= N; i++)
fprintf(g, "%d ", v[i]);
fclose(g);
}
int main(void)
{
read();
solve();
print();
return 0;
}