commit - 328c5416b4f9e108c66c4230f84140283565ebd4
commit + 76fcf99621439aea130b4dc5141a55c51a95486d
blob - 2e42cae8ee8a694673c6c6f5bea6b2ccccff60bc
blob + eb665286f4da7a59383e9d133561bf3e590dd72a
--- 3-1.c
+++ 3-1.c
@@ -2,24 +2,37 @@
  * suffice (at the price of more tests outside). Write a version with only one
  * test inside the loop and measure the difference in run-time. */
 
+/* Oddly enough, the "improved" binsrch gets worse performance on large sets */
+
 #include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
 
-#define MAXSIZE 100
+#define MAXSIZE 1000000
 
+int binsrch(int x, int v[], int n);
 int binsearch(int x, int v[], int n);
+void shellsort(int v[], int n);
 
 int main() {
-	int needle = 0;
 	int haystack[MAXSIZE];
-	int i;
-	if (scanf("%d\n", &needle) != 1) {
-		printf("Input must be one number per line, the first number is the needle\n");
-		return 1;
+	clock_t time;
+	for (int i = 0; i < MAXSIZE; i++)
+		haystack[i] = arc4random()%MAXSIZE;
+	shellsort(haystack, MAXSIZE);
+	for (int i = 0, time = clock(); i < MAXSIZE; i++) {
+		int needle = arc4random()%MAXSIZE;
+		binsrch(needle, haystack, MAXSIZE);
 	}
-	while(scanf("%d\n", &haystack[i++]) == 1)
-		;
-	printf("Needle %d found in haystack at index %d\n", needle, binsrch(needle, haystack, i));
-	/* note the index is 2 less than line number */
+	time = clock() - time;
+	printf("%llu to search %d times in array of %d using new binsrch\n", (unsigned long long)time, MAXSIZE, MAXSIZE);
+
+	for (int i = 0, time = clock(); i < MAXSIZE; i++) {
+		int needle = arc4random()%MAXSIZE;
+		binsearch(needle, haystack, MAXSIZE);
+	}
+	time = clock() - time;
+	printf("%llu to search %d times in array of %d using original binsearch\n", (unsigned long long)time, MAXSIZE, MAXSIZE);
 }
 
 /* binsrch: find x in v[0] <= v[1] <= ... <= v[n-1] */
@@ -59,3 +72,16 @@ int binsearch(int x, int v[], int n) {
 	}
 	return -1; /* no match */
 }
+
+/* shellsort: sort v[0]...v[n-1] into increasing order */
+void shellsort(int v[], int n) {
+	int gap, i, j, temp;
+	
+	for (gap = n/2; gap > 0; gap /= 2)
+		for (i = gap; i < n; i++)
+			for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) {
+				temp = v[j];
+				v[j] = v[j+gap];
+				v[j+gap] = temp;
+			}
+}