*PLEASE HELP* (in language C) Compare the execution time for different sorting a
ID: 3814163 • Letter: #
Question
*PLEASE HELP* (in language C)
Compare the execution time for different sorting algorithms.You need to implement one kind of sorting algorithm and compare its execution time with that of the qsort function in header file stdlib.h
Both of these two sorting algorithms will do sort on arrays which contain x randomly generated integers where the value of x could be 10000, 20000, 40000 and 80000
The whole process of the program is as follows:
a. Set x = 10000, randomly generate x integers. Call qsort function to sort these
integers and get the execution time.
b. Randomly generate another x integers. Call your own sorting algorithm and get
the execution time.
c. Print the above two execution time on the screen. Program terminates if x =
80000, otherwise set x = x * 2.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
HINTS
1. Dynamic memory allocation and deallocation is suggested but not required. You need to check carefully to make sure your own sorting algorithm works fine.
2. The rand() function in header file stdlib.h could be used to generate a random integer.
The sample codes for using the qsort function and measuring the program execution time are listed in three3.c
3. You may implement selection sort, bubble sort or any other existing sorting algorithm for comparison. You do not need to propose a new kind of sorting algorithm. It is totally fine if your own sorting algorithm is slower than qsort.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
SAMPLE OUTPUT
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Three3.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int cmp(const void* p,const void* q)
{
int *p1,*q1;
p1=(int*)p;
q1=(int*)q;
return *p1>*q1;
}
int main()
{
int i,a[]={3,1,2,4,5};
clock_t t1,t2;
qsort(a,5,sizeof(int),cmp);
for(i=0;i<5;i++)
printf("%d ",a[i]);
t1=clock();
for(i=0;i<100000000;i++)
{
}
t2=clock();
printf(" execution time:%fs",(t2-t1)/((float)CLOCKS_PER_SEC));
return 0;
}
Explanation / Answer
#include<stdio.h>
int *array1, *array2;
void createArray(int m){
int i;
array1 = (int*)malloc(sizeof(int)*m);
array2 = (int*)malloc(sizeof(int)*m);
for (i=0; i<m; i++)
array2[i] = array1[i] = rand();
}
int cmp(const void* a, const void* b){
int* x =(int*)a;
int* y =(int*)b;
return *x - *y;
}
void sort(int *ar, int m) {
int i, j ,temp;
for (i = 0; i < m - 1 ;i++)
for (j = 0; j<m-i-1; j++)
if(ar[j] > ar[j+1]) {
temp = ar[j];
ar[j] = ar[j+1];
ar[j+1] = temp;
}
}
void main() {
int m;
long t1,t2;
printf("size qsort mysort ");
for(m=10000; m<=80000; m = m*2) {
createArray(m);
t1 = clock();
qsort(array1,m,sizeof(int),cmp);
t1 = clock() - t1;
t2 = clock();
sort(array2,m);
t2 = clock() - t2;
printf("%d %ld %ld ",m,t1,t2);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.