Brute Force Techniques I

Comparison Counting

#include <stdio.h>
#define SIZE 10

void comparisonCount(int arr[])
{
    int i, output[SIZE];

    int max = arr[0];
    for (i = 1; i < SIZE; i++)
    {
        if (arr[i] > max)
            max = arr[i];
    }

    int count[SIZE];
    for (i = 0; i <= max; i++)
        count[i] = 0;

    for (i = 0; i < SIZE; i++)
        count[arr[i]]++;

    for (i = 1; i <= max; i++)
        count[i] += count[i - 1];

    for (i = SIZE - 1; i >= 0; i--)
    {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (i = 0; i < SIZE; i++) {
    arr[i] = output[i];
    }
}

void printArray(int array[]) {
    int i;
    for (i = 0; i < SIZE; ++i) {
        printf("%d  ", array[i]);
    }
    printf("\n");
}

void main() {
    int array[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(array) / sizeof(array[0]);
    comparisonCount(array);
    printArray(array);
}

Boyer-Moore Pattern Matching

#include <stdio.h>
#define SIZE 10

void comparisonCount(int arr[])
{
    int i, output[SIZE];

    int max = arr[0];
    for (i = 1; i < SIZE; i++)
    {
        if (arr[i] > max)
            max = arr[i];
    }

    int count[SIZE];
    for (i = 0; i <= max; i++)
        count[i] = 0;

    for (i = 0; i < SIZE; i++)
        count[arr[i]]++;

    for (i = 1; i <= max; i++)
        count[i] += count[i - 1];

    for (i = SIZE - 1; i >= 0; i--)
    {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (i = 0; i < SIZE; i++) {
    arr[i] = output[i];
    }
}

void printArray(int array[]) {
    int i;
    for (i = 0; i < SIZE; ++i) {
        printf("%d  ", array[i]);
    }
    printf("\n");
}

void main() {
    int array[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(array) / sizeof(array[0]);
    comparisonCount(array);
    printArray(array);
}