(ALGL9) Space & Time Tradeoffs
(ALGL9) Space & Time Tradeoffs

(ALGL9) Space & Time Tradeoffs

 

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); }