(ALGL3) Brute Force Techniques - I

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

Binary Digit Count

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