home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c072 / 1.ddi / PRG3_4.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-09-19  |  3.5 KB  |  118 lines
  1. /* Program 3_4 - the classic Bubble Sort using user-supplied routines
  2.     by Stephen R. Davis, 1987
  3.  
  4.   The bubble sort routine first appeared in Kernighan and Ritchie as
  5.   an example of the passing of one routine to another.  This is a
  6.   further generalization of that routine.  This version is as
  7.   completely general as is possible.
  8.  
  9.   SORT () can sort ANY data type, including any user defined
  10.     structure, if provided with three routines: one to compare two
  11.     entries, another to swap two entries and a third to sequence from
  12.     one entry to the next.  The details of these routines are given
  13.     below.  Sort returns a 0 if the sort is successful and a -1
  14.     otherwise.
  15.  
  16.   COMPARE(ptr1, ptr2)
  17.     receives two pointers to the structures to be compared.
  18.     Returns a -1 if *ptr1 < *ptr2, a 0 if *ptr1 == *ptr2, and 1 if
  19.     *ptr1 > *ptr2 for ascending order and the opposite for
  20.     descending.
  21.  
  22.   SWAP (ptr1, ptr2)
  23.     receives two pointers to structures.  Upon returning *ptr2 is
  24.     in the location of *ptr1 and visca versa.  If ptr1 == ptr2 then
  25.     swap() has no effect.  Swap() returns a 0 if the exchange is
  26.     successful and a non-zero otherwise.
  27.  
  28.   SEQUENCE (ptr1)
  29.     receives a pointer to an entry.  Returns a pointer to the
  30.     next entry.  Notice that the definition of "next" is left to
  31.     the user.  If ptr1 == 0, sequence() returns the first entry.
  32.     If sequence () == 0 then the end of sequence has been reached.
  33. */
  34.  
  35. #include <stdio.h>
  36.  
  37. /*prototype definitions --*/
  38. int sort (int (*)(void *, void *), int (*)(void *, void *),
  39.       void *(*)(void *));
  40.  
  41. /*Sort - impliment bubble sort*/
  42. int sort (compare, swap, sequence)
  43.      int (*compare)(void *, void *), (*swap)(void *, void *);
  44.      void *(*sequence)(void *);
  45. {
  46.     int flag;
  47.     void *p1, *p2;
  48.  
  49.     do {
  50.          flag =  0;
  51.          p2 = (*sequence)(0);          /*starting w/ first entry...*/
  52.          while (p1 = p2, p2 = (*sequence) (p2)) /*...sequence thru*/
  53.          {
  54.               if ((*compare)(p1, p2) > 0) {     /*if p1 > p2...*/
  55.                    if ((*swap)(p1, p2)) return -1;/*...swap p1 & p2*/
  56.                    flag = 1;
  57.               }
  58.          }
  59.        } while (flag);                 /*stop when all are in order*/
  60.     return 0;
  61. }
  62.  
  63.  
  64. /*simple example of using SORT() --
  65.   let's simply sort an array of integers called "data" declared
  66.   globally with N entries.  Convince yourself that the 3 routines
  67.   below actually operate according to the description above.  Then
  68.   prove that it works at all by executing the program.
  69. */
  70.  
  71. #define N 10
  72. int data [N];
  73.  
  74.  
  75. int compare (i1, i2)
  76.     int *i1, *i2;
  77. {
  78.     if (*i1 != *i2) return (*i1 > *i2) ? 1: -1;
  79.     return 0;
  80. }
  81.  
  82. int swap (i1, i2)
  83.     int *i1, *i2;
  84. {
  85.     int temp;
  86.  
  87.     temp = *i1;
  88.     *i1 = *i2;
  89.     *i2 = temp;
  90.     return 0;
  91. }
  92.  
  93. void *sequence (i)
  94.     int *i;
  95. {
  96.     if (i)
  97.          if (i == &data[N - 1])        /*if last entry...*/
  98.               return 0;                /*...return a 0; else...*/
  99.          else
  100.               return ++i;              /*...return the next entry*/
  101.     else
  102.          return data;                  /*return first entry*/
  103. }
  104.  
  105. main ()
  106. {
  107.     int i;
  108.  
  109.     printf ("Enter a sequence of %d integers\n", N);
  110.     for (i = 0; i < N; i++)
  111.          scanf ("%d", &data[i]);
  112.     if (sort (compare, swap, sequence))
  113.          printf ("Error during sort!\n");
  114.     printf ("\n\nHere is the sorted sequence\n");
  115.     for (i = 0; i < N; i++)
  116.          printf ("%d  ", data[i]);
  117. }
  118.