/* --------------------------------------------------------------------------- **
   Figures  21.15:  Getting ready to sort: quicksort().
            21.17:  The quick() function performs the recursion.
            21.26:  The partition() function.
            12.8 :  The swap() function.
   --------------------------------------------------------------------------- */
#include <float.h>                          /* For the sentinel value, FLT_MAX */

/* Functions called directly or indirectly by quicksort() -------------------- */
void    quick( float* first, float* last ); 
float*  partition( float* first, float* last );
void    swap( float* fp1, float* fp2 ); 

/* --------------------------------------------------------------------------- */
/* Sort n values starting at first by quicksort algorithm -------------------- */
/* Allocation array must have one extra slot on the end for sentinel. -------- */

void
quicksort( data_pack sort )  
{   
    float* sentinel = sort.data + sort.n;   /* Create off-board sentinel... */ 
   
    *sentinel = FLT_MAX;                    /* with big value to stop loops. */
    quick( sort.data, sentinel - 1 );       /* Call quick() with pointers to */
}                                           /* beginning and end of data. */

/* -------------------------------------------------------------------------- 
** Swap the values of two array slots, given pointers to those slots.   
*/
void
swap( float* left, float* right )  
{   float  swapper;
    swapper=*left;  *left=*right;  *right=swapper;
}

/* --------------------------------------------------------------------------- 
** Recursively sort the values between (and including) first and last.
*/
void 
quick( float* first, float* last )
{   
    int how_many = last - first + 1;           /* Number of items left to sort */
    float* split;

    /* Base cases: ----------------------------------------------------------- */
    if (how_many < 2){}        /* Nothing to do for 0 or 1 items left. ------- */    
    else if (how_many == 2) {  /* Stop recursive descent and ----------------- */
        if (*last < *first)  swap( last, first );     /* swap if not in order. */
    }

    /* Recursive calls: how_many > 2 ----------------------------------------- */
    else { 
        split = partition( first, last );  /* Split into two areas. */
        quick( first, split-1 );           /* Sort left portion (small items)  */
        quick( split+1, last );            /* Sort right portion (large items) */
    }
 }

/* --------------------------------------------------------------------------- 
** Choose a pivot data value.  Put smaller items on left, larger ones on right.      
*/
float* 
partition( float* first, float* last )
{ 
    float* lester = first;                      /* Data scanners */
    float* rose = last + 1;
    float* mid = first + (last - first) / 2;    /* Use mid element as pivot. */
    float pivot;
    float* split;                               /* Location of split point. */
    
    /* Move pivot element to front end of array - copy remains in 'pivot'. */
    pivot = *mid; *mid = *first; *first = pivot;
    /* printf( " pivot= %g in slot %li\n", pivot, mid-first); // For debugging. */

    for(;;) {  
        while (*(++lester) <= pivot);   /* scan from left-to-right */
        while (*(--rose) > pivot);      /* scan from right-to-left */
        if (lester >= rose) break;      /* break if scanners meet */
        swap ( rose, lester );          /* otherwise swap items */
    }

    split = rose ;
    *first = *split,  *split = pivot;    /* swap.  (pivot == *first ) */
    return split ;
}