|
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: 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
* * May 14, 2024: modified swap to occur only if needed
*/
#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 */
if (min != 0){
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() */
/*
* 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)
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);
}
|
ECS 36A, Programming & Problem Solving Version of April 2, 2024 at 12:13PM
|
You can get the raw source code here.
|