Pagini recente » Cod sursa (job #1009698) | Cod sursa (job #1909412) | Cod sursa (job #1340119)
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#define MAX 500000
using namespace std;
int v[MAX];
void qsort(int b, int e)
{
int aux;
if (e - b > 4) {
int piv = v[(b + e) / 2];
int l = b - 1, r = e;
while (l < r) {
while (v[++l] < piv);
while (v[--r] > piv);
aux = v[l];
v[l] = v[r];
v[r] = aux;
}
aux = v[l];
v[l] = v[r];
v[r] = aux;
qsort(b, l);
qsort(l, e);
} else if (e - b == 4) {
int b1 = b + 1, b2 = b + 2, b3 = b + 3;
if (v[b1] < v[b]) {
aux = v[b1];
v[b1] = v[b];
v[b] = aux;
}
if (v[b2] < v[b]) {
aux = v[b2];
v[b2] = v[b];
v[b] = aux;
}
if (v[b3] < v[b]) {
aux = v[b3];
v[b3] = v[b];
v[b] = aux;
}
if (v[b2] < v[b1]) {
aux = v[b2];
v[b2] = v[b1];
v[b1] = aux;
}
if (v[b3] < v[b1]) {
aux = v[b3];
v[b3] = v[b1];
v[b1] = aux;
}
if (v[b3] < v[b2]) {
aux = v[b3];
v[b3] = v[b2];
v[b2] = aux;
}
} else if (e - b == 3) {
int b1 = b + 1, b2 = b + 2;
if (v[b1] < v[b]) {
aux = v[b1];
v[b1] = v[b];
v[b] = aux;
}
if (v[b2] < v[b]) {
aux = v[b2];
v[b2] = v[b];
v[b] = aux;
}
if (v[b2] < v[b1]) {
aux = v[b2];
v[b2] = v[b1];
v[b1] = aux;
}
} else if (e - b == 2) {
if (v[b + 1] < v[b]) {
aux = v[b + 1];
v[b + 1] = v[b];
v[b] = aux;
}
}
}
#define BUF_SIZE 4096
char buf[BUF_SIZE];
int pos = BUF_SIZE;
inline char getChar(FILE *f) {
if (pos == BUF_SIZE) {
fread(buf, 1, BUF_SIZE, f);
pos = 0;
}
return buf[pos++];
}
inline int readInt(FILE *f) {
int result = 0;
char c;
do {
c = getChar(f);
} while (!isdigit(c));
do {
result = 10 * result + c - '0';
c = getChar(f);
} while (isdigit(c));
return result;
}
int main()
{
freopen("algsort.in", "r", stdin);
freopen("algsort.out", "w", stdout);
int N;
scanf("%d", &N);
int i;
for (i = 0; i < N; i++) {
v[i] = readInt(stdin);
}
qsort(0, N);
//sort(v, v + N);
for (i = 0; i < N; i++) {
printf("%d ", v[i]);
}
}