home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / mslang / qsort / qsort.c
Encoding:
C/C++ Source or Header  |  1994-06-15  |  1.5 KB  |  99 lines
  1. /*
  2. //    An implementation of the Quicksort algorithm written specifically
  3. //    for sorting arrays of C integer data types
  4. */
  5. #include    <stdio.h>
  6. #include    <stdlib.h>
  7. #include    <time.h>
  8. #include    <sys/times.h>
  9.  
  10. #define    X    5
  11. #define    Y    100000
  12.  
  13. static    int    ia[X][Y] ;
  14.  
  15. /*
  16. //    Use of macro preferred to function - more code but faster !!
  17. */
  18. #define    SWAP(A,I,J)    { int temp=A[I]; A[I]=A[J]; A[J]=temp; }
  19.  
  20. static    void
  21. rqs (int *ip, int lo, int hi)
  22. {
  23.     int    last ;
  24.     int    i ;
  25.  
  26.     if (lo < hi)
  27.     {
  28.         SWAP (ip, lo, hi) ;
  29.  
  30.         last = lo ;
  31.  
  32.         for (i = lo + 1 ; i <= hi ; ++i)
  33.             if (ip[i] < ip[lo])
  34.             {
  35.                 ++last ;
  36.                 SWAP (ip, last, i) ;
  37.             }
  38.  
  39.         SWAP (ip, lo, last) ;
  40.  
  41.         rqs (ip, lo, last - 1) ;
  42.         rqs (ip, last + 1, hi) ;
  43.     }
  44. }
  45.  
  46. static    void
  47. qsort (int *ip, int nel)
  48. {
  49.     rqs (ip, 0, nel - 1) ;
  50. }
  51.  
  52. main ()
  53. {
  54.     struct    tms    start ;
  55.     struct    tms    finish ;
  56.     int    i ;
  57.     int    j ;
  58.  
  59.     /*
  60.     //    Set seed for srand48
  61.     */
  62.     srand48 ((long)getpid()) ;
  63.  
  64.     /*
  65.     //    Load random data
  66.     */
  67.     for (i = 0 ; i < X ; ++i)
  68.         for (j = 0 ; j < Y ; ++j)
  69.             ia[i][j] = lrand48 () ;
  70.  
  71.     /*
  72.     //    Get CPU time prior to sorting
  73.     */
  74.     times (&start) ;
  75.  
  76.     /*
  77.     //    Sort the arrays
  78.     */
  79.     for (i = 0 ; i < X ; ++i)
  80.         qsort (ia[i], Y) ;
  81.  
  82.     /*
  83.     //    Get CPU time after sorting
  84.     */
  85.     times (&finish) ;
  86.  
  87.     printf ("%.4f seconds to sort\n"
  88.         , (double)(finish.tms_utime - start.tms_utime) / CLK_TCK) ;
  89.  
  90.     /*
  91.     //    Show results on stdout
  92.     for (i = 0 ; i < X ; ++i)
  93.         for (j = 0 ; j < Y ; ++j)
  94.             printf ("%d\n", ia[i][j]) ;
  95.     */
  96.  
  97.     return 0 ;
  98. }
  99.