home *** CD-ROM | disk | FTP | other *** search
/ ftp.wwiv.com / ftp.wwiv.com.zip / ftp.wwiv.com / pub / MISC / SQDEV200.ZIP / SRC / QKSORT.C < prev    next >
C/C++ Source or Header  |  1994-05-23  |  3KB  |  74 lines
  1. /***************************************************************************
  2.  *                                                                         *
  3.  *  Squish Developers Kit Source, Version 2.00                             *
  4.  *  Copyright 1989-1994 by SCI Communications.  All rights reserved.       *
  5.  *                                                                         *
  6.  *  USE OF THIS FILE IS SUBJECT TO THE RESTRICTIONS CONTAINED IN THE       *
  7.  *  SQUISH DEVELOPERS KIT LICENSING AGREEMENT IN SQDEV.PRN.  IF YOU DO NOT *
  8.  *  FIND THE TEXT OF THIS AGREEMENT IN THE AFOREMENTIONED FILE, OR IF YOU  *
  9.  *  DO NOT HAVE THIS FILE, YOU SHOULD IMMEDIATELY CONTACT THE AUTHOR AT    *
  10.  *  ONE OF THE ADDRESSES LISTED BELOW.  IN NO EVENT SHOULD YOU PROCEED TO  *
  11.  *  USE THIS FILE WITHOUT HAVING ACCEPTED THE TERMS OF THE SQUISH          *
  12.  *  DEVELOPERS KIT LICENSING AGREEMENT, OR SUCH OTHER AGREEMENT AS YOU ARE *
  13.  *  ABLE TO REACH WITH THE AUTHOR.                                         *
  14.  *                                                                         *
  15.  *  You can contact the author at one of the address listed below:         *
  16.  *                                                                         *
  17.  *  Scott Dudley       FidoNet     1:249/106                               *
  18.  *  777 Downing St.    Internet    sjd@f106.n249.z1.fidonet.org            *
  19.  *  Kingston, Ont.     CompuServe  >INTERNET:sjd@f106.n249.z1.fidonet.org  *
  20.  *  Canada  K7M 5N3    BBS         1-613-634-3058, V.32bis                 *
  21.  *                                                                         *
  22.  ***************************************************************************/
  23.  
  24. /*# name=Integer quicksort routine.
  25.     credit=Thanks to Thomas Plum and _Reliable_Data_Structure_In_C_
  26.     credit=for this routine.
  27. */
  28.  
  29. #include <stdio.h>
  30. #include "prog.h"
  31.  
  32. #define NUM sizeof(array)/sizeof(array[0])
  33. #define SWAP(a,b,s) s=a; a=b; b=s;
  34.  
  35. static void _fast iqksort(int *p_lo,int *p_hi);
  36.  
  37. void _fast qksort(int a[],size_t n)
  38. {
  39.   if (n > 1)
  40.     iqksort(a,&a[n-1]);
  41. }
  42.  
  43.  
  44.  
  45. static void _fast iqksort(int *p_lo,int *p_hi)
  46. {
  47.   int  *p_mid=p_lo+(((int)(p_hi-p_lo))/2),
  48.        *p_i,
  49.        *p_lastlo,
  50.        tmp;
  51.  
  52.   SWAP(*p_lo,*p_mid,tmp);
  53.  
  54.   p_lastlo=p_lo;
  55.  
  56.   for (p_i=p_lo+1;p_i <= p_hi;++p_i)
  57.   {
  58.     if (*p_lo > *p_i)
  59.     {
  60.       ++p_lastlo;
  61.       SWAP(*p_lastlo,*p_i,tmp);
  62.     }
  63.   }
  64.  
  65.   SWAP(*p_lo,*p_lastlo,tmp);
  66.  
  67.   if (p_lo < p_lastlo && p_lo < p_lastlo-1)
  68.     iqksort(p_lo,p_lastlo-1);
  69.  
  70.   if (p_lastlo+1 < p_hi)
  71.     iqksort(p_lastlo+1,p_hi);
  72. }
  73.  
  74.