Is this the worst case? If so why? If not, what is the worst case and why?
What is the best case? What are c and s in the best case?
What is a formula for the number of comparisons and the number of swaps in the worst case for an array of n elements?
// selsort.c: use selection sort to order 'n' numbers on stdin #include <stdio.h> #include <stdlib.h> #include <assert.h> void selsort(int array[], int n); int main(int argc, char **argv) { int *array; int readError = 0; int number; if (scanf("%d", &number) == 1) { // read the 'n' array = (int *)malloc(number * sizeof(int)); // get memory to hold 'n' numbers assert(array != NULL); int i; for (i=0; i<number && !readError; i++) { if (scanf("%d", &array[i]) != 1) { // fill the array readError = 1; } } } else { readError = 1; } if (!readError && number>0) { //////////////////////////// selSort(array, number); // sort the array ////////////////////////// printf("Sorted numbers:"); // output the sorted list int i; for (i=0; i<number; i++) { printf(" %d", array[i]); } putchar('\n'); } return EXIT_SUCCESS; } void selSort(int array[], int length) {// actual selection sort int i; // this is an 'in place' sort so ... int min; // ... the array is 'overwritten' int marker; for (marker=0; marker<length; marker++) { min = marker; // assume element 'marker' is minimum for (i = marker+1; i<length; i++) { if (array[i] < array[min]) { min = i; // found a better min at location 'i' } } int tmp; tmp = array[marker]; array[marker] = array[min]; // swap element 'min' and 'marker' array[min] = tmp; } } |
It reads numbers from stdin into an array, sorts them, and prints the sorted numbers on stdout. Now let us assume that we do not have simple numbers, but the input data consists of strings (colours) and numbers (codes) as in:
4 red 12 blue 3 green 67 white 0 |
We assume for convenience that all colour names are less than 20 characters long.
Create a type called Colourcode to represent the input data.
Sorted codes: white:0 blue:3 red:12 green:67 |
If instead we want to sort the data alphabetically based on the colour, what needs to change? The data sorted by colour is:
Sorted codes: blue:3 green:67 red:12 white:0 |
Suppose we are given two stacks, say s1 and s2, of numbers. Implement a function linearSearch(s1,s2,n)
that pops n items off s1 and pushes them onto s2 except the maximum element, which the function returns. The function should have prototype:
int linearSearch(Quack, Quack, int) |