home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / avl / ssort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-12-31  |  2.7 KB  |  104 lines
  1. /****************************************************************************
  2. *
  3. *                    Copyright (C) 1991 Kendall Bennett.
  4. *                            All rights reserved.
  5. *
  6. * Filename:        $RCSfile: ssort.c $
  7. * Version:        $Revision: 1.3 $
  8. *
  9. * Language:        ANSI C
  10. * Environment:    any
  11. *
  12. * Description:    Shell sort for array's and array's of pointers.
  13. *
  14. * $Id: ssort.c 1.3 91/12/31 19:40:39 kjb Exp $
  15. *
  16. * Revision History:
  17. * -----------------
  18. *
  19. * $Log:    ssort.c $
  20. * Revision 1.3  91/12/31  19:40:39  kjb
  21. * Modified include file directories
  22. * 
  23. * Revision 1.2  91/09/02  11:21:52  ROOT_DOS
  24. * Minor cosmetic change.
  25. * 
  26. * Revision 1.1  91/08/16  13:16:25  ROOT_DOS
  27. * Initial revision
  28. * 
  29. ****************************************************************************/
  30.  
  31. #include "debug.h"
  32. #include "ssort.h"
  33.  
  34. PUBLIC void ssort(char *base,int nel,int elsize,int (*cmp)(void *,void*) )
  35. /****************************************************************************
  36. *
  37. * Function:        ssort
  38. * Parameters:    base    - Pointer to base of array to sort
  39. *                nel        - Number of elements to sort
  40. *                elsize    - Size of elements in bytes
  41. *                cmp        - Comparision routine for elements
  42. *
  43. * Description:    Sorts the array using the standard "Shell Sort". The shell
  44. *                sort is simple and very efficient if we are sorting only
  45. *                small numbers of elements (say < 5000 elements).
  46. *
  47. ****************************************************************************/
  48. {
  49.     int        i,j;
  50.     int        gap,k,tmp;
  51.     char    *p1,*p2;
  52.  
  53.     for (gap = 1; gap <= nel; gap = 3*gap + 1);
  54.  
  55.     for(gap /= 3; gap > 0; gap /= 3)
  56.         for(i = gap; i < nel; i++)
  57.             for(j = i-gap; j >= 0; j -= gap) {
  58.                 p1 = base + (j * elsize);
  59.                 p2 = base + ((j+gap) * elsize);
  60.  
  61.                 if ((*cmp)(p1,p2) <= 0)        /* Compare the two elements    */
  62.                     break;
  63.  
  64.                 for (k = elsize; --k >= 0;) { /* Swap two elements, one    */
  65.                     tmp = *p1;
  66.                     *p1++ = *p2;
  67.                     *p2++ = tmp;
  68.                     }
  69.                 }
  70. }
  71.  
  72. PUBLIC void assort(void **base,int nel,int elsize,int (*cmp)(void*,void*) )
  73. /****************************************************************************
  74. *
  75. * Function:        assort
  76. * Parameters:    base    - Pointer to base of array to sort
  77. *                nel        - Number of elements to sort
  78. *                cmp        - Comparision routine for elements
  79. *
  80. * Description:    Same as ssort(), except that it sorts an array of pointer
  81. *                size objects.
  82. *
  83. ****************************************************************************/
  84. {
  85.     int        i,j,gap;
  86.     void    *tmp, **p1, **p2;
  87.  
  88.     for (gap = 1; gap <= nel; gap = 3*gap + 1);
  89.  
  90.     for(gap /= 3; gap > 0; gap /= 3)
  91.         for(i = gap; i < nel; i++)
  92.             for(j = i-gap; j >= 0; j -= gap) {
  93.                 p1 = base + j;
  94.                 p2 = base + j + gap;
  95.  
  96.                 if ((*cmp)(p1,p2) <= 0)        /* Compare the two elements    */
  97.                     break;
  98.  
  99.                 tmp = *p1;
  100.                 *p1 = *p2;
  101.                 *p2 = tmp;
  102.                 }
  103. }
  104.