Using Insertion sort Generate 100000 positive numbers between (0,150) Search the

Question

Using Insertion sort

Generate 100000 positive numbers between (0,150)

Search the position of the first “58” in the array

Count how many “58” in the array

Sort the array

Repeat step 3 on the sorted array and compute the time cost difference between the time from step 3 only, and time from step 4 and 5 together.

Run your program three times and calculate the time:

The time to generate 100000#

The time to search the element 58 (step 2)

The time to count the 58’s (step 3)

The time to sort the array (step 4)

Step 5 ( difference of 4 5 and step 3)

A good programming and documentation are about 60-70% of the grade.

A clear report will cost another 30%.

The final report includes the introduction, problem description, theoretical solution, simulation results and conclusion. You can use any skills to prepare the documentation such as the flowchart.

Steps 1, 2 and 3 should be finished before step 4.

Explanation / Answer

#include <stdio.h>
#include <time.h>
int main(){
  
int n, array[100000], c, d, t;
int randnum, max_number, minimum_number;
max_number = 150;
minimum_number = 0;
  
n = 100000;
  
clock_t start1, end1;
clock_t start2, end2;
clock_t start3, end3;
clock_t start, end;
double total_time1, total_time2, total_time3,total_time;
  
//part 1
start1 = clock();
srand(time(NULL));
printf("Enter %d integers ", n);
for (c = 0; c < n; c++) {
randnum = rand() % (max_number + 1 - minimum_number) + minimum_number;
array[c] = randnum;
}
end1 = clock();
total_time1 = ((double) (end1 - start1)) / 60;
printf("Time taken to generate %d random numbers is %.2f ",n,total_time1);
  
//sorting
start = clock();
srand(time(NULL));
for (c = 1 ; c <= n - 1; c++) {
d = c;
while ( d > 0 && array[d] < array[d-1]) {
t = array[d];
array[d] = array[d-1];
array[d-1] = t;
d--;
}
}
end = clock();
total_time = ((double) (end - start)) / 60;
printf("Time taken to sort the array is %.2f ",total_time);
  
//part 2
start2 = clock();
srand(time(NULL));
int searched,i,index;
searched = 58;
index = 0;
for(i=0;i<n;i++){
if(searched == array[i]){
index = i;
}
}
if(index != 0){
printf("The first 58 is found at %d ",index);
}else{
printf("58 is not found ");
}
end2 = clock();
total_time2 = ((double) (end2 - start2)) / 60;
printf("Time taken to search for 58 is %.2f ",n,total_time2);
  
  
//part 3
start3 = clock();
srand(time(NULL));
int count;
count = 0;
searched = 58;
  
for(i=0;i<n;i++){
if(searched == array[i]){
count++;
}
}
if(count != 0){
printf("There are total %d 58 ",count);
}else{
printf("58 is not found ");
}
end3 = clock();
total_time3 = ((double) (end3 - start3)) / 60;
printf("Time taken to count all 58 is %.2f ",n,total_time3);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.