/* * 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); }
|
ECS 36A, Programming & Problem Solving Version of April 2, 2024 at 12:13PM
|
You can get the raw source code here. |