hi at first and
ramadan kareem
guys i do this program for this statment
in the average case which algorithm performs faster --- an algorithm that takes time proportional to nlogn or an algorithm that takes time proporitionla to n^2 , for the same values of n? do a comparative analysis by taking real examples(programs) and run them in different size of input .
and then the details
you might have to modify the program to print the start and end times to calculate the total time taken for the running of the program to print the start time and end times to calculate the total time taken for the running of the program. you might also have to write a small function to generate random numbers to be used as input for the input use a numbers no more than 99999
and do not include the time taken for generating the numbers in ur analysis
and this is my try for the program
#include
#include
#include
void InsertionSort (double A[], int N)
{
int j, P;
double Tmp;
for (P=1; P
{
Tmp=A[P];
for (j=P; j>0 && A[j-1]>Tmp; j--)
A[j]=A[j-1];
A[j]=Tmp;
}
}
void QuickSort( double A[], int l, int r)
{ double pivot= A[r];
int i = l-1;
int j = r;
int temp;
if (r>l)
{
do
{
do i++; while (A
do j--; while (A[j]>pivot);
temp = A;
A = A[j];
A[j] = temp;
}
while (j>i);
A[j] = A;
A = pivot;
A[r] = temp;
QuickSort(A,l,i-1);
QuickSort(A,i+1,r);
}
}
main()
{
double a[5000], b[5000]; /*Change these lines for different size arrays*/
int i, arraysize=5000; /*Arraysize must equal sizes set for A and B*/
clock_t start,end;
double first, second;
randomize();
for (i=0; i
{
a=random(100); /*These three lines are necessary for random to 99999*/
a=a*1000;
a+=random(1000);
b=a; /*Copy unsorted array to use in other sort(control)*/
}
start=clock();
InsertionSort(a, arraysize);
end=clock();
first=(end-start)/(double)CLOCKS_PER_SEC;
start=clock();
QuickSort (b,0,arraysize-1);
end=clock();
second=(end-start)/(double)CLOCKS_PER_SEC;
for (i=0;i<100;i++)
printf ("%gt", a);
printf("nTime taken for Insertion Sort is %g n",first);
printf("Time taken for Quick Sort is %g n",second);
getch();
}
but the problem is that i can't make the u ser to input the numbers
and the second proplem is
the random values go upto 99999 only when the array is of size 100. When the array size increases, the max random value decreases. At size 10000 the max value is only about 10000. It should be 99 times bigger. I think this because of set memory allocation to the array. I could try using malloc( ) to allocate space for the values but I don't think it is of much use. The time of execution doesnt change, or only changes by a very small fraction.
and sorry for the long but plz tell me what is wrong with it