/*
  Name:    ex9-1.c
  Purpose: recursive selection sort
  Author:  Bill Slough
*/

#include <stdio.h>
#include <stdbool.h>

#define N 100          /* maximum number of input values */
#define PERLINE 8      /* how many values to display on each line */

int get_data(int a[ ], int size, bool *overflow);
void display_data(int a[ ], int n, int per_line);
void swap(int *x, int *y);
void selection_sort(int a[ ], int n);

int main() {
    int x[N];           /* storage for the values to be sorted */
    int how_many;       /* how many values are stored in x? */
    bool too_many;      /* did reading data cause overflow? */

    how_many = get_data(x, N, &too_many);
    if (too_many)
        printf("Warning: too much input data\n");

    printf("Before sorting:\n");
    display_data(x, how_many, PERLINE);

    selection_sort(x, how_many);

    printf("After sorting:\n");
    display_data(x, how_many, PERLINE);

    return 0;
}

/* Read input data values into an array a, with capacity = size.
   Set the overflow indicator if there were too many input values and
   return the actual number of data values which were read and stored. */
int get_data(int a[ ], int size, bool *overflow) {
    int i;
    int item;
    i = 0;
    while (i < size && (scanf("%d", &item) != EOF)) {
        a[i++] = item;
    }
    *overflow =  (i == size) && (scanf("%d", &item) != EOF);
    return i;
}

/* Output the n values of a given array */
void display_data(int a[ ], int n, int per_line) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%10d ", a[i]);
        if ((i + 1) % per_line == 0)
            printf("\n");
    }
    printf("\n");
}

/* Swap two integers */
void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

/* sort the first n elements of the array a */
void selection_sort(int a[ ], int n) {
    int k;     /* index of largest value among a[0] ... a[n - 1] */
    int i;

    if (n > 1) {
        /* find the largest among a[0] ... a[n - 1] */
        k = 0;
        for (i = 1; i < n; i++) {
            if (a[i] > a[k])
                k = i;         /* larger value seen at i */
        }

        /* move this largest value to its correct location */
        swap(&a[k], &a[n - 1]);

        /* sort the rest */
        selection_sort(a, n - 1);
    }
}