Book Review

The practice of programming

Chapter 2 Algorithms and Data Structures

• Searching

1. sequential search (linear search):

   easy but the amount of work is directly proportional to the amount of data to be searched

2. binary search:

    The number of steps is logn, so it‘s more efficient for a lager array

• Sorting

the following quicksort is what I used to code:

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int ascend(int a, int b) {
    return (a < b);
}

int descend(int a, int b) {
    return (a > b);
}

void qsort( int num, int arrange_by[], int other[], 
            int start, int end, int (*compare)(int a, int b) ) {

    int head = start, tail = end, mid = arrange_by[(head+tail)/2], temp;
    while (head <= tail) {
        while ( (*compare) (arrange_by[head], mid) ) head ++;
        while ( (*compare) (mid, arrange_by[tail]) ) tail --;
        if (head <= tail) {
            swap(&arrange_by[head], &arrange_by[tail]);
            swap(&other[head], &other[tail]);
            head ++; tail --;
        }
    }
    if (start < tail) qsort( num, arrange_by, other,
                             start, tail, compare );
    if (head < end) qsort( num, arrange_by, other,
                            head, end, compare );
}

• Libraries

1.  qsort: for example, sort an array of strings:

   /* scmp: string compare of *pl and *p2 */
   int scmp(const void *p1, const void *p2)
   {
   char *v1, *v2;
   v1 = *(char **) p1;
   v2 = *(char **) p2;
   return strcmp(v1, v2) ;
   }

   We can‘t use strcmp  directly as the comparison function because qsort  passes the address of each entry in the array, &str [i]  (of type char**),  not str [i]  (of type char*).

   To sort elements str[O]  through str[N-l]  of an array of strings, qsort  must be called with the array, its length, the size of the items being sorted, and the comparison function:

   char astr[N] ;
   
   qsort(str, N, sizeof(str[O]) , scmp);

    

2. ANSIC also defines a binary search routine, bsearch.

   /* lookup: use bsearch t o f i n d name i n tab, return index */
   int lookup(char *name, Nameval tab[], i n t ntab)
   {
   Nameval key, anp;
   key.name = name;
   key-value = 0; /* unused; anything will do */
   np = (Nameval *) bsearch(&key, tab, ntab, sizeof (tablo]), nvcmp);
   if (np == NULL)
   　　return -1;
   else
   　　return np-tab;
   }

   As with qsort, the comparison routine receives the address of the items to be

   compared, so the key must have that type; in this example, we need to construct a fake

   Nameval entry that is passed to the comparison routine. The comparison routine itself

    is a function nvcmp  that compares two Nameval  items by calling strcmp  on their

   string components, ignoring their values:

   /* nvcmp: compare two Nameval names */
   i n t nvcmp(const void ava, const void avb)
   const Nameval *a, ab;
   a = (Nameval a) va;
   b = (Nameval a) vb:
   return strcmp(a->name, b->name);
   3

    

3.  The standard C++  library has a generic algorithm called sort  that guarantees

   O(n1ogn) behavior.

   int arr[N];
   sort(arr, arr + N);

    

Book Review

原文：http://www.cnblogs.com/Christen/p/4987178.html