{ int i, j;    for (i = l; i < r; i++)      { int min = i;        for (j = i+1; j <= r; j++)             if (less(a[j], a[min])) min = j;        exch(a[i], a[min]);      }   }-----void insertion(Item a[], int l, int r)  { int i;    for (i = l+1; i <= r; i++) compexch(a[l], a[i]);    for (i = l+2; i <= r; i++)      { int j = i; Item v = a[i];         while (less(v, a[j-1]))          { a[j] = a[j-1]; j--; }        a[j] = v;       }   }-----void bubble(Item a[], int l, int r)  { int i, j;    for (i = l; i < r; i++)      for (j = r; j > i; j--)        compexch(a[j-1], a[j]);  }-----void shellsort(Item a[], int l, int r)  { int i, j, h;     for (h = 1; h <= (r-l)/9; h = 3*h+1) ;    for ( ; h > 0; h /= 3)      for (i = l+h; i <= r; i++)        { int j = i; Item v = a[i];           while (j >= l+h && less(v, a[j-h]))            { a[j] = a[j-h]; j -= h; }          a[j] = v;         }   }-----#include <stdlib.h>#include "Item.h"#include "Array.h"main(int argc, char *argv[])  { int i, N = atoi(argv[1]), sw = atoi(argv[2]);    Item *a = malloc(N*sizeof(Item));    if (sw) randinit(a, N); else scaninit(a, &N);     sort(a, 0, N-1);    show(a, 0, N-1);  }-----void randinit(Item [], int);void scaninit(Item [], int *);void show(Item [], int, int);void sort(Item [], int, int);-----#include <stdio.h>                   #include <stdlib.h>                   #include "Item.h"#include "Array.h"void randinit(Item a[], int N)  { int i;    for (i = 0; i < N; i++) a[i] = ITEMrand();  }void scaninit(Item a[], int *N)  { int i = 0;    for (i = 0; i < *N; i++)       if (ITEMscan(&a[i]) == EOF) break;    *N = i;  }void show(itemType a[], int l, int r)  { int i;    for (i = l; i <= r; i++) ITEMshow(a[i]);     printf("\n");  }  -----typedef double Item;#define key(A) (A)#define less(A, B) (key(A) < key(B))#define exch(A, B) { Item t = A; A = B; B = t; } #define compexch(A, B) if (less(B, A)) exch(A, B)Item ITEMrand(void); int ITEMscan(Item *);void ITEMshow(Item);-----#include <stdio.h>#include <stdlib.h>#include "Item.h"double ITEMrand(void)          { return 1.0*rand()/RAND_MAX; }     int ITEMscan(double *x)          { return scanf("%f", x); }    void ITEMshow(double x)          { printf("%7.5f ", x); }  -----#include <stdio.h>#include <stdlib.h>#include <string.h>#include "Item.h"static char buf[100000];static int cnt = 0;int ITEMscan(char **x)  { int t;    *x = &buf[cnt];     t = scanf("%s", *x); cnt += strlen(*x)+1;    return t;  }  void ITEMshow(char *x)   { printf("%s ", x); }  -----struct record { char name[30]; int num; };typedef struct record* Item;#define exch(A, B) { Item t = A; A = B; B = t; } #define compexch(A, B) if (less(B, A)) exch(A, B); int less(Item, Item);Item ITEMrand(); int ITEMscan(Item *);void ITEMshow(Item);-----struct record data[maxN];int Nrecs = 0;int ITEMscan(struct record **x)  {     *x = &data[Nrecs];    return scanf("%30s %d\n",              data[Nrecs].name, &data[Nrecs++].num);  }void ITEMshow(struct record *x)  { printf("%3d %-30s\n", x->num, x->name); }  -----insitu(dataType data[], int a[], int N)  { int i, j, k;     for (i = 0; i < N; i++)       { dataType v = data[i];         for (k = i; a[k] != i; k = a[j], a[j] = j)          { j = k; data[k] = data[a[k]]; }        data[k] = v; a[k] = k;      }   }  -----typedef struct node *link;struct node { Item item;  link next; };link NEW(Item, link);link init(int);void show(link);link sort(link);-----link listselection(link h)  { link max, t, out = NULL;    while (h->next != NULL)      {         max = findmax(h);        t = max->next; max->next = t->next;        t->next = out; out = t;      }     h->next = out;    return(h);  }-----void distcount(int a[], int l, int r)  { int i, j, cnt[M];     int b[maxN];    for (j = 0; j <  M; j++) cnt[j] = 0;    for (i = l; i <= r; i++) cnt[a[i]+1]++;    for (j = 1; j <  M; j++) cnt[j] += cnt[j-1];    for (i = l; i <= r; i++) b[cnt[a[i]]++] = a[i];    for (i = l; i <= r; i++) a[i] = b[i];  } -----void insertion(itemType a[], int l, int r)  { int i, j;     for (i = l+1; i <= r; i++)      for (j = i; j > l; j--)        if (less(a[j-1], a[j])) break;        else exch(a[j-1], a[j]);  }----------CHAPTER 7. Quicksort----- int partition(Item a[], int l, int r);void quicksort(Item a[], int l, int r)  { int i;    if (r <= l) return;    i = partition(a, l, r);    quicksort(a, l, i-1);    quicksort(a, i+1, r);  }-----int partition(Item a[], int l, int r)  { int i = l-1, j = r; Item v = a[r];    for (;;)      {         while (less(a[++i], v)) ;        while (less(v, a[--j])) if (j == l) break;        if (i >= j) break;        exch(a[i], a[j]);      }    exch(a[i], a[r]);    return i;  }-----#define push2(A, B)  push(B); push(A);void quicksort(Item a[], int l, int r)  { int i;    stackinit(); push2(l, r);    while (!stackempty())      {        l = pop(); r = pop();         if (r <= l) continue;        i = partition(a, l, r);        if (i-l > r-i)          { push2(l, i-1); push2(i+1, r); }        else          { push2(i+1, r); push2(l, i-1); }      }  }-----#define M 10void quicksort(Item a[], int l, int r)  { int i;     if (r-l <= M) return;    exch(a[(l+r)/2], a[r-1]);    compexch(a[l], a[r-1]);       compexch(a[l], a[r]);         compexch(a[r-1], a[r]);    i = partition(a, l+1, r-1);    quicksort(a, l, i-1);    quicksort(a, i+1, r);  } void sort(Item a[], int l, int r)  {     quicksort(a, l, r);    insertion(a, l, r);  }-----#define eq(A, B) (!less(A, B) && !less(B, A))void quicksort(Item a[], int l, int r)  { int i, j, k, p, q; Item v;    if (r <= l) return;    v = a[r]; i = l-1; j = r; p = l-1; q = r;    for (;;)      {         while (less(a[++i], v)) ;        while (less(v, a[--j])) if (j == l) break;        if (i >= j) break;        exch(a[i], a[j]);        if (eq(a[i], v)) { p++; exch(a[p], a[i]); }        if (eq(v, a[j])) { q--; exch(a[q], a[j]); }      }    exch(a[i], a[r]); j = i-1; i = i+1;    for (k = l  ; k < p; k++, j--) exch(a[k], a[j]);    for (k = r-1; k > q; k--, i++) exch(a[k], a[i]);    quicksort(a, l, j);    quicksort(a, i, r);   }-----select(Item a[], int l, int r, int k)  { int i;    if (r <= l) return;    i = partition(a, l, r);    if (i > k) select(a, l, i-1, k);    if (i < k) select(a, i+1, r, k);  }-----select(Item a[], int l, int r, int k)  {     while (r > l)      { int i = partition(a, l, r);        if (i >= k) r = i-1;        if (i <= k) l = i+1;      }   }----------CHAPTER 8. Mergesort-----mergeAB(Item c[], Item a[], int N, Item b[], int M )  { int i, j, k;    for (i = 0, j = 0, k = 0; k < N+M; k++)      {        if (i == N) { c[k] = b[j++]; continue; }        if (j == M) { c[k] = a[i++]; continue; }        c[k] = (less(a[i], b[j])) ? a[i++] : b[j++];      }  }-----Item aux[maxN];merge(Item a[], int l, int m, int r)  { int i, j, k;    for (i = m+1; i > l; i--) aux[i-1] = a[i-1];    for (j = m; j < r; j++) aux[r+m-j] = a[j+1];    for (k = l; k <= r; k++)       if (less(aux[i], aux[j]))           a[k] = aux[i++]; else a[k] = aux[j--];  }-----void mergesort(Item a[], int l, int r)  { int m = (r+l)/2;    if (r <= l) return;    mergesort(a, l, m);      mergesort(a, m+1, r);    merge(a, l, m, r);  }-----#define maxN 10000Item aux[maxN];void mergesortABr(Item a[], Item b[], int l, int r)  { int m = (l+r)/2;    if (r-l <= 10) { insertion(a, l, r); return; }    mergesortABr(b, a, l, m);      mergesortABr(b, a, m+1, r);    mergeAB(a+l, b+l, m-l+1, b+m+1, r-m);  }void mergesortAB(Item a[], int l, int r)  { int i;    for (i = l; i <= r; i++) aux[i] = a[i];    mergesortABr(a, aux, l, r);  }-----#define min(A, B) (A < B) ? A : Bvoid mergesortBU(Item a[], int l, int r)  { int i, m;    for (m = 1; m < r-l; m = m+m)      for (i = l; i <= r-m; i += m+m)        merge(a, i, i+m-1, min(i+m+m-1, r));  }-----link merge(link a, link b)  { struct node head; link c = &head;    while ((a != NULL) && (b != NULL))      if (less(a->item, b->item))        { c->next = a; c = a; a = a->next; }      else        { c->next = b; c = b; b = b->next; }    c->next = (a == NULL) ? b : a;    return head.next;  }-----link merge(link a, link b);link mergesort(link c)  { link a, b;    if (c->next == NULL) return c;    a = c; b = c->next;    while ((b != NULL) && (b->next != NULL))      { c = c->next; b = b->next->next; }    b = c->next; c->next = NULL;    return merge(mergesort(a), mergesort(b));  }-----link mergesort(link t)  { link u;    for (Qinit(); t != NULL; t = u)       { u = t->next; t->next = NULL; Qput(t); }    t = Qget();         while (!Qempty())      { Qput(t); t = merge(Qget(), Qget()); }    return t;  }----------CHAPTER 9. Priority Queues and Heapsort-----void PQinit(int); int PQempty();void PQinsert(Item);Item PQdelmax();-----#include <stdlib.h>#include "Item.h"   static Item *pq; static int N;void PQinit(int maxN)  { pq = malloc(maxN*sizeof(Item)); N = 0; } int PQempty()   { return N == 0; }void PQinsert(Item v)  { pq[N++] = v; }Item PQdelmax()  { int j, max = 0;    for (j = 1; j < N; j++)      if (less(pq[max], pq[j])) max = j;    exch(pq[max], pq[N-1]);      return pq[--N];  }-----fixUp(Item a[], int k)  {    while (k > 1 && less(a[k/2], a[k]))      { exch(a[k], a[k/2]); k = k/2; }  }-----fixDown(Item a[], int k, int N)  { int j;    while (2*k <= N)      { j = 2*k;        if (j < N && less(a[j], a[j+1])) j++;        if (!less(a[k], a[j])) break;        exch(a[k], a[j]); k = j;      }  }-----#include <stdlib.h>#include "Item.h"   static Item *pq; static int N;void PQinit(int maxN)  { pq = malloc((maxN+1)*sizeof(Item)); N = 0; } int PQempty()   { return N == 0; }void PQinsert(Item v)  { pq[++N] = v; fixUp(pq, N); }Item PQdelmax()  {     exch(pq[1], pq[N]);     fixDown(pq, 1, N-1);     return pq[N--];   }-----void PQsort(Item a[], int l, int r)  { int k;    PQinit();    for (k = l; k <= r; k++) PQinsert(a[k]);    for (k = r; k >= l; k--) a[k] = PQdelmax();  }-----#define pq(A) a[l-1+A]void heapsort(Item a[], int l, int r)  { int k, N = r-l+1;    for (k = N/2; k >= 1; k--)       fixDown(&pq(0), k, N);    while (N > 1)       { exch(pq(1), pq(N));         fixDown(&pq(0), 1, --N); }  }-----typedef struct pq* PQ;typedef struct PQnode* PQlink;    PQ PQinit();   int PQempty(PQ);PQlink PQinsert(PQ, Item);  Item PQdelmax(PQ);  void PQchange(PQ, PQlink, Item);  void PQdelete(PQ, PQlink);  void PQjoin(PQ, PQ);-----#include <stdlib.h>#include "Item.h"#include "PQfull.h"struct PQnode { Item key; PQlink prev, next; };struct pq { PQlink head, tail; };PQ PQinit()  { PQ pq = malloc(sizeof *pq);    PQlink h = malloc(sizeof *h),           t = malloc(sizeof *t);    h->prev = t; h->next = t;    t->prev = h; t->next = h;    pq->head = h; pq->tail = t;    return pq;  }int PQempty(PQ pq)  { return pq->head->next->next == pq->head; }PQlink PQinsert(PQ pq, Item v)  { PQlink t = malloc(sizeof *t);    t->key = v;     t->next = pq->head->next; t->next->prev = t;    t->prev = pq->head; pq->head->next = t;  }Item PQdelmax(PQ pq)  { Item max; struct PQnode *t, *x = pq->head->next;    for (t = x; t->next != pq->head; t = t->next)      if (t->key > x->key) x = t;    max = x->key;     x->next->prev = x->prev;     x->prev->next = x->next;     free(x); return max;  }-----void PQchange(PQ pq, PQlink x, Item v)  { x->key = v; }  void PQdelete(PQ pq, PQlink x)  { PQlink t;    t->next->prev = t->prev;    t->prev->next = t->next;    free(t);  }  void PQjoin(PQ a, PQ b)  { PQlink atail, bhead;    a->tail->prev->next = b->head->next;    b->head->next->prev = a->tail->prev;    a->head->prev = b->tail;     b->tail->next = a->head;    free(a->tail); free(b->head);  }----- int less(int, int);void PQinit(); int PQempty();void PQinsert(int); int PQdelmax();void PQchange(int);void PQdelete(int);-----#include "PQindex.h"typedef int Item;static int N, pq[maxPQ+1], qp[maxPQ+1];void exch(int i, int j)  { int t;    t = i; i = j; j = t;    t = qp[i]; qp[i] = qp[j]; qp[j] = t;  }void PQinit() { N = 0; } int PQempty() { return !N; }void PQinsert(int k)  { qp[k] = ++N; pq[N] = k; fixUp(pq, N); } int PQdelmax()  {     exch(pq[1], pq[N]);     fixDown(pq, 1, --N);     return pq[N+1];   }void PQchange(int k)  { fixUp(pq, qp[k]); fixDown(pq, qp[k], N); }