home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1994 #1 / monster.zip / monster / PROG_C / SNIP9404.ZIP / RG_QSORT.C2 < prev    next >
Text File  |  1994-04-03  |  1KB  |  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.