Exercise 5-6. Rewrite appropriate programs from earlier chapters and exercises with pointers instead of array indexing. Good possibilities include getline() (Chapters 1 and 4), atoi(), itoa(), and their variants (Chapters 2, 3, and 4), reverse() (Chapter 3), and strindex() and getop() (Chapter 4).
#include <stdio.h> // for printf()
#include <time.h> // for clock_t, clock(), CLOCKS_PER_SEC
#define SIZE 1000000 // array size
// find x in v[0] <= v[1] <= ... <= v[n-1]
int binsearch1(int x, int v[], int n);
int binsearch2(int x, int v[], int n);
int binsearchp1(int x, int *v, int n); // pointer variants
int binsearchp2(int x, int *v, int n);
int main()
{
int array[SIZE+1]; // for ending '\0'
int i;
clock_t start, end;
double time;
for (i = 0; i < SIZE; i++) // initialize array
{
*(array+i) = i*2;
}
*(array+SIZE) = '\0';
start = clock();
for (i = 0; i < 100000000; i++)
{
binsearch1(i % (SIZE*2), array, SIZE);
}
end = clock();
time = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Execution time for binsearch1(): %f\n", time);
start = clock();
for (i = 0; i < 100000000; i++)
{
binsearchp1(i % (SIZE*2), array, SIZE);
}
end = clock();
time = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Execution time for binsearchp1(): %f\n", time);
start = clock();
for (i = 0; i < 100000000; i++)
{
binsearch2(i % (SIZE*2), array, SIZE);
}
end = clock();
time = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Execution time for binsearch2(): %f\n", time);
start = clock();
for (i = 0; i < 100000000; i++)
{
binsearchp2(i % (SIZE*2), array, SIZE);
}
end = clock();
time = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Execution time for binsearchp2(): %f\n", time);
return 0;
}
// find x in v[0] <= v[1] <= ... <= v[n-1]
int binsearch1(int x, int v[], int n)
{
int low = 0, high = n-1, mid;
while (low <= high)
{
if (x < v[low] || x > v[high])
{return -1;} // not found
if (x == v[low]) {return low;} // found
if (x == v[high]) {return high;} // found
mid = (low+high)/2;
if (x < v[mid])
{high = mid-1;}
else if (x > v[mid])
{low = mid+1;}
else {return mid;} // found match
}
return -1;
}
// find x in v[0] <= v[1] <= ... <= v[n-1]
int binsearchp1(int x, int *v, int n)
{
int *low = v, *high = v+n-1, *mid;
while (low <= high)
{
if (x < *low || x > *high)
{return -1;} // not found
if (x == *low) {return *low;} // found
if (x == *high) {return *high;} // found
mid = low + (high-low)/2;
if (x < *mid)
{high = mid-1;}
else if (x > *mid)
{low = mid+1;}
else {return *mid;} // found match
}
return -1;
}
// find x in increasingly sorted array v[] of size n
int binsearch2(int x, int v[], int n)
{
int low = 0, high = n-1, mid;
while (low < high)
{
mid = (low+high)/2;
if (x <= v[mid])
{high = mid;}
else {low = mid+1;}
}
if (x == v[high]) // found match
{return high;}
return -1;
}
// find x in increasingly sorted array v of size n
int binsearchp2(int x, int *v, int n)
{
int *low = v, *high = v+n-1, *mid;
while (low < high)
{
mid = low + (high-low)/2;
if (x <= *mid)
{high = mid;}
else {low = mid+1;}
}
if (x == *high) // found match
{return *high;}
return -1;
}
/*
gcc binsearch.c -o binsearch
./binsearch // SIZE 100
Execution time for binsearch1(): 4.539842
Execution time for binsearchp1(): 3.647170
Execution time for binsearch2(): 3.593694
Execution time for binsearchp2(): 4.551710
gcc binsearch.c -o binsearch
./binsearch // SIZE 1000
Execution time for binsearch1(): 8.654936
Execution time for binsearchp1(): 7.529870
Execution time for binsearch2(): 9.710993
Execution time for binsearchp2(): 9.727921
gcc binsearch.c -o binsearch
./binsearch // SIZE 10000
Execution time for binsearch1(): 10.492143
Execution time for binsearchp1(): 9.965404
Execution time for binsearch2(): 11.458571
Execution time for binsearchp2(): 12.200146
gcc binsearch.c -o binsearch
./binsearch // SIZE 100000
Execution time for binsearch1(): 13.175537
Execution time for binsearchp1(): 12.543357
Execution time for binsearch2(): 13.706660
Execution time for binsearchp2(): 14.330371
gcc binsearch.c -o binsearch
./binsearch // SIZE 1000000
Execution time for binsearch1(): 15.499027
Execution time for binsearchp1(): 17.515706
Execution time for binsearch2(): 15.664980
Execution time for binsearchp2(): 16.384891
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#include <stdio.h> // for printf(), scanf()
#define SIZE 100 // array size
int strLen(char *); // strlen() is declared in string.h, included by stdio.h
// sort v[0] ... v[n-1] or *v ... *(v+n-1) into increasing order
void shellsort(char *v, int n);
int main()
{
char array[SIZE];
printf("Type a word: ");
scanf("%s", array);
shellsort(array, strLen(array));
printf("Sorted: %s\n", array);
return 0;
}
int strLen(char *s)
{
int i = 0;
while (*(s+i) != '\0')
{i++;}
return i;
}
// sort v[0] ... v[n-1] or *v ... *(v+n-1) into increasing order
void shellsort(char *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)
{ // interchange v[j], v[j+gap] using a temporary variable
temp = *(v+j);
*(v+j) = *(v+j+gap);
*(v+j+gap) = temp;
}
}
}
}
/*
gcc shellc.c -o shellc
./shellc
Type a word: abracadabra
Sorted: aaaaabbcdrr
./shellc
Type a word: hocus-pocus
Sorted: -cchoopssuu
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#include <stdio.h> // for printf(), putchar()
#include <stdlib.h> // for srand(), rand()
#include <time.h> // for time_t, time()
#define SIZE 100 // array size
// sort v[0] ... v[n-1] or *v ... *(v+n-1) into increasing order
void shellsort(int *v, int n);
void printArray(int *arr, int n);
int main()
{
int array[SIZE];
int i;
time_t t;
srand((unsigned) time(&t)); // seed for rand()
for (i = 0; i < SIZE; i++)
{*(array+i) = rand() % 1000;} // initialize array[]
printf("Unsorted:\n");
printArray(array, SIZE);
shellsort(array, SIZE);
printf("\nSorted:\n");
printArray(array, SIZE);
return 0;
}
// sort v[0] ... v[n-1] or *v ... *(v+n-1) into increasing order
void shellsort(int v[], int n)
{
int gap, temp;
int *start = v, *mid, *end = v+n;
for (gap = n/2; gap > 0; gap /= 2)
{
for (mid = v+gap; mid < end; mid++)
{
for (start = mid-gap; start >= v && *start > *(start+gap); start -= gap)
{ // interchange *start, *(start+gap) using a temporary variable
temp = *start;
*start = *(start+gap);
*(start+gap) = temp;
}
}
}
}
void printArray(int *arr, int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("%d%c", *(arr+i), ((i % 10) == 9) || (i == n-1) ? '\n' : ' ');
}
if ((n % 10) != 0) {putchar('\n');}
}
/*
gcc shelli.c -o shelli
Unsorted:
73 896 304 97 264 845 908 250 246 508
560 87 732 455 218 378 980 759 922 250
890 995 751 517 517 12 11 26 975 450
776 401 698 80 850 315 278 758 565 524
267 125 963 351 932 182 729 264 941 3
514 183 998 618 52 867 630 415 246 957
866 22 710 916 103 561 231 381 319 148
257 938 625 220 290 557 402 19 174 343
375 688 878 373 306 930 593 288 346 839
598 564 861 308 480 316 869 64 697 541
Sorted:
3 11 12 19 22 26 52 64 73 80
87 97 103 125 148 174 182 183 218 220
231 246 246 250 250 257 264 264 267 278
288 290 304 306 308 315 316 319 343 346
351 373 375 378 381 401 402 415 450 455
480 508 514 517 517 524 541 557 560 561
564 565 593 598 618 625 630 688 697 698
710 729 732 751 758 759 776 839 845 850
861 866 867 869 878 890 896 908 916 922
930 932 938 941 957 963 975 980 995 998
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#include <stdio.h> // for printf(), putchar()
#include <stdlib.h> // for srand(), rand()
#include <time.h> // for time_t, time()
#define SIZE 100 // array size
// sort v[left] ... v[right] or *(v+left) ... *(v+right) into increasing order:
void qSort (int *v, int left, int right); // qsort() in declared in stdlib.h
int main()
{
int array[SIZE];
int i;
time_t t;
srand((unsigned) time(&t)); // seed for rand()
for (i = 0; i < SIZE; i++)
{*(array+i) = rand() % 1000;} // initialize array[]
printf("Unsorted:\n");
for (i = 0; i < SIZE; i++)
{
printf("%d%c", *(array+i), (i % 10) == 9 ? '\n' : ' ');
}
putchar('\n');
qSort(array, 0, SIZE-1);
printf("Sorted:\n");
for (i = 0; i < SIZE; i++)
{
printf("%d%c", *(array+i), (i % 10) == 9 ? '\n' : ' ');
}
return 0;
}
void swap(int *v, int i, int j); // swap v[i] and v[j] or *(v+i) and *(v+j)
// sort v[left] ... v[right] or *(v+left) ... *(v+right) into increasing order:
void qSort (int *v, int left, int right)
{
int i, last;
if (left >= right) // do nothing if array contains fewer that
{return;} // two elements (stopping condition for recursion)
swap(v, left, (left + right) / 2); // move partition element to v[left]
last = left; // v[left] is now in the middle of v[left] ... v[right]
for (i = left+1; i <= right; i++)
{ // value of `left' does not change here
if (*(v+i) < *(v+left)) // compare v[left] ... v[right] to partition element
{swap(v, ++last, i);} // smaller to the left, bigger to the right
}
swap(v, left, last); // restore partition element
qSort(v, left, last-1); // recursive call (sort first half)
qSort(v, last+1, right); // recursive call (sort last half)
}
void swap(int *v, int i, int j) // swap v[i] and v[j]
{
int temp;
temp = *(v+i);
*(v+i) = *(v+j);
*(v+j) = temp;
}
/*
gcc qsort1.c -o qsort1
./qsort1
Unsorted:
363 9 285 242 973 62 917 896 838 905
493 952 789 644 819 250 241 275 787 731
944 966 250 843 735 664 383 918 185 880
806 548 889 443 790 214 505 59 110 344
317 604 648 458 600 467 708 841 95 495
925 39 813 175 234 901 192 617 171 377
497 977 277 386 772 419 953 278 830 415
974 147 19 622 957 619 441 666 813 536
513 90 928 679 617 162 932 161 780 103
890 277 433 167 16 205 938 321 835 769
Sorted:
9 16 19 39 59 62 90 95 103 110
147 161 162 167 171 175 185 192 205 214
234 241 242 250 250 275 277 277 278 285
317 321 344 363 377 383 386 415 419 433
441 443 458 467 493 495 497 505 513 536
548 600 604 617 617 619 622 644 648 664
666 679 708 731 735 769 772 780 787 789
790 806 813 813 819 830 835 838 841 843
880 889 890 896 901 905 917 918 925 928
932 938 944 952 953 957 966 973 974 977
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#include <stdio.h> // for printf(), putchar()
#include <stdlib.h> // for srand(), rand()
#include <time.h> // for time_t, time()
#define SIZE 100 // array size
// sort *v ... *t into increasing order:
void qSort (int *v, int *t); // qsort() in declared in stdlib.h
int main()
{
int array[SIZE];
int i;
time_t t;
srand((unsigned) time(&t)); // seed for rand()
for (i = 0; i < SIZE; i++)
{*(array+i) = rand() % 1000;} // initialize array[]
printf("Unsorted:\n");
for (i = 0; i < SIZE; i++)
{
printf("%d%c", *(array+i), (i % 10) == 9 ? '\n' : ' ');
}
putchar('\n');
qSort(array, array+SIZE-1);
printf("Sorted:\n");
for (i = 0; i < SIZE; i++)
{
printf("%d%c", *(array+i), (i % 10) == 9 ? '\n' : ' ');
}
return 0;
}
void swap(int *v, int *t); // swap *v and *t
// sort *v ... *t into increasing order:
void qSort (int *v, int *t)
{
if (v >= t) // do nothing if array contains fewer that
{return;} // two elements (stopping condition for recursion)
int *iter, *last; // iterator
swap(v, v + (t - v) / 2); // move partition element to *v
last = v; // *v is now in the middle of *v ... *t
for (iter = v + 1; iter <= t; iter++)
{
if (*iter < *v) // compare *v ... *t to partition element
{swap(++last, iter);} // smaller to the left, bigger to the right
}
swap(v, last); // restore partition element
qSort(v, last-1); // recursive call (sort first half)
qSort(last+1, t); // recursive call (sort last half)
}
void swap(int *v, int *t) // swap *v and *t
{
int temp;
temp = *v;
*v = *t;
*t = temp;
}
/*
gcc qsort2.c -o qsort2
./qsort2
Unsorted:
58 774 68 323 104 140 365 493 549 25
411 875 576 760 948 726 823 840 81 180
114 971 321 897 370 655 788 421 555 259
761 614 34 829 289 138 970 655 984 871
32 747 746 608 859 694 334 682 886 768
214 353 91 535 250 462 542 39 235 450
298 996 64 332 826 705 823 796 360 159
667 392 906 413 353 765 460 39 799 698
807 14 51 899 901 654 361 444 693 948
894 343 944 310 28 770 15 203 918 728
Sorted:
14 15 25 28 32 34 39 39 51 58
64 68 81 91 104 114 138 140 159 180
203 214 235 250 259 289 298 310 321 323
332 334 343 353 353 360 361 365 370 392
411 413 421 444 450 460 462 493 535 542
549 555 576 608 614 654 655 655 667 682
693 694 698 705 726 728 746 747 760 761
765 768 770 774 788 796 799 807 823 823
826 829 840 859 871 875 886 894 897 899
901 906 918 944 948 948 970 971 984 996
*/