This file contains (part of) the code from "Algorithms in C, Third Edition,
Parts 1-4," by Robert Sedgewick, and is covered under the copyright
and warranty notices in that book. Permission is granted for this
code to be used for educational purposes in association with the text,
and for other uses not covered by copyright laws, provided that
the following notice is included with the code:

 	"This code is from "Algorithms in C, Third Edition,"
	by Robert Sedgewick, Addison Wesley Longman, 1998."

Commercial uses of this code require the explicit written
permission of the publisher. Send your request for permission,
stating clearly what code you would like to use, and in what
specific way, to: aw.cse@aw.com

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]);
  }


----------