Pagini recente » Cod sursa (job #2674071) | Cod sursa (job #2212242) | Cod sursa (job #168422) | Cod sursa (job #940083) | Cod sursa (job #1092453)
#include <fstream>
using namespace std;
const int N = 5e5;
const int Size = 8, Mask = (1 << Size) - 1;
int v[N], pos[1 + Mask], n;
ifstream in("algsort.in");
ofstream out("algsort.out");
void selSort(int st, int dr){
for (int i = st ; i < dr ; i++)
for (int j = i + 1 ; j <= dr ; j++)
if (v[i] > v[j])
swap(v[i], v[j]);
}
int median(int st, int dr){
int p, i;
while (st != dr){
for (i = st, p = st ; p + 5 <= dr ; p += 5, i++){
selSort(p, p + 4);
swap(v[i], v[p + 2]);
}
if (p != dr){
selSort(p, dr);
swap(v[i], v[(p + dr) >> 1]);
} else
i--;
dr = i;
}
return v[st];
}
void qsort(int st, int dr){
if (dr - st <= 20)
return selSort(st, dr);
// if (dr <= st) return;
int i = st, j = dr, p = median(st, dr);
for (int k = i + 1 ; k <= j ; ){
if (v[k] < p)
swap(v[k], v[i++]);
if (p < v[k])
swap(v[k], v[j--]);
if (p == v[k])
k++;
}
qsort(st, i - 1);
qsort(j + 1, dr);
}
int main(){
in >> n;
for (int i = 0 ; i < n ; i++)
in >> v[i];
qsort(0, n - 1);
for (int i = 0 ; i < n ; i++)
out << v[i] << " ";
out << "\n";
return 0;
}