Search for? 49
Linear search: 49 is in the numbers - search took 6 operations
Binary search: 49 is in the numbers - search took 20 operations
Search for? 42
Linear search: 42 is not in the numbers - search took 1000000 operations
Binary search: 42 is not in the numbers - search took 20 operations
Instrument linear search and binary search with an operation counter
and compare their performance on a sorted arrays of random numbers.
Array size is specified as a command line argument
#include <stdio.h>
#include <stdlib.h>
int linear_search(int array[], int length, int x);
int binary_search(int array[], int length, int x);
void quicksort(int array[], int length);
void quicksort1(int array[], int lo, int hi);
int partition(int array[], int lo, int hi);
void sorted_random_ints(int array[], int length);
void random_ints(int array[], int length);
// we use a global variable to instrument the program
// and count operations performed
int operation_counter;
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "Usage: %s <array-size>\n", argv[0]);
exit(1);
}
int length = atoi(argv[1]);
// use malloc to create an array so we can
// because we may want an array too large to be a global variable
int *numbers = malloc(length * sizeof (int));
if (numbers == NULL) {
fprintf(stderr, "%s: <array-size>\n", argv[0]);
exit(1);
}
sorted_random_ints(numbers, length);
printf("Array size is %d, elements are: ", length);
for (int i = 0; i < length; i = i + 1) {
printf(" %d", numbers[i]);
if (i == 20) {
printf(" ... ");
i = length;
}
}
printf("\n");
while (1) {
int x;
printf("Search for? ");
if (scanf("%d", &x) != 1) {
free(numbers);
return 0;
}
operation_counter = 0;
printf("\nLinear search: ");
if (linear_search(numbers, length, x) == 1) {
printf("%d is in the numbers", x);
} else {
printf("%d is not in the numbers", x);
}
printf(" - search took %d operations\n", operation_counter);
operation_counter = 0;
printf("Binary search: ");
if (binary_search(numbers, length, x) == 1) {
printf("%d is in the numbers", x);
} else {
printf("%d is not in the numbers", x);
}
printf(" - search took %d operations\n\n", operation_counter);
}
}
int linear_search(int array[], int length, int x) {
for (int i = 0; i < length; i = i + 1) {
operation_counter++;
if (array[i] == x) {
return 1;
}
}
return 0;
}
int binary_search(int array[], int length, int x) {
int lower = 0;
int upper = length - 1;
while (lower <= upper) {
int mid = (lower + upper)/ 2;
operation_counter++;
if (array[mid] == x) {
return 1;
} else if (array[mid] > x) {
upper = mid - 1;
} else {
lower = mid + 1;
}
}
return 0;
}
// fill array with pseudo-random ints
void random_ints(int array[], int length) {
for (int i = 0; i < length; i = i + 1) {
array[i] = rand() % (10 * length);
}
}
// fill array with pseudo-random ints in sorted (non-decreasing) order
void sorted_random_ints(int array[], int length) {
random_ints(array, length);
quicksort(array, length);
}
// https://en.wikipedia.org/wiki/Quicksort
void quicksort(int array[], int length) {
quicksort1(array, 0, length - 1);
}
void quicksort1(int array[], int lo, int hi) {
if (lo >= hi) {
return;
}
// rearrange array so that
// all elements smaller than pivot value are below it and
// all element larger than pivot value are above it
int p = partition(array, lo, hi);
// sort lower part of array
quicksort1(array, lo, p);
// sort upper part of array
quicksort1(array, p + 1, hi);
}
int partition(int array[], int lo, int hi) {
int i = lo;
int j = hi;
// use middle value as pivot
int pivotValue = array[(lo + hi) / 2];
// start from left and right ends
while (1) {
// Look for pair to swap
while (array[i] < pivotValue) {
i = i + 1;
operation_counter++;
}
while (array[j] > pivotValue) {
j = j - 1;
operation_counter++;
}
// No pair to swap so return
if (i >= j) {
return j;
}
// and swap them over
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i = i + 1;
j = j - 1;
}
}
$ dcc compare_sort.c
$ ./a.out
Array size 10: bubblesort took 81 operations, quicksort took 24 operations
Array size 100: bubblesort took 8415 operations, quicksort took 457 operations
Array size 1000: bubblesort took 981018 operations, quicksort took 9351 operations
Array size 10000: bubblesort took 98790120 operations, quicksort took 102807 operations
Instrument quicksort and bubblesort with an operation counter
and compare performance on arrays of random numbers of size 10..10000
#include <stdio.h>
#include <stdlib.h>
// use a global variable to count operations
// at key points for both sorting algorithms
int operation_counter;
void bubblesort(int array[], int length);
void quicksort(int array[], int length);
void quicksort1(int array[], int lo, int hi);
int partition(int array[], int lo, int hi);
void random_ints(int array[], int length);
int main(void) {
for (int n = 10; n <= 10000; n = n * 10) {
int numbers1[n];
int numbers2[n];
random_ints(numbers1, n);
for (int i = 0; i < n; i = i + 1) {
numbers2[i] = numbers1[i];
}
printf("Array size %5d: ", n);
operation_counter = 0;
bubblesort(numbers1, n);
printf(" bubblesort took %8d operations,", operation_counter);
operation_counter = 0;
quicksort(numbers2, n);
printf(" quicksort took %6d operations\n", operation_counter);
for (int i = 0; i < n; i = i + 1) {
if(numbers2[i] != numbers1[i]) {
printf("arrays differ at index %d\n", i);
return 1;
}
}
}
return 0;
}
// https://en.wikipedia.org/wiki/Bubble_sort
void bubblesort(int array[], int length) {
int swapped = 1;
while (swapped) {
swapped = 0;
for (int i = 1; i < length; i = i + 1) {
operation_counter++;
if (array[i] < array[i - 1]) {
int tmp = array[i];
array[i] = array[i - 1];
array[i - 1] = tmp;
swapped = 1;
}
}
}
}
// https://en.wikipedia.org/wiki/Quicksort
void quicksort(int array[], int length) {
quicksort1(array, 0, length - 1);
}
void quicksort1(int array[], int lo, int hi) {
if (lo >= hi) {
return;
}
// rearrange array so that
// all elements smaller than pivot value are below it and
// all element larger than pivot value are above it
int p = partition(array, lo, hi);
// sort lower part of array
quicksort1(array, lo, p);
// sort upper part of array
quicksort1(array, p + 1, hi);
}
int partition(int array[], int lo, int hi) {
int i = lo;
int j = hi;
// use middle value as pivot
int pivotValue = array[(lo + hi) / 2];
// start from left and right ends
while (1) {
// Look for pair to swap
while (array[i] < pivotValue) {
i = i + 1;
operation_counter++;
}
while (array[j] > pivotValue) {
j = j - 1;
operation_counter++;
}
// No pair to swap so return
if (i >= j) {
return j;
}
// and swap them over
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i = i + 1;
j = j - 1;
}
}
// fill array with pseudo-random ints
void random_ints(int array[], int length) {
for (int i = 0; i < length; i = i + 1) {
array[i] = rand() % (10 * length);
}
}
Instrument linear search and binary search with an operation counter and compare their performance on a sorted arrays of random numbers.
Array size is specified as a command line argument