14-12-2010, 00:25
|
|
|
|
חבר מתאריך: 07.12.09
הודעות: 7,072
|
|
קוד PHP:
#define length(a) 21
static int c[21];
static int heapsize = 21;
static int countCopy = 0;
static int countComp = 0;
int parent();
int child();
void heapify();
void buildheap();
void heapsort();
int maxextract();
void printArray();
int main();
int parent(int i,int d){
return (i-1)/d+((i-1)%d ==0 ? 0 :1);
}
int child(int i, int j,int d){
return (d*(i-1)+j-1);
}
void heapify(int i,int d){
if (i>20)
return;
printf("%d\n",i);
int largest = i;
countCopy++;
int j,l,temp;
for(j=1;j<=d;j++){
l = child(i,j,d);
countCopy++;
countComp +=2;
if(l<20&& c[l]>c[largest]){
largest = l;
countCopy++;
}
printf("%d\n",largest);
}
countComp++;
if(largest !=i){
temp = c[i];
c[i]= c[largest];
c[largest] = temp;
countComp+=3;
}
printf("3\n");
heapify(largest,d);
}
void buildheap(int d){
int i;
for(i = (19)/d + ((19%d) == 0 ? 0 : 1);i >= 1;i--){
countCopy++;
countComp++;
heapify(i,d);
}
}
void heapsort(int d){
buildheap(d);
int i;
int sorted[21];
for(i=1;i<=heapsize; i++){
countCopy++;
countComp++;
sorted[21-i]= maxextract(d);
countCopy++;
}
printArray(sorted);
}
int maxextract(int d){
if(heapsize<1)
puts("error");
int max = c[1];
c[1] = c[heapsize];
heapsize--;
countCopy += 3;
heapify(1,d);
return max;
}
void printArray(int b[]){
int i;
for(i=1;i<=20;i++)
printf("%d " ,b[i]);
puts("\n");
}
int main(void){
int i,j,d;
for(d = 2; d <= 5; d++)
for(i=0;i<10;i++){
for(j=1;j<21;j++){
c[j] = rand()%11;
}
printArray(c);
printf("d= %d number of i is %d number of j is %d number of copy is %d \n",d, i, j-1,countCopy);
heapsort(d);
}
}
אין לי כוח לעבור על זה...
אבל אלוהי כל הבאלגן....
נערך לאחרונה ע"י hellfrost בתאריך 14-12-2010 בשעה 00:29.
|