Brute force: #include <stdio.h> #include <string.h> #define MAX 100 /* try to fi

Question

Brute force:

#include <stdio.h>
#include <string.h>
#define MAX 100

/* try to find the given pattern in the search string */
int bruteForce(char *search, char *pattern, int slen, int plen) {
int i, j, k;

for (i = 0; i <= slen - plen; i++) {
for (j = 0, k = i; (search[k] == pattern[j]) &&
(j < plen); j++, k++);
if (j == plen)
return j;
}
return -1;
}

int main() {
char searchStr[MAX], pattern[MAX];
int res;
printf("Enter Search String:");
fgets(searchStr, MAX, stdin);
printf("Enter Pattern String:");
fgets(pattern, MAX, stdin);
searchStr[strlen(searchStr) - 1] = '';
pattern[strlen(pattern) - 1] = '';
res = bruteForce(searchStr, pattern, strlen(searchStr), strlen(pattern));
if (res == -1) {
printf("Search pattern is not available ");
} else {
printf("Search pattern available at the location %d ", res);
}
return 0;
}

Merge sort:

1. /*

* C Program to Find the Sum of Contiguous Subarray within a 1 - D Array of N

umbers which has the Largest Sum

*/

4.#include <stdio.h>
5.#include <stdlib.h>
6.
7.int maxSubArraySum(int a[], int size, int *begin, int *end) 8.{

int max_so_far = 0, max_end = 0;

int i, current_index = 0;

11.

for(i=0;i<size;i++)

{

max_end = max_end + a[i];

if (max_end <= 0)

{

max_end = 0;

current_index = i + 1;

}

else if (max_so_far < max_end)

{

max_so_far = max_end;

*begin = current_index;

*end = i;

}

}

return max_so_far;

28. }
29.
30.int main() 31. {

int arr[] = {10, -2, 15, 9, -8, 12, 20, -5};

intstart=0,end=0;

int size = sizeof(arr) / sizeof(arr[0]);

35.

printf(" The max sum is %d", maxSubArraySum(arr, size, &start, &end));

printf(" The begin and End are %d & %d", start, end);

getchar();

return 0;

40. }

How can I implement a timing function to see which one takes longer to sort?

(Program for the maximum subarray problem in C) Objective: Compare execution times of the brute force and the divide-and-conquer algorithms when solving the maximum subarray problem for arrays of different sizes. The arrays to be analyzed shall be the same for each algorithm, in order to make a valid comparison. Assignment: 1. Generate a C program that implement the brute force and the divide-and-conquer algorithms. 2. n your program, include a provision to generate arrays of varying sizes. Populate the arrays with integers, using a random number generator function (a library function is fine). Make a copy of this input array so that the same values will be used in both algorithms. 3. Use a timing function to measure the execution time for each algorithm used to analyze the input arrays. 4. Test your algorithms using arrays of size: 10, 100, and 1000 elements. Record the execution times and summarize the execution times in a table, ensuring that you provide time units for the execution times, i.e. seconds, milliseconds, clock cycles, etc. 5. Generate a short summary of your experimental observations and based on your results provide a commentary on when you would use each algorithm. (You may want to conduct more experiments to refine your recommendation.)

Explanation / Answer

SOLUTION:

Just create a function to calculate the running time, within the program and call the required sorting functions within it. Function is given below.

int executionTime()
{

float time1=0,time2=0;
clock_t b1,e1,e2,b2;

int res;

//here b1 is taken as current time before calling the brute force function
           b1 = clock();
          
           //calling bruteForce function
       res = bruteForce(searchStr, pattern, strlen(searchStr), strlen(pattern));
      

//e1 is taken as final time after the brute force function gets executed
       e1 = clock();
      

//now calculating the time take by bruteforce function
            time1=(float)(e1-b1)/CLOCKS_PER_SEC;
  
//storing intial time in b2 before calling maxSubArray() function
   b2=clock();
  
   //calling maxsubarray function
   maxSubArraySum(arr, size, &start, &end);
  

//Storing final time in e2.
   e2=clock();
  

//calculating required time taken to execute the MaxSubArray() function
   time2 = (float)(e2-b2)/CLOCKS_PER_SEC;
return 0;
}

I have supposed that all the sorting functions are within a single .c / .cpp file.

NOTE- Dont forget to include header file #include<bits/stdc++.h>

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

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