home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / snippet.exe / RG_QSORT.C2 < prev    next >
Encoding:
Text File  |  1991-12-23  |  1.1 KB  |  51 lines
  1. /*
  2. ** quicksort.c -- quicksort integer array
  3. **
  4. ** public domain by Raymond Gardner     12/91
  5. */
  6.  
  7. static void swap(int *a, int *b)
  8. {
  9.       register int t;
  10.  
  11.       t = *a;
  12.       *a = *b;
  13.       *b = t;
  14. }
  15.  
  16. void quicksort(int v[], unsigned n)
  17. {
  18.       unsigned i, j, ln, rn;
  19.  
  20.       while ( n > 1 )
  21.       {
  22.             swap(&v[0], &v[n/2]);
  23.             for ( i = 0, j = n; ; )
  24.             {
  25.                   do
  26.                         --j;
  27.                   while ( v[j] > v[0] );
  28.                   do
  29.                         ++i;
  30.                   while ( i < j && v[i] < v[0] );
  31.                   if ( i >= j )
  32.                         break;
  33.                   swap(&v[i], &v[j]);
  34.             }
  35.             swap(&v[j], &v[0]);
  36.             ln = j;
  37.             rn = n - ++j;
  38.             if ( ln < rn )
  39.             {
  40.                   quicksort(v, ln);
  41.                   v += j;
  42.                   n = rn;
  43.             }
  44.             else
  45.             {
  46.                   quicksort(v + j, rn);
  47.                   n = ln;
  48.             }
  49.       }
  50. }
  51.