home *** CD-ROM | disk | FTP | other *** search
/ BCI NET / BCI NET Dec 94.iso / archives / programming / misc / aprof334.lha / AProf334 / demo / qsort1.c next >
Encoding:
C/C++ Source or Header  |  1994-08-04  |  1.3 KB  |  97 lines
  1. /* qsort1.c
  2.  *
  3.  * AProf example code
  4.  *
  5.  */
  6.  
  7.  
  8. /* Size of sort array */
  9. #define ASIZE  50
  10.  
  11. /* Definition of sort array */
  12. int array[ ASIZE ];
  13.  
  14.  
  15.  
  16. /* swap
  17.  *
  18.  * swap the values at index positions x1 and x2 in array
  19.  */
  20. void swap( int x1, int x2 )
  21. {
  22.    int tmp;
  23.  
  24.    tmp         = array[ x1 ];
  25.    array[ x1 ] = array[ x2 ];
  26.    array[ x2 ] = tmp;
  27. }
  28.  
  29.  
  30.  
  31. /* getPivot
  32.  *
  33.  * Return the index of the pivot element in range x1, x2
  34.  */
  35. int getPivot( int x1, int x2 )
  36. {
  37.    return x1;
  38. }
  39.  
  40.  
  41.  
  42. /* doSplit
  43.  * 
  44.  * Gnah...
  45.  */
  46. int doSplit( int x1, int x2, int pivot )
  47. {
  48.    do {
  49.       while ( array[x1] < array[pivot] )
  50.          x1++;
  51.       swap( x1, pivot );
  52.       pivot = x1;
  53.  
  54.       while ( array[x2] > array[pivot] )
  55.          x2--;
  56.       swap( x2, pivot );
  57.       pivot = x2;
  58.    } while ( x1 < pivot || x2 > pivot );
  59.  
  60.    return pivot;
  61. }
  62.  
  63.  
  64.  
  65. /* theQsort
  66.  *
  67.  * Quicksorts array between indices x1, x2
  68.  */
  69. void theQsort( int x1, int x2 )
  70. {
  71.    if ( x1 < x2 )
  72.    {
  73.       /* pivot element */
  74.       int pivot = getPivot( x1, x2 );
  75.  
  76.       pivot = doSplit( x1, x2, pivot );
  77.  
  78.       theQsort( x1, pivot-1 );
  79.       theQsort( pivot+1, x2 );
  80.    }
  81. }
  82.  
  83.  
  84.  
  85. int main( void )
  86. {
  87.    int i;
  88.  
  89.    /* Initialize sort array */
  90.    for ( i = 0 ; i < ASIZE ; i++ )
  91.       array[i] = rand();
  92.  
  93.    theQsort( 0, ASIZE-1 );
  94.  
  95.    exit( 0 );
  96. }   
  97.