usort15.c

/*
 * SORT -- recursively sort a list using selection sort,
 * building list in an array created by malloc()
 *
 * Usage: sort
 *      
 * Inputs: numbers to be sorted
 * Outputs: prints the initial array and the sorted array
 *      
 * Matt Bishop, ECS 36A, Spring 2023
 * * October 30, 2019: adapted from a program for ECS 30
 * * May 8, 2023: rewrote read number routine to use dynamic allocation
 */             
#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);
}

#define SZ 3
/*
 * the input routine
 */
void readnums(void)
{
	int i;		/* number of numbers read so far */
	int j = 0;	/* last number read */
	int n = 0;	/* number of chunks of size SZ allocated */
	int *tmp;	/* temp pointer for realloc() */
	int ch;

	/*
	 * initial allocation of memory for the list
	 */
	if ((list = (int *) malloc(SZ * sizeof(int))) == NULL){
		perror("Cannot allocate enough space");
		exit(1);
	}
	/* allocated the first chunk */
	n++;

	/*
	 * read on numbers
	 */
	for(i = 0; j != EOF; i++){
		/* do we need to reallocate to get more space? */
		if (i >= n * SZ){
			/*now reallocate space */
			tmp = (int *) realloc(list, (n+1) * SZ * sizeof(int));
			/* didn't work -- quit */
			if (tmp == NULL){
				perror("Cannot allocate enough space");
				exit(1);
            		}
			/* fix up the list pointer and chunk count */
			list = tmp;
			n++;
		}
		/* prompt */
		printf("\t   number %d: ", i + 1);
		/* loop until you get an integer or EOF */
		while((j = scanf("%d", &list[i])) != 1 && j != EOF){
			while((ch = getchar()) != '\n' && ch != EOF)
				;
			printf("try again; number %d: ", i);
		}
	}
	/* EOF does not put out a newline, so we do it */
	putchar('\n');
	/* set total number of numbers */
	nlist = i - 1;
}

 /*
  * 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);
}


UC Davis sigil
Matt Bishop
Office: 2209 Watershed Sciences
Phone: +1 (530) 752-8060
Email: [email protected]
ECS 36A, Programming & Problem Solving
Version of April 2, 2024 at 12:13PM

You can get the raw source code here.

Valid HTML 4.01 Transitional Built with BBEdit Built on a Macintosh