change c program this is an array A of size 7 with the following values: 12, 10,
ID: 3683114 • Letter: C
Question
change c program
this is an array A of size 7 with the following values: 12, 10, 20, 19, 8, 7, 15. change to an array A of size 100 containing random integers between 1 and 500
#include<stdio.h>
void printArray(int *a,int size);
void Heapify(int *a,int i,int j);
/*note: j is the last index for an array, not size!!!*/
void BuildHeap(int a[],int size);
void HeapSort(int a[],int size);
void main()
{ int A[7]={12,10,20,19,8,7,15};
printf("Inital Array: ");
printArray(A,7); //output the initial array.
HeapSort(A,7);
printf("Array after call HeapSort: ");
printArray(A,7); //output the array.
}
void printArray(int *a,int size)
{int i;
for(i=0;i<size;i++)
printf("%d ",a[i]);
printf(" ");
}
void Heapify(int *a,int i,int j)
{ if(2*i+1<=j) // to determine if a[i] is a leaf
{ int max;
if(2*i+2<=j) //case1: a[i] has two children
{ if(a[2*i+1]>a[2*i+2]) // extract the index for the larger child to max.
max=2*i+1;
else
max=2*i+2;
}
else
max=2*i+1; //case2: a[i] has only one child
if(a[i]<a[max]) //if the leaf is smaller than its child,to exchange their postion.
{ int temp=a[i];
a[i]=a[max];
a[max]=temp;
Heapify(a,max,j);
}
}
}
void BuildHeap(int a[],int size)
{ int i;
for(i=size/2-1;i>=0;i--)
Heapify(a,i,size-1);
}
void HeapSort(int a[],int size)
{ BuildHeap(a,size);
int i,temp;
for(i=size-1;i>=1;i--)
{ temp=a[0]; //exchange a[0] and a[i]
a[0]=a[i];
a[i]=temp;
Heapify(a,0,i-1);
}
}
Explanation / Answer
#include<stdio.h>
#include <stdlib.h>
#include<time.h>
void printArray(int *a,int size);
void Heapify(int *a,int i,int j);
/*note: j is the last index for an array, not size!!!*/
void BuildHeap(int a[],int size);
void HeapSort(int a[],int size);
void main()
{
srand(time(NULL));
int A[100],i;
for (i=0;i<100;i++){
A[i] = (rand() % 500) +1;
}
printf("Initial Array: ");
printArray(A,100); //output the initial array.
HeapSort(A,100);
printf("Array after call HeapSort: ");
printArray(A,100); //output the array.
}
void printArray(int *a,int size)
{int i;
for(i=0;i<size;i++)
printf("%d ",a[i]);
printf(" ");
}
void Heapify(int *a,int i,int j)
{ if(2*i+1<=j) // to determine if a[i] is a leaf
{ int max;
if(2*i+2<=j) //case1: a[i] has two children
{ if(a[2*i+1]>a[2*i+2]) // extract the index for the larger child to max.
max=2*i+1;
else
max=2*i+2;
}
else
max=2*i+1; //case2: a[i] has only one child
if(a[i]<a[max]) //if the leaf is smaller than its child,to exchange their postion.
{ int temp=a[i];
a[i]=a[max];
a[max]=temp;
Heapify(a,max,j);
}
}
}
void BuildHeap(int a[],int size)
{ int i;
for(i=size/2-1;i>=0;i--)
Heapify(a,i,size-1);
}
void HeapSort(int a[],int size)
{ BuildHeap(a,size);
int i,temp;
for(i=size-1;i>=1;i--)
{ temp=a[0]; //exchange a[0] and a[i]
a[0]=a[i];
a[i]=temp;
Heapify(a,0,i-1);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.