Pagini recente » Cod sursa (job #759737) | Cod sursa (job #471282) | Cod sursa (job #1214239) | Cod sursa (job #1451214) | Cod sursa (job #373528)
Cod sursa(job #373528)
using namespace std;
#include <cstdio>
#define MAX 500010
int heap[MAX], n;
void read(){
freopen("algsort.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",heap+i);
}
void write(){
freopen("algsort.out","w",stdout);
for(int i=1;i<=n;++i)
printf("%d ",heap[i]);
}
void Cerne(int poz){
int esteHeap=0,k=poz,i,aux;
while(!esteHeap && (i=2*k)<=n){
if(i+1<=n && heap[i]<=heap[i+1])
i++;
if(heap[k]>=heap[i])
esteHeap=1;
else{
aux=heap[k]; heap[k] = heap[i]; heap[i] = aux;
k=i;
}
}
}
void Promoveaza(int poz){
int esteHeap=0, aux, i,k=poz;
while(!esteHeap && k/2>0){
i=k/2;
if(heap[i]>=heap[k])
esteHeap=1;
else{
aux=heap[i]; heap[i] = heap[k]; heap[k]=aux;
k=i;
}
}
}
void sort(){
for(int i=1;i<=n;i++)
Promoveaza(i);
int q=n;
for( ; n >1 ;){
int aux=heap[1]; heap[1] = heap[n]; heap[n]=aux;
n--;
Cerne(1);
}
n=q;
}
int main(){
read();
sort();
write();
return 0;
}