algorithms in c++, parts 1-4 (fundamental algorithms, data structures, sorting, searching) code.txt

Algorithms in C++, Parts 1-4 (Fundamental Algorithms, Data Structures, Sorting, Searching) code

  void sort(Item a[], int l, int r)
    { for (int i = l+1; i <= r; i++)
        for (int j = i; j > l; j--) 
          compexch(a[j-1], a[j]);
    }
int main(int argc, char *argv[])
  { int i, N = atoi(argv[1]), sw = atoi(argv[2]);
    int *a = new int[N];
    if (sw) 
      for (i = 0; i < N; i++) 
        a[i] = 1000*(1.0*rand()/RAND_MAX);
    else 
      { N = 0; while (cin >> a[N]) N++; }
    sort(a, 0, N-1);
    for (i = 0; i < N; i++) cout << a[i] << " ";
    cout << endl;
  }
-----
template <class Item>
void selection(Item a[], int l, int r)
  { for (int i = l; i < r; i++)
      { int min = i;
        for (int j = i+1; j <= r; j++) 
            if (a[j] < a[min]) min = j;
        exch(a[i], a[min]);
      } 
  }
-----
template <class Item>
void insertion(Item a[], int l, int r)
  { int i;
    for (i = r; i > l; i--) compexch(a[i-1], a[i]);
    for (i = l+2; i <= r; i++)
      { int j = i; Item v = a[i]; 
        while (v < a[j-1])
          { a[j] = a[j-1]; j--; }
        a[j] = v; 
      } 
  }
-----
template <class Item>
void bubble(Item a[], int l, int r)
  { for (int i = l; i < r; i++)
      for (int j = r; j > i; j--)
        compexch(a[j-1], a[j]);
  }
-----
template <class Item>
void shellsort(Item a[], int l, int r)
  { int h; 
    for (h = 1; h <= (r-l)/9; h = 3*h+1) ;
    for ( ; h > 0; h /= 3)
      for (int i = l+h; i <= r; i++)
        { int j = i; Item v = a[i]; 
          while (j >= l+h && v < a[j-h])
            { a[j] = a[j-h]; j -= h; }
          a[j] = v; 
        } 
  }
-----
#include <stdlib.h>
#include "Item.h"
#include "exch.h"
#include "Array.h"
main(int argc, char *argv[])
  { int N = atoi(argv[1]), sw = atoi(argv[2]);
    Item *a = new Item[N];
    if (sw) rand(a, N); else scan(a, N); 
    sort(a, 0, N-1);
    show(a, 0, N-1);
  }
-----
template <class Item>
  void rand(Item a[], int N);
template <class Item>
  void scan(Item a[], int &N);
template <class Item>
  void show(Item a[], int l, int r);
template <class Item>
  void sort(Item a[], int l, int r);
-----
#include <iostream.h>                   
#include <stdlib.h>                   
#include "Array.h"
template <class Item>
  void rand(Item a[], int N)
    { for (int i = 0; i < N; i++) rand(a[i]); }
template <class Item>
  void scan(Item a[], int &N)
    { for (int i = 0; i < N; i++) 
        if (!scan(a[i])) break;
      N = i;
    }
template <class Item>
  void show(Item a[], int l, int r)
    { for (int i = l; i <=r; i++)
          show(a[i]);
      cout << endl;
    }  
-----
typedef struct record { int key; float info; } Item;
 int operator<(const Item&, const Item&);
 int scan(Item&);
void rand(Item&);
void show(const Item&);
-----
#include <iostream.h>
#include <stdlib.h>
#include "Item.h"
int operator<(const Item& A, const Item& B)
  { return A.key < B.key; }
int scan(Item& x)
  { return (cin >> x.key >> x.info) != 0; }
void rand(Item& x) 
  { x.key =  1000*(1.0*rand()/RAND_MAX); 
    x.info = 1.0*rand()/RAND_MAX; }  
void show(const Item& x)
  { cout << x.key << " " << x.info << endl; }
-----
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include "Item.h"
static char buf[100000];
static int cnt = 0;
int operator<(const Item& a, const Item& b)
  { return strcmp(a.str, b.str) < 0; }
void show(const Item& x)
  { cout << x.str << " "; }
int scan(Item& x)
  { int flag = (cin >> (x.str = &buf[cnt])) != 0; 
    cnt += strlen(x.str)+1;
    return flag; 
  }
-----
struct record { char name[30]; int num; };
typedef struct { record *r; } Item;
int operator<(const Item&, const Item&);
void rand(Item&);
void show(const Item&);
int scan(Item&);
-----
static record data[maxN];
static int cnt = 0;
void show(const Item& x)
  { cout << x.r->name << " " << x.r->num << endl; }
