home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / pcmagazi / 1988 / 15 / qwiksort.c < prev    next >
C/C++ Source or Header  |  1988-05-24  |  4KB  |  104 lines
  1. quicksort(int left, int right)
  2. {
  3.      int i;
  4.  
  5.      if (right > left)
  6.      {
  7.           i = partition(left, right);
  8.           quicksort(left, i-1);
  9.           quicksort(i+1, right);
  10.      }
  11. }
  12.  
  13. Figure 3.  The Quicksort algorithm.
  14.  
  15. [figure ends]
  16.  
  17. [figure]
  18.  
  19. /*
  20.     QWIKSORT.C  Simple implementation of Quicksort
  21.                 in C, sorts an array of numbers.
  22.  
  23.     Ray Duncan * PC Magazine May 1988
  24. */
  25.  
  26. #include <stdio.h>
  27. #include <stdlib.h>
  28. #define N_ITEMS     25              /* size of array */
  29.  
  30. static int items[N_ITEMS];          /* numbers to be sorted */
  31. void quicksort(int, int);           /* function prototype */
  32.  
  33. main(int argc, char *argv[])
  34. {
  35.     int i, j;                       /* some scratch variables */
  36.     char buffer[80];                /* some scratch space
  37.                                        for keyboard input */
  38.     while(1)                        /* get numbers & sort them */
  39.     {
  40.         puts("\nEnter numbers to be sorted...");
  41.         i = 0;                      /* initialize array index */
  42.         while(i < N_ITEMS)          /* enforce maximum entries */
  43.         {
  44.             printf("%2d: ", i+1);   /* prompt user */
  45.                                     /* read the keyboard */
  46.             gets(buffer);
  47.                                     /* last entry if empty line */
  48.             if(buffer[0] == 0 ) break;
  49.                                     /* convert ASCII number to
  50.                                        binary and save it */
  51.             items[i] = atoi(buffer);
  52.             i++;                    /* bump array pointer */
  53.         }
  54.         if(i==0) exit(0);           /* if no numbers exit */
  55.         quicksort(0, i-1);          /* sort the numbers */
  56.         puts("\nHere are the sorted numbers...");
  57.         j = 0;                      /* initialize array pointer */
  58.         while (j < i)               /* display sorted numbers */
  59.         {
  60.             printf("%2d: %d\n", j+1, items[j]);
  61.             j++;                    /* bump array pointer */
  62.         }
  63.     }
  64. }
  65.  
  66.  
  67. /*
  68.     Quicksorts an array of integers, recursing to sort subsets
  69.     of the array.  Called with the index to the left and right
  70.     members of the array to be sorted.
  71. */
  72.  
  73. void quicksort(int left, int right)
  74. {
  75.     int i, j, t;                    /* some scratch variables */
  76.  
  77.     if(right > left)                /* skip unnecessary calls */
  78.     {
  79.         i = left-1; j = right;      /* initialize scan pointers */
  80.                                     /* partition array on value */
  81.                                     /* of the rightmost item */
  82.         do {
  83.                                     /* scan right for item >=  */
  84.                                     /* than partitioning value */
  85.             do i++;
  86.                 while(items[i] < items[right]);
  87.                                     /* scan left for item <=   */
  88.                                     /* than partitioning value */
  89.             do j--;
  90.                 while(items[j] > items[right] && j > 0);
  91.             t = items[i];           /* interchange the items */
  92.             items[i] = items[j];
  93.             items[j] = t;
  94.         } while(j > i);             /* do until pointers cross */
  95.  
  96.         items[j] = items[i];        /* undo the last swap and */
  97.         items[i] = items[right];    /* put the partitioning */
  98.         items[right] = t;           /* element into position */
  99.         quicksort(left, i-1);       /* sort items to left of */
  100.                                     /* partitioning element */
  101.         quicksort(i+1, right);      /* sort items to right of */
  102.     }                               /* partitioning element */
  103. }
  104.