C/sorting.and.searching.cormen.algo/src/ins.txt

   1 /* insert sort */
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5
   6 typedef int T;          /* type of item to be sorted */
   7 typedef int tblIndex;   /* type of subscript */
   8
   9 #define compGT(a,b) (a > b)
  10
  11 void insertSort(T *a, tblIndex lb, tblIndex ub) {
  12     T t;
  13     tblIndex i, j;
  14
  15    /**************************
  16     *  sort array a[lb..ub]  *
  17     **************************/
  18     for (i = lb + 1; i <= ub; i++) {
  19         t = a[i];
  20
  21         /* Shift elements down until */
  22         /* insertion point found.    */
  23         for (j = i-1; j >= lb && compGT(a[j], t); j--)
  24             a[j+1] = a[j];
  25
  26         /* insert */
  27         a[j+1] = t;
  28     }
  29 }
  30
  31 void fill(T *a, tblIndex lb, tblIndex ub) {
  32     tblIndex i;
  33     srand(1);
  34     for (i = lb; i <= ub; i++) a[i] = rand();
  35 }
  36
  37 int main(int argc, char *argv[]) {
  38     tblIndex maxnum, lb, ub;
  39     T *a;
  40
  41     /* command-line:
  42      *
  43      *   ins maxnum
  44      *
  45      *   ins 2000
  46      *       sorts 2000 records
  47      *
  48      */
  49
  50     maxnum = atoi(argv[1]);
  51     lb = 0; ub = maxnum - 1;
  52     if ((a = malloc(maxnum * sizeof(T))) == 0) {
  53         fprintf (stderr, "insufficient memory (a)\n");
  54         exit(1);
  55     }
  56
  57     fill(a, lb, ub);
  58     insertSort(a, lb, ub);
  59
  60     return 0;
  61 }