algorithms in c code.txt

This file contains the code from "Algorithms in C, Third Edition, Parts 1-4," by Robert Sedgewick,

    while (!QUEUEempty())
      if (visited[k = QUEUEget()] == 0)
        {
          (*visit)(k); visited[k] = 1;
          for (t = adj[k]; t != NULL; t = t->next)
            if (visited[t->v] == 0) QUEUEput(t->v);
        }
  }
-----

----------
CHAPTER 6. Elementary Sorting Methods
-----
#include <stdio.h>
#include <stdlib.h>
typedef int 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)
void sort(Item a[], int l, int r)
  { int i, j; 
    for (i = l+1; i <= r; i++)
      for (j = i; j > l; j--) 
        compexch(a[j-1], a[j]);
  }
main(int argc, char *argv[])
  { int i, N = atoi(argv[1]), sw = atoi(argv[2]);
    int *a = malloc(N*sizeof(int));
    if (sw) 
      for (i = 0; i < N; i++) 
        a[i] = 1000*(1.0*rand()/RAND_MAX);
    else 
      while (scanf("%d", &a[N]) == 1) N++; 
    sort(a, 0, N-1);
    for (i = 0; i < N; i++) printf("%3d ", a[i]);
    printf("\n");
  }
-----
void selection(Item a[], int l, int r)
  { 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 10
void 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 10000
Item 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 : B
void 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)