home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Libraries / SortLib 2.0 / documentation / README < prev   
Encoding:
Text File  |  1994-11-30  |  5.1 KB  |  135 lines  |  [TEXT/MPS ]
  1.  
  2. Sort Library, Version 2.0, Copyright (c) 1990-1994 Ari Halberstadt
  3.  
  4. Contents:
  5.  
  6. - Description
  7. - Portability
  8. - Notes to users of THINK C
  9. - Possible Enhancements
  10. - Your suggestions
  11. - Known bugs (none)
  12. - Bibliography
  13. - My address
  14.  
  15. DESCRIPTION
  16.  
  17. This is a free implementation in C of several array sorting algorithms. A
  18. makefile for UNIX users, an MPW Makefile for the Macintosh, and project
  19. files for THINK C and CodeWarrior users (also on the Macintosh) are provided.
  20.  
  21. The purpose of this software is to provide fast and portable implementations of
  22. the most useful general purpose array sorting algorithms. While for most
  23. applications quick sort is probably sufficient, having access to the other
  24. algorithms can be a huge bonus. Never again will you have to sit down to write
  25. and debug the fastest implementation of some sorting algorithm. Since all the
  26. functions are designed to be called in the exact same way as the standard
  27. qsort, it is simple to use the algorithm of your choice. Each implementation
  28. is guaranteed to return a sorted array [for instance, if merge sort can't
  29. allocate its auxiliary array, it will call heap sort instead, which still
  30. gives a time bound of O(n*lg(n))].
  31.  
  32. The test program provided (in "sort.c") compares several implementations of
  33. array sorting algorithms. The functions compared are:
  34.  
  35.     qsort     The standard library implementation of quick sort.
  36.     qksort    My version of quick sort.
  37.     shsort    Shell sort.
  38.     hpsort    Heap sort.
  39.     mgsort    Merge sort.
  40.     insort    Insertion sort.
  41.     tqksort    Quick sort using integers.
  42.     tshsort    Shell sort using integers.
  43.     thpsort    Heap sort using integers.
  44.     tmgsort    Merge sort using integers.
  45.     tinsort    Insertion sort using integers.
  46.  
  47. Compile and run this program, and then look at the output to see how long it
  48. takes to sort things using each algorithm. Be prepared to wait a few minutes
  49. for the results. You may want to adjust the define for MAXDATA in "sort.c" to
  50. get a value which will not take too long on your machine.
  51.  
  52. The directory "outputs" contains the program's output for various machines and
  53. compilers. The directory "source" contains the source code.
  54.  
  55. PORTABILITY
  56.  
  57. I tested version 1.0 of this software using gcc on the: NeXT; VAX 11/780
  58. (UNIX, BSD4.3); and DEC System running Ultrix. I've tested version 2.0 of
  59. this software on a couple of Unix systems. I also tested version 2.0 on
  60. the Macintosh using THINK C 7.0 and CodeWarrior DR4. Though a makefile is
  61. included for MPW, I could not get the MPW C compiler to accept the file
  62. "sort.c".
  63.  
  64. The folder "unix" contains files specific to the Unix environment (like the
  65. Makefile). The folder "macintosh" contains files specific to the Macintosh
  66. environment (like a project file for users of THINK C).
  67.  
  68. You should be able to find out if this implementation of qksort is better than
  69. the version supplied with your compiler, and replace all calls to qsort with
  70. calls to qksort. For instance, qksort is 4 to 5 times faster than THINK C's
  71. qsort for random files, and many times faster for presorted files.
  72.  
  73. POSSIBLE ENHANCEMENTS
  74.  
  75. I intend to implement the main sorting algorithms for arrays. Each
  76. implementation will be done in the most efficient manner that I feel like
  77. doing. Quick sort is just about as efficient as it's likely to get; shell sort
  78. could use a better increment sequence; heap sort could be further optimized to
  79. use pointers; merge sort might be convinced to use space n/2 instead of n.
  80. External and radix sorting functions may be added.
  81.  
  82. YOUR SUGGESTIONS
  83.  
  84. If you have any ideas on how to make any of the implementations faster, or
  85. have specific knowledge of another good sorting algorithm, or have revised the
  86. programs to be faster, then please let me know. I would like to include these
  87. enhancements with the next release. Anything you do should, however, be ANSI
  88. compatible (no assembly language). I will, of course, include proper credits.
  89. If you compare this software to standard qsort using an as yet untested
  90. compiler, I'd like to add your test results to the "outputs" file (please
  91. email me a copy).
  92.  
  93. Please report any bugs. Please report any potential bugs (eg, overflow,
  94. underflow, etc). Please report problems executing with ANSI compatible
  95. compilers.
  96.  
  97. KNOWN BUGS
  98.  
  99. Several loops (for instance, for merge sort and shell sort) may cause the
  100. value of an index variable to exceed the number of items in the array. For
  101. instance, the following loop:
  102.  
  103.     size_t sz;
  104.     for (sz = 1; sz < n; sz *= 2) { ... }
  105.  
  106. will stop after sz has reached a value of  about  2*n.  This  could  cause  an
  107. overflow  problem  if n were near the maximum value for type size_t. However,
  108. since the maximum value of a variable of type size_t is typically at least
  109. 2^31,  I don't  see  much  cause for alarm: no one in the near future is
  110. likely to sort 2^30 items in memory.
  111.  
  112. BIBLIOGHRAPHY
  113.  
  114. Knuth, D. E.,  "The  Art  of  Computer  Programming.  Volume  3:  Sorting  and
  115. Searching", Addison-Wesley, 1975.
  116.  
  117. Sedgewick, Robert, "Algorithms", 2nd ed., Addison-Wesley, 1988.
  118.  
  119. MY ADDRESS
  120.  
  121. I may be reached, as of November 1994, at the following addresses:
  122.  
  123. Postal mail:
  124.  
  125.     Ari Halberstadt
  126.     9 Whittemore Road
  127.     Newton, MA 02158-2105
  128.     USA
  129.  
  130. Electronic mail:
  131.     
  132.     ari@world.std.com
  133.  
  134. Electronic mail is preferred.
  135.