int scan(Item& x)
  {  
    x.r = &data[cnt++]; 
    return (cin >> x.r->name >> x.r->num) != 0; 
  }
-----
template <class Item>
void insitu(Item data[], Index a[], int N)
  { for (int i = 0; i < N; i++) 
      { Item v = data[i]; 
        int j, k;
        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;
      } 
  }  
-----
struct node 
  { Item item; node* next; 
    node(Item x) 
      { item = x; next = 0; } 
  };
typedef node *link;
link randlist(int);
link scanlist(int&);
void showlist(link);
link sortlist(link);
-----
link listselection(link h)
  { node dummy(0); link head = &dummy, out = 0;
    head->next = h;
    while (head->next != 0)
      { link max = findmax(head), t = max->next;
        max->next = t->next;
        t->next = out; out = t;
      } 
    return out;
  }
-----
void distcount(int a[], int l, int r)
  { int i, j, cnt[M]; 
    static 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-l];
  } 

----------
CHAPTER 7. Quicksort
-----
template <class Item>
void quicksort(Item a[], int l, int r)
  {
    if (r <= l) return;
    int i = partition(a, l, r);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
  }
-----
template <class Item>
int partition(Item a[], int l, int r)
  { int i = l-1, j = r; Item v = a[r];
    for (;;)
      { 
        while (a[++i] < v) ;
        while (v < a[--j]) if (j == l) break;
        if (i >= j) break;
        exch(a[i], a[j]);
      }
    exch(a[i], a[r]);
    return i;
  }
-----
#include "STACK.cxx"
inline void push2(STACK<int> &s, int A, int B)
  { s.push(B); s.push(A); }
template <class Item>
void quicksort(Item a[], int l, int r)
  { STACK<int> s(50); 
    push2(s, l, r);
    while (!s.empty())
      {
        l = s.pop(); r = s.pop(); 
        if (r <= l) continue;
        int i = partition(a, l, r);
        if (i-l > r-i)
          { push2(s, l, i-1); push2(s, i+1, r); }
        else
          { push2(s, i+1, r); push2(s, l, i-1); }
      }
  }
-----
static const int M = 10;
template <class Item>
void quicksort(Item a[], int l, int r)
  {
    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]);
    int i = partition(a, l+1, r-1);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
  } 
template <class Item>
void hybridsort(Item a[], int l, int r)
  { quicksort(a, l, r); insertion(a, l, r); }
-----
template <class Item>
int operator==(const Item &A, const Item &B)
  { return !less(A, B) && !less(B, A); }
template <class Item>
void quicksort(Item a[], int l, int r)
  { int k; Item v = a[r];
    if (r <= l) return;
    int i = l-1, j = r, p = l-1, q = r;
    for (;;)
      { 
        while (a[++i] < v) ;
        while (v < a[--j]) if (j == l) break;
        if (i >= j) break;
        exch(a[i],a[j]);
        if (a[i] == v) { p++; exch(a[p],a[i]); }
        if (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); 
  }
-----
template <class Item>
void select(Item a[], int l, int r, int k)
  {
    if (r <= l) return;
    int i = partition(a, l, r);
    if (i > k) select(a, l, i-1, k);
    if (i < k) select(a, i+1, r, k);
  }
-----
template <class Item>
void 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
-----
template <class Item>
void mergeAB(Item c[], Item a[], int N, 
                       Item b[], int M )
  {
    for (int 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] = (a[i] < b[j]) ? a[i++] : b[j++];
      }
  }
-----
template <class Item>
void merge(Item a[], int l, int m, int r)
  { int i, j;
    static Item aux[maxN];
    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 (int k = l; k <= r; k++)
       if (aux[j] < aux[i]) 
          a[k] = aux[j--]; else a[k] = aux[i++];
  }
-----
template <class Item>
void mergesort(Item a[], int l, int r)
  { if (r <= l) return;
    int m = (r+l)/2;
    mergesort(a, l, m);  
    mergesort(a, m+1, r);
    merge(a, l, m, r);
  }
-----
template <class Item>
void mergesortABr(Item a[], Item b[], int l, int r)
  { if (r-l <= 10) { insertion(a, l, r); return; }
    int m = (l+r)/2;
    mergesortABr(b, a, l, m);  
    mergesortABr(b, a, m+1, r);
    mergeAB(a+l, b+l, m-l+1, b+m+1, r-m);
  }
template <class Item>
void mergesortAB(Item a[], int l, int r)
  { static Item aux[maxN];
    for (int i = l; i <= r; i++) aux[i] = a[i];
    mergesortABr(a, aux, l, r);
  }
-----
inline int min(int A, int B) 
  { return (A < B) ? A : B; }
template <class Item>
void mergesortBU(Item a[], int l, int r)
  {
    for (int m = 1; m <= r-l; m = m+m)
      for (int 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)
  { node dummy(0); link head = &dummy, c = head;
    while ((a != 0) && (b != 0))
      if (a->item < b->item)
        { c->next = a; c = a; a = a->next; }
      else
        { c->next = b; c = b; b = b->next; }
    c->next = (a == 0) ? b : a;
    return head->next;
  }
-----
link mergesort(link c)
  { 
    if (c == 0 || c->next == 0) return c;
    link a = c, b = c->next;
    while ((b != 0) && (b->next != 0))
      { c = c->next; b = b->next->next; }
    b = c->next; c->next = 0;
    return merge(mergesort(a), mergesort(b));
  }
-----
link mergesort(link t)
  { QUEUE<link> Q(max);
    if (t == 0 || t->next == 0) return t;
    for (link u = 0; t != 0; t = u) 
      { u = t->next; t->next = 0; Q.put(t); }
    t = Q.get();     
    while (!Q.empty())
      { Q.put(t); t = merge(Q.get(), Q.get()); }
    return t;
  }

----------
CHAPTER 9. Priority Queues and Heapsort
-----
template <class Item>
class PQ 
  {
    private:
      // Implementation-dependent code
    public:
      PQ(int);
      int empty() const;
      void insert(Item);
      Item getmax();
  };
-----
template <class Item>
class PQ 
  {
    private:
      Item *pq; 
      int N;
    public:
      PQ(int maxN)
        { pq = new Item[maxN]; N = 0; }
      int empty() const
        { return N == 0; }
      void insert(Item item)
        { pq[N++] = item; }
      Item getmax()
        { int max = 0;
          for (int j = 1; j < N; j++)
            if (pq[max] < pq[j]) max = j;
          exch(pq[max], pq[N-1]);  
          return pq[--N];
        }
  };
-----
template <class Item>
void fixUp(Item a[], int k)
  {
    while (k > 1 && a[k/2] < a[k])
      { exch(a[k], a[k/2]); k = k/2; }
  }
-----
template <class Item>
void fixDown(Item a[], int k, int N)
  {
    while (2*k <= N)
      { int j = 2*k;
        if (j < N && a[j] < a[j+1]) j++;
        if (!(a[k] < a[j])) break;
        exch(a[k], a[j]); k = j;
      }
  }
-----
template <class Item>
class PQ 
  {
    private:
      Item *pq; 
      int N;
    public:
      PQ(int maxN)
        { pq = new Item[maxN+1]; N = 0; }
      int empty() const
        { return N == 0; }
      void insert(Item item)
        { pq[++N] = item;  fixUp(pq, N); }
      Item getmax()
        { 
          exch(pq[1], pq[N]); 
          fixDown(pq, 1, N-1); 
          return pq[N--]; 
        }
  };
-----
#include "PQ.cxx"
template <class Item>
void PQsort(Item a[], int l, int r)
  { int k;
    PQ<Item> pq(r-l+1);
    for (k = l; k <= r; k++) pq.insert(a[k]);
    for (k = r; k >= l; k--) a[k] = pq.getmax();
  }
-----
template <class Item>
void heapsort(Item a[], int l, int r)
  { int k, N = r-l+1;
    Item *pq = a+l-1;
    for (k = N/2; k >= 1; k--) 
      fixDown(pq, k, N);
    while (N > 1) 
      { exch(pq[1], pq[N]); 
        fixDown(pq, 1, --N); }
  }
-----
template <class Item>
class PQ 
  {
    private:
      // Implementation-dependent code
    public:
      // Implementation-dependent handle definition
      PQ(int);
      int empty() const;
      handle insert(Item);
      Item getmax();
      void change(handle, Item);
      void remove(handle);
      void join(PQ<Item>&);
  };
-----
template <class Item>
class PQ 
  {
    private:
      struct node 
        { Item item; node *prev, *next; 
          node(Item v) 
            { item = v; prev = 0; next = 0; } 
        }; 
      typedef node *link;
      link head, tail;
    public:
      typedef node* handle;
      PQ(int = 0)
        { 
          head = new node(0); tail = new node(0); 
          head->prev = tail; head->next = tail;
          tail->prev = head; tail->next = head; 
        }
      int empty() const
        { return head->next->next == head; }
      handle insert(Item v)
        { handle t = new node(v);
          t->next = head->next; t->next->prev = t;
          t->prev = head; head->next = t;
          return t;
         }
      Item getmax();
      void change(handle, Item);
      void remove(handle);