/*
 * SORT -- recursively sort a list using selection sort,
 * building list as a linked list with nodes created by malloc()
 *
 * The data structure used is a linked list;
 * each element looks like this:
 *	+--------------+
 *  |  data field  |  <--- holds the integer that you read in
 *	+--------------+
 *  |  next field  |  <--- holds pointer to next element in
 *	+--------------+       linked list (NULL if nothing
 *	                       follows it)
 *
 * The pointer variable "list" contains a pointer to the first
 * element in the linked list (NULL if there are no elements
 * in the linked list)
 *
 * Usage: sort
 *      
 * Inputs: numbers to be sorted
 * Outputs: prints the initial list and the sorted list
 *      
 * Matt Bishop, ECS 36A, Fall 2019
 * * October 30, 2019: adapted from a program for ECS 30
 */             
#include <stdio.h>
#include <stdlib.h>

/*
 * the structure
 */
struct s_numentry {			/* a list entry */
	int num;				/* the number it holds */
	struct s_numentry *next;		/* points to next element */
};
typedef struct s_numentry numentry;	/* renamed above type */
 
/*
 * pointer to head of list to be sorted
 */
numentry *list;
 
/*
 * recursive sort -- put smallest element at head of array
 * and then sort the rest
 */
void sort(numentry *l)
{
		numentry *p;    /* used to walk the list */
		numentry *min;  /* points to minimum element */
		int tmp;        /* used to swap ints */
 
		/* base case */
		if (l == NULL)
			return;
 
		/* find index of smallest number in array */
		min = l;
		for(p = l; p != NULL; p = p->next)
			if (min->num > p->num)
				min = p;
 
		/* move smallest element to 0-th element */
		/* swapping it with whatever is there    */
		tmp = l->num;
		l->num = min->num;
		min->num = tmp;
		
		/* recurse */
		sort(l->next);
}

/*
 * make a node in the list
 */
numentry *createnode(int n)
{
	numentry *p;		/* points to allocated space */

	/*
	 * allocate the space for the node
	 */
	if ((p = malloc(sizeof(numentry))) == NULL){
		fprintf(stderr, "Ran out of memoty\n");
		exit(1);
	}

	/*
	 * now populate the fields
	 */
	p->num = n;
	p->next = NULL;

	/*
	 * done with the node
	 */
	return(p);
}
 
/*
 * the input routine
 */
void readnums(void)
{
	int i;			/* counter in a for loop */
	int j;			/* number of numbers read */
	int n;			/* the input number */
	numentry *l;		/* pointer to new node */

	/*
	 * now create the array
	 */
	printf("Please enter your numbers, one per line; end with EOF\n");

	/*
	 * count numbers for prompt
	 */
	i = 1;

	/*
	 * now loop until end of list entered
	 */
	while(j != EOF){
		/* prompt and read number */
		printf("\t   number %d: ", i);
		while((j = scanf("%d", &n)) != 1 && j != EOF)
			printf("try again; number %d: ", i);
		/* at EOF, you're done! */
		if (j == EOF)
			break;

		/* read one more number */
		i++;

		/* create the node */
		if ((l = createnode(n)) == NULL)
			exit(1);

		/* insert it into the list (at the head of list) */
		if (list == NULL)
			list = l;
		else{
			l->next = list;
			list = l;
		}
	}
} 

/*
 * the main routine
 */
int main(void)
{
		numentry *l;		/* pointer to an element in list */

		/*
		 * now create the array
		 */
		readnums();

		/* print initial array */
		printf("\ninitial array: ");
		for(l = list; l != NULL; l = l->next)
			printf(" %3d", l->num);
		putchar('\n');
 
		/* now sort */
		sort(list);
 
		/* print sorted array */
		printf("final array:   ");
		for(l = list; l != NULL; l = l->next)
			printf(" %3d", l->num);
		putchar('\n');
		return(0);
}