/* The function sort(), with a test main().
   Input:  a list of at most MAXNUM (see below) floats typed by the
           user.  The end is detected by looking for an illegal number,
           for example, the letter 'X'.
   Output: (Generated by a 'temporary' printf inside sort) The array
           after each pass of the sorting algorithm, ending with
           the fully sorted array.
*/

#include <stdio.h>
#include <stdlib.h>
#define MAXNUM 500      /* maximum number of numbers */

int enter_and_count(float nums[]);
int maxindex(float values[], int lowindex, int numvalues);
void sort(float data[], int count);

main() {
    float numbers[MAXNUM];  /* The numbers entered by the user */
    int count;

    /* Read numbers into array, summing and counting as we go. */
    count = enter_and_count(numbers);

    sort(numbers, count);
    printf("Array sorted\n");
    return 0;
}

/* enter_and_count:
   Reads input, counting the values, stopping when scanf fails to read
   a number.  Stores the values in its argument array, nums, and
   returns a count of the number of items input.
*/
int enter_and_count(float nums[]) {
    int scan_status, count; float x;
    printf("Enter all input numbers:\n");
    count = 0;
    scan_status = scanf("%f", &x);
    while (scan_status == 1 /* scanf input OK */) {
        if (count >= MAXNUM) {           /* Too many numbers? */
            printf("ERROR: Too many input numbers\n");
            exit(EXIT_FAILURE);
        }
        nums[count] = x;                 /* Store number in array */
        count++;                         /* Count that number */
        scan_status = scanf("%f", &x);   /* get next number */
    }
    return count;
}

/* sort: sorts its argument array in descending order.
   Arguments:
       data: the array to sort.  count: number of values in data.
*/
void sort(float data[], int count) {
    void display(float data[], int count); /* Function to output array */
    int num_of_passes,     /* Num. of passes needed to sort the array */
        completed_passes,  /* how many passes are complete */
                           /* NB: also the index of the first item */
                           /* to scan in a pass */
        items_to_scan,     /* no. of items to examine this pass */
        max_item;          /* index of max. item in relevant region */
    float temp;            /* a temporary. */

    /* temporary output, just to demonstrate how it works: */
    printf("Initial order: ");
    display(data, count);

    /* Set up for pass one. */
    num_of_passes = count - 1;
    completed_passes = 0;  /* none done yet */
    items_to_scan = count; /* on first pass, scan all elements */

    while (completed_passes < num_of_passes) {
        /* Invariant: data[0] to data[completed_passes-1] are sorted,
                      and larger than any item in data[completed_passes] to
                                 data[count-1].
        */

        /* Locate the biggest item */
        max_item = maxindex(data, completed_passes, items_to_scan);

        /* Now swap the biggest item with the first. */
        temp = data[completed_passes];  /* store first item */
        data[completed_passes] = data[max_item];
                                        /* put largest first */
        data[max_item] = temp;          /* put old first item where
                                           max item used to be. */

        /* prepare for next pass */
        completed_passes++;
        items_to_scan--;

        /* temporary output, just to demonstrate how it works: */
        printf("After pass %2d: ", completed_passes);
        display(data, count);
    }
}

void display(float data[], int count) {
    int i;
    for (i=0; i<count; i++) {
        printf(" %5.2f", data[i]);
    }
    putchar('\n');
}

/* maxindex: Tell which array element in a range has the largest value.
   Parameters: values:    the array to search,
               lowindex:  the index of the first element to examine,
               numvalues: the number of elements to examine.
   N.B. lowindex+numvalues must not exceed the declared
        array size, nor may numvalues be below 1, or lowindex
        below 0.
   Function result: the index of the largest element with a subscript
                    in the range lowindex ... lowindex+numvalues-1
                    inclusive.
*/
int maxindex(float values[], int lowindex, int numvalues) {
    int i, index, latest_max_index;
    float current_max;

    current_max = values[lowindex];     /* remember 1st value */
    latest_max_index = lowindex;        /* remember 1st index */

    /* Now loop, looking at numvalues-1 elements, starting just AFTER
       the element remembered above.  Note the use of two initialisers
       and two increment assignments in the for loop heading.  This
       trick is accomplished using the 'comma' operator (','), which
       lets us write two expressions where normally only one would
       be allowed.  See appendix C. */

    for (i=1, index=lowindex+1; i<numvalues; i++, index++) {
        if (values[index] > current_max) {  /* found a bigger one... */
            current_max = values[index];    /* update max */
            latest_max_index = index;       /* update index */
        }
    }

    return latest_max_index;
}