May 11, 2023 Brute Force Techniques I
This is a description Sorts & Searches
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
void selectionSort(int arr[], int n)
{
int i, j, min;
for (i = 0; i < n - 1; i++)
{
min = i;
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[min])
min = j;
}
if (min != i)
swap(&arr[min], &arr[i]);
}
}
void bubbleSort(int arr[], int n)
{
int i, j, swapped;
for (i = 0; i < n - 1; i++)
{
swapped = 0;
for (j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
swap(&arr[j], &arr[j + 1]);
swapped = 1;
}
}
if (!swapped)
break;
}
}
void linearSearch(int arr[], int num, int item)
{
int i;
for (i = 0; i < num; i++)
if (arr[i] == item)
return;
return;
}
void binarySearch(int arr[], int num, int item)
{
int low = 0, high = num;
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] == item)
return;
if (arr[mid] < item)
low = mid + 1;
else
high = mid - 1;
}
return;
}
void main()
{
int num, item, choice = 0;
int i, j;
time_t t;
srand((unsigned)time(&t));
clock_t start, end;
double cpuTimeUsed;
while (1)
{
printf("\n\n--- ALL SORTS ---");
printf("\n1. Selection Sort");
printf("\n2. Bubble Sort");
printf("\n3. Exit.");
printf("\n\nEnter your choice: ");
scanf("%d", &choice);
if (choice < 0 || choice >= 3)
exit(0);
printf("\n\nEnter number of elements: ");
scanf("%d", &num);
int arr[num];
for (i = 0; i < num; i++)
arr[i] = rand() % 1000;
printf("\n\nList input received.");
if (choice == 1)
{
start = clock();
selectionSort(arr, num);
end = clock();
}
else if (choice == 2)
{
start = clock();
bubbleSort(arr, num);
end = clock();
}
cpuTimeUsed = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nSorting time: %f seconds", cpuTimeUsed);
printf("\nList sorted.");
item = rand() % 1000;
start = clock();
linearSearch(arr, num, item);
end = clock();
cpuTimeUsed = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nLinear time: %f seconds", cpuTimeUsed);
printf("\nLinear search complete.");
start = clock();
binarySearch(arr, num, item);
end = clock();
cpuTimeUsed = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nBinary time: %f seconds", cpuTimeUsed);
printf("\nBinary search complete.");
}
}
Factorial
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int factorial(int n)
{
static int opCount = 1;
if(n == 0 || n == 1)
{
printf("\nOperation Count: %d", opCount);
opCount = 1;
return 1;
}
opCount++;
return n * factorial(n-1);
}
void main()
{
int num, i;
printf("Enter number of iterations: ");
scanf("%d", &num);
for (i = 0; i < num; i++)
{
factorial((i + 1) * 10000);
printf("\nFactorial: %d", ((i + 1) * 10000));
}
}
Enter number of iterations: 5
Operation Count: 10000
Factorial: 10000
Operation Count: 20000
Factorial: 20000
Operation Count: 30000
Factorial: 30000
Operation Count: 40000
Factorial: 40000
Operation Count: 50000
Factorial: 50000
String Pattern Matching
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
void patternSearch(char *string, char *pattern)
{
int i;
int n = strlen(string);
int m = strlen(pattern);
for (i = 0; i <= n - m; i++)
{
int j;
for (j = 0; j < m; j++)
if (string[i + j] != pattern[j])
break;
if (j == m)
printf ("\nPattern matches at index %d", i);
}
}
void main()
{
clock_t start, end;
double cpuTimeUsed;
char string[100], pattern[100];
while (1)
{
printf("\nEnter string: ");
gets(string);
printf("\nEnter pattern: ");
gets(pattern);
start = clock();
patternSearch(string, pattern);
end = clock();
cpuTimeUsed = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nExecution time: %f seconds", cpuTimeUsed);
}
}
Enter string: LAKSFJGNSDLKFJGALSKDFJGLSJFGLDFKGJSN
Enter pattern: SN
Pattern matches at index 34
Execution time: 0.001000 seconds