/*
 * SORT -- recursively sort a list using selection sort,
 * building list in an array created by malloc()
 *
 * Usage: sort
 *      
 * Inputs: number of numbers to be sorted; then the numbers
 * Outputs: prints the initial array and the sorted array
 *      
 * Matt Bishop, ECS 36A, Fall 2019
 * * October 30, 2019: adapted from a program for ECS 30
 */             
#include <stdio.h>
#include <stdlib.h>
 
/*
 * the array and its size
 */
int *list;		/* the array of integers, to be allocated */
int nlist;		/* number of elements in the array */
 
/*
 * recursive sort -- put smallest element at head of array
 * and then sort the rest
 */
void sort(int l[], int lsz)
{
	int i;          /* counter in a for loop */
	int tmp;        /* used to swap ints */
	int min;        /* index of minimum element */

	/* base case */
	if (lsz == 1)
		return;

	/* find index of smallest number in array */
	min = 0;
	for(i = 1; i < lsz; i++)
		if (l[i] < l[min])
			min = i;

	/* move smallest element to 0-th element */
	/* swapping it with whatever is there    */
	tmp = l[0];
	l[0] = l[min];
	l[min] = tmp;
	
	/* recurse */
	sort(&l[1], lsz-1);
}

/*
 * the input routine
 */
void readnums(void)
{
	int i;			/* counter in a for loop */
	int j;			/* number of numbers read */

	/*
	 * read in size of array
	 */
	printf("Number of numbers to sort > ");
	while((j = scanf("%d", &nlist)) != 1 && j != EOF && nlist < 1)
		printf("Try again; number of numbers to sort > \n");
	/* on EOF, program ends */
	if (j == EOF)
		exit(0);

	/*
	 * now create the array
	 */
	if ((list = (int *) malloc(nlist * sizeof(int))) == NULL){
		fprintf(stderr, "Not enough room for %d numbers\n", nlist);
		exit(1);
	}

	/*
	 * and read it in
	 */
	for(i = 0; i < nlist; i++){
		/* prompt */
		printf("\t   number %d: ", i + 1);
		/* loop until you get an integer or EOF */
		while((j = scanf("%d", &list[i])) != 1 && j != EOF)
			printf("try again; number %d: ", i);
		/* EOF here means to end the program */
		if (j == EOF)
			exit(0);
	}
}

 /*
  * the main routine
  */
int main(void)
{
	int i;			/* counter in a for loop */

	/*
	 * read in the array
	 */
	readnums();
		
	/*
	 * print initial array
	 */
	printf("initial array: ");
	for(i = 0; i < nlist; i++)
		printf(" %3d", list[i]);
	putchar('\n');

	/*
	 * now sort
	 */
	sort(list, nlist);

	/*
	 * print sorted array
	 */
	printf("final array:   ");
	for(i = 0; i < nlist;i++)
		printf(" %3d", list[i]);
	putchar('\n');
	
	/*
	 * all done!
	  */
	return(0);
}