|
Matt Bishop Office: 2209 Watershed Sciences Phone: +1 (530) 752-8060 Email: mabishop@ucdavis.edu |
Version of April 2, 2024 at 12:13PM
/*
* 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);
}
|
ECS 36A, Programming & Problem Solving Version of April 2, 2024 at 12:13PM
|
You can get the raw source code here.
|