/*
 * SORT -- recursively sort a list using selection sort
 *
 * Matt Bishop, ECS 36A, Fall 2019
 *
 * October 30, 2019
 *		-- adapted from a program for ECS 30
 */             
#include <stdio.h>
 
/*
 * the array and its size
 */
int list[] = { 13, 82, 0, 16, 5, -1, 99, 0 };
int nlist = sizeof(list)/sizeof(int);
 
/*
 * 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    */
		if (min != 0){
			tmp = l[0];
			l[0] = l[min];
			l[min] = tmp;
		}
		
		/* recurse */
		sort(&l[1], lsz-1);
}
 
 /*
  * the main routine
  */
int main(void)
{
		int i;			/* counter in a for loop */
 
		/* 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);
}