home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume34 / flogger / part01 / quick_sort.c < prev    next >
C/C++ Source or Header  |  1992-12-18  |  5KB  |  203 lines
  1.  
  2. /*
  3.  
  4. NAME
  5.   quicksort, or partition exchange sort
  6.  
  7. DESCRIPTION
  8.  
  9.   Sort by partitioning, then sort the partitions, and so on.
  10.  
  11. AUTHORSHIP
  12.  
  13.   C. A. R. Hoare.
  14.   This particular implementation is taken from K&R2.
  15.  
  16. REFERENCES
  17.  
  18.   Hoare, Comp. J. 5, 1962
  19.   Knuth, Vol 3, page 114ff
  20.   Kernighan & Ritchie The C Programming Language, Revised Edition, pg 87
  21.   Standish, Data Structure Techniques pg 23-27
  22.   Sedgewick, Implementing Quicksort Programs CACM 21:10 October 1978
  23.  
  24. COMPLEXITY
  25.  
  26.   Best case O(n log n)
  27.   Worse case O(n^2)
  28.   Recursive.
  29.  
  30. PORTABILITY PROBLEMS
  31.  
  32.   Same problems as with merge_sort.
  33.  
  34. COPYRIGHT
  35.  
  36.   Copyright 1992 Michael Lee.
  37.  
  38.   (1) Permission to use, copy, distribute, and make changes is granted
  39.   providing that (a) that you do so without charging anyone a fee and
  40.   (b) this copyright notice must be included verbatim in all copies and 
  41.   distributions.  
  42.  
  43.   (2) There is no warranty for this program, to the extent permitted by
  44.   applicable law.  This program is provided "AS IS" without warranty of
  45.   any kind, either expressed or implied, including, but not limited to,
  46.   the implied warranties of merchantability and fitness for a particular 
  47.   purpose.  The entire risk as to the quality and performance of this 
  48.   program is with the user.  Should this program prove defective, the 
  49.   user assumes the cost of all necessary servicing, repair or correction.
  50.  
  51.   (3) In no event unless required by applicable law will the copyright
  52.   holder be liable to the user for damages, including any general,
  53.   special, incidental or consequential damages arising out of the use
  54.   or inability to use this program (including but not limited to loss of
  55.   data or data being rendered inaccurate or losses sustained by the
  56.   user or third parties or a failure of this program to operate with any
  57.   other programs), even if such holder or third party has been advised
  58.   of the possibility of such damages.
  59.  
  60.   (4) Object code produced by a compiler from this code may be 
  61.   incorporated into commercial products without being subject to 
  62.   restrictions (1)(a) or (1)(b).
  63.  
  64. */
  65.  
  66. #include <stdio.h>
  67. #include <malloc.h>
  68. #include <memory.h>
  69. #include <string.h>
  70. #include <assert.h>
  71.  
  72. #include "sorting.h"
  73.  
  74. static char * copy_buffer = NULL;
  75.  
  76. static int quick_sortn();
  77. static int quick_sort4();
  78. static int quick_sort8();
  79.  
  80. int quick_sort(base, nelem, width, cmpr_func)
  81.   char * base;
  82.   int nelem;
  83.   int width;
  84.   int (*cmpr_func)();
  85. {
  86.   copy_buffer = malloc(width); 
  87.   assert(copy_buffer != NULL);
  88.  
  89.   if (width == sizeof(chunk4) && (long) base % sizeof(chunk4) == 0) 
  90.     quick_sort4((chunk4 *) base, cmpr_func, 0, nelem-1);
  91.   else if (width == sizeof(chunk8) && (long) base % sizeof(chunk8) == 0) 
  92.     quick_sort8((chunk8 *) base, cmpr_func, 0, nelem-1);
  93.   else 
  94.     quick_sortn(base, width, cmpr_func, 0, nelem-1);
  95.  
  96.   free(copy_buffer);
  97.   copy_buffer = NULL;
  98. }
  99.  
  100.  
  101. static quick_sortn(base, width, cmpr_func, left, right)
  102.   char * base;
  103.   int width;
  104.   int (*cmpr_func)();
  105.   int left, right;
  106. {
  107.   int i, last;
  108.   int half = (left+right)/2;
  109.  
  110.   if (left >= right) return;
  111.  
  112.   memcpy(copy_buffer, base+width*left, width);
  113.   memcpy(base+width*left, base+width*half, width);
  114.   memcpy(base+width*half, copy_buffer, width);
  115.  
  116.   last = left;
  117.   for (i = left + 1; i <= right; i++)
  118.     if ((*cmpr_func)(base+width*i, base+width*left) < 0)
  119.     {
  120.       last ++;
  121.       if (last == i) continue;
  122.       memcpy(copy_buffer, base+width*last, width);
  123.       memcpy(base+width*last, base+width*i, width);
  124.       memcpy(base+width*i, copy_buffer, width);
  125.     }
  126.  
  127.   memcpy(copy_buffer, base+width*left, width);
  128.   memcpy(base+width*left, base+width*last, width);
  129.   memcpy(base+width*last, copy_buffer, width);
  130.  
  131.   quick_sortn(base, width, cmpr_func, left, last-1);
  132.   quick_sortn(base, width, cmpr_func, last+1, right);
  133. }
  134.  
  135.  
  136. static quick_sort4(base, cmpr_func, left, right)
  137.   chunk4 * base;
  138.   int (*cmpr_func)();
  139.   int left, right;
  140. {
  141.   int i, last; 
  142.   chunk4 temp;
  143.  
  144.   if (left >= right) return;
  145.  
  146.   temp = base[left];
  147.   base[left] = base[(left+right)/2];
  148.   base[(left+right)/2] = temp;
  149.  
  150.   last = left;
  151.   for (i = left + 1; i <= right; i++)
  152.     if ((*cmpr_func)(&base[i], &base[left]) < 0)
  153.     {
  154.       last ++;
  155.       if (last == i) continue;
  156.       temp = base[last];
  157.       base[last] = base[i];
  158.       base[i] = temp;
  159.     }
  160.  
  161.   temp = base[left];
  162.   base[left] = base[last];
  163.   base[last] = temp;
  164.  
  165.   quick_sort4(base, cmpr_func, left, last-1);
  166.   quick_sort4(base, cmpr_func, last+1, right);
  167. }
  168.  
  169.  
  170. static quick_sort8(base, cmpr_func, left, right)
  171.   chunk8 * base;
  172.   int (*cmpr_func)();
  173.   int left, right;
  174. {
  175.   int i, last; 
  176.   chunk8 temp;
  177.  
  178.   if (left >= right) return;
  179.  
  180.   temp = base[left];
  181.   base[left] = base[(left+right)/2];
  182.   base[(left+right)/2] = temp;
  183.  
  184.   last = left;
  185.   for (i = left + 1; i <= right; i++)
  186.     if ((*cmpr_func)(&base[i], &base[left]) < 0)
  187.     {
  188.       last ++;
  189.       if (last == i) continue;
  190.       temp = base[last];
  191.       base[last] = base[i];
  192.       base[i] = temp;
  193.     }
  194.  
  195.   temp = base[left];
  196.   base[left] = base[last];
  197.   base[last] = temp;
  198.  
  199.   quick_sort8(base, cmpr_func, left, last-1);
  200.   quick_sort8(base, cmpr_func, last+1, right);
  201. }
  202.  
  203.