home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / avl / ssorttst.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-12-31  |  7.6 KB  |  290 lines
  1. /****************************************************************************
  2. *
  3. *                    Copyright (C) 1991 Kendall Bennett.
  4. *                            All rights reserved.
  5. *
  6. * Filename:        $RCSfile$
  7. * Version:        $Revision$
  8. *
  9. * Language:        ANSI C
  10. * Environment:    any
  11. *
  12. * Description:    Program to test the shell sort routines, and to compare the
  13. *                running time to that of quicksort.
  14. *
  15. * $Id$
  16. *
  17. * Revision History:
  18. * -----------------
  19. *
  20. * $Log$
  21. ****************************************************************************/
  22.  
  23. #include <stdio.h>
  24. #include <stdlib.h>
  25. #include <string.h>
  26. #include <dir.h>
  27. #include <time.h>
  28. #include "debug.h"
  29. #include "getopt.h"
  30. #include "mgraph.h"
  31. #include "ztimer.h"
  32.  
  33. /*------------------------- Global variables ------------------------------*/
  34.  
  35. char    *rcsid = "$Id$";
  36.  
  37. char    *version = "1.0b";            /* Version string (eg: 5.20b)        */
  38. char    nameofus[MAXFILE];            /* Name of program (no path)        */
  39. char    pathtous[MAXDIR];            /* Pathname to our program.            */
  40. char    *progname;                    /* Descriptive name of program        */
  41.  
  42. int        N = 0;
  43. bool    interactive = false;
  44. bool    use_qsort = false;
  45.  
  46. Option    optarr[] =
  47.    {{'g',OPT_SWITCH,&interactive,"Graphically analyse algorithm performance"},
  48.     {'q',OPT_SWITCH,&use_qsort,"Sort using standard quicksort"}};
  49.  
  50. /*-------------------------- Implementation -------------------------------*/
  51.  
  52. void init(char *argv0,char *prognam)
  53. /****************************************************************************
  54. *                                                                              *
  55. * Function:        init                                                        *
  56. * Parameters:    char    *argv0        - The argv[0] array entry.                *
  57. *                char    *prognam    - Descriptive name of program.            *
  58. *                                                                           *
  59. * Description:    Init takes the pathname to our program as a parameter        *
  60. *                (found in argv[0]) and use this to set up three global        *
  61. *                variables:                                                  *
  62. *                                                                           *
  63. *                pathtous    - Contains the pathname to our program          *
  64. *                nameofus    - Contains the name of the program (without the *
  65. *                              .EXE extension)                               *
  66. *                                                                            *
  67. *                We also set up the global variable progname to point to     *
  68. *                the static string passed to init for all to use.            *
  69. *                                                                           *
  70. ****************************************************************************/
  71. {
  72.     char    *p,i;
  73.  
  74.     /* Obtain the path to our program from pathname - note that we only
  75.      * do this for MS DOS machines. Under UNIX this is not available
  76.      * since argv[0] holds the name of the program without the path
  77.      * attached. We set pathtous to an empty string under UNIX, and
  78.      * nameofus to the value of argv[0].
  79.      */
  80.  
  81. MS(    p = strrchr(argv0,'\\') + 1;
  82.     i = *p;
  83.     *p = '\0';
  84.     strcpy(pathtous,argv0);
  85.     *p = i;
  86.  
  87.     /* Obtain the name of our program from pathname */
  88.  
  89.     i = 0;
  90.     while (*p != '.')
  91.         nameofus[i++] = *p++;
  92.     nameofus[i] = '\0';)
  93.  
  94. UX(    strcpy(nameofus,argv0);
  95.     pathtous[0] = '\0';)
  96.  
  97.     progname = prognam;
  98. }
  99.  
  100. void banner(void)
  101. /****************************************************************************
  102. *
  103. * Function:     banner
  104. *
  105. * Description:  Prints the program's banner to the standard output
  106. *                Under Borland C++, we insert the compilation date into
  107. *                the banner using the __DATE__ macro. This does not
  108. *                seem to be available under some UNIX systems, so for UNIX
  109. *                we do not insert the date into the banner.
  110. *
  111. ****************************************************************************/
  112. {
  113.     MS(printf("%s  Version %s - %s  Copyright (C) 1991 Kendall Bennett\n\n"
  114.         ,progname,version,__DATE__);)
  115.     UX(printf("%s  Version %s  Copyright (C) 1991 Kendall Bennett\n\n"
  116.         ,progname,version);)
  117. }
  118.  
  119. void help(void)
  120. /****************************************************************************
  121. *
  122. * Function:     help
  123. *
  124. * Description:  Help provides usage information about our program if the
  125. *               options do make any sense or the help switch was specified
  126. *                on the command line.
  127. *
  128. ****************************************************************************/
  129. {
  130.     banner();
  131.     printf("Usage: %s [options] <number of elements>\n\n",nameofus);
  132.     printf("Options are:\n");
  133.     print_desc(NUM_OPT(optarr),optarr);
  134.     exit(1);
  135. }
  136.  
  137. int do_params(char *param,int num)
  138. /****************************************************************************
  139. *
  140. * Function:        do_params
  141. * Parameters:    param    - String representing parameter
  142. *                num        - Parameter number
  143. * Returns:        ALLDONE on success, or INVALID on error.
  144. *
  145. * Description:    Handles the parameters on the command line, interspersed
  146. *                between command line options.
  147. *
  148. ****************************************************************************/
  149. {
  150.     switch (num) {
  151.         case 1:
  152.             if((N = atoi(param)) <= 0) {
  153.                 printf("Invalid number elements specified\n");
  154.                 exit(1);
  155.                 }
  156.             break;
  157.         default:
  158.             return INVALID;
  159.         }
  160.     return ALLDONE;
  161. }
  162.  
  163. PUBLIC void ssort(char *base,int nel,int elsize,int (*cmp)(const void*,const void*) )
  164. /****************************************************************************
  165. *
  166. * Function:        ssort
  167. * Parameters:    base    - Pointer to base of array to sort
  168. *                nel        - Number of elements to sort
  169. *                elsize    - Size of elements in bytes
  170. *                cmp        - Comparision routine for elements
  171. *
  172. * Description:    Sorts the array using the standard "Shell Sort". The shell
  173. *                sort is simple and very efficient if we are sorting only
  174. *                small numbers of elements (say < 5000 elements).
  175. *
  176. ****************************************************************************/
  177. {
  178.     int        i,j;
  179.     int        gap,k,tmp;
  180.     char    *p1,*p2;
  181.  
  182.     for (gap = 1; gap <= nel; gap = 3*gap + 1);
  183.  
  184.     for(gap /= 3; gap > 0; gap /= 3)
  185.         for(i = gap; i < nel; i++)
  186.             for(j = i-gap; j >= 0; j -= gap) {
  187.                 p1 = base + (j * elsize);
  188.                 p2 = base + ((j+gap) * elsize);
  189.  
  190.                 if ((*cmp)(p1,p2) <= 0)        /* Compare the two elements    */
  191.                     break;
  192.  
  193.                 for (k = elsize; --k >= 0;) { /* Swap two elements, one    */
  194.                     tmp = *p1;
  195.                     *p1++ = *p2;
  196.                     *p2++ = tmp;
  197.                     }
  198.                 }
  199. }
  200.  
  201. int mycmp(const void *e1,const void *e2)
  202. {
  203.     return ((*(int*)e1) - (*(int*)e2));
  204. }
  205.  
  206. int main(int argc,char *argv[])
  207. {
  208.     int        i,*array;
  209.     int        driver,mode;
  210.     point    p;
  211.  
  212.     init(argv[0],"Sort Test");
  213.  
  214.     switch (getargs(argc,argv,NUM_OPT(optarr),optarr,do_params)) {
  215.         case INVALID:
  216.             printf("Invalid option\n");
  217.             exit(1);
  218.             break;
  219.         case HELP:
  220.             help();
  221.         }
  222.  
  223.     if (N == 0)
  224.         help();
  225.  
  226.     /* Allocate space for array on the heap */
  227.  
  228.     if ((array = malloc(N * sizeof(int))) == NULL) {
  229.         printf("Not enough memory to allocate array\n");
  230.         exit(1);
  231.         }
  232.  
  233.     /* Generate N random integers between 0 and 350 */
  234.  
  235.     srand(44378);
  236.  
  237.     if (interactive) {
  238.         for (i = 0; i < N; i++)
  239.             array[i] = random(350);
  240.         }
  241.     else {
  242.         for (i = 0; i < N; i++)
  243.             array[i] = rand();
  244.         }
  245.  
  246.     if (interactive) {
  247.         driver = grDETECT;
  248.         MGL_init(&driver,&mode,"",true);
  249.  
  250.         MGL_setMarkerColor(YELLOW);
  251.         MGL_setMarkerStyle(MARKER_SQUARE);
  252.         MGL_setMarkerSize(2);
  253.  
  254.         for (i = 0; i < N; i++) {
  255.             p.x = i;
  256.             p.y = array[i];
  257.             MGL_marker(p);
  258.             }
  259.         }
  260.  
  261.     /* Sort the integers */
  262.  
  263.     if (use_qsort) {
  264.         LZTimerOn();
  265.         qsort(array,N,sizeof(int),mycmp);
  266.         LZTimerOff();
  267.         }
  268.     else {
  269.         LZTimerOn();
  270.         ssort(array,N,sizeof(int),mycmp);
  271.         LZTimerOff();
  272.         }
  273.  
  274.     if (interactive) {
  275.         MGL_setMarkerColor(LIGHTRED);
  276.  
  277.         for (i = 0; i < N; i++) {
  278.             p.x = i;
  279.             p.y = array[i];
  280.             MGL_marker(p);
  281.             }
  282.         getch();
  283.         MGL_exit();
  284.         }
  285.  
  286.     LZTimerReport();
  287.  
  288.     return 0;
  289. }
  290.