Week 12 Tutorial — Sample Solutions

    1. Given case: 
                     c    s
  [4 3 2 1]:
  [1 3 2 4]:   3    1
  [1 2 3 4]:   2    1
  [1 2 3 4]:   1    0
              ---  ---
               6    2

    2. A worst case (there's more than one): 
                     c    s
  [3 4 2 1]:
  [1 4 2 3]:   3    1
  [1 2 4 3]:   2    1
  [1 2 3 4]:   1    1
              ---  ---
               6    3
      It is a worst case because there is a swap for every change in marker.

    3. The best case (there's only one): 
                     c    s
  [1 2 3 4]:
  [1 2 3 4]:   3    0
  [1 2 3 4]:   2    0
  [1 2 3 4]:   1    0
              ---  ---
               6    0

    4. In general, c = (n-1) + (n-2) + ... + 1 = n(n-1)/2 and s = n-1. Hence the number of comparisons c is quadratic (it grows like n2).

    1. The type is: 

      #define MAXNAME 20
typedef struct {
	char colour[MAXNAME];
	int  code;
} Colourcode;

    2. The complete program that sorts according to 'code' is: 

      // structselsort1c: use selection sort to sort 'n' colour+code structs according to 'code'
#include <stdio.h>
#include <stdlib.h>

#define MAXNAME 20
typedef struct {
        char colour[MAXNAME];
        int  code;
} Colourcode;

void selsort(Colourcode array[], int n);

int main(int argc, char **argv) {
   Colourcode *array;
   int readError = 0;
   int number;
   if (scanf("%d", &number) == 1) {          // read the 'n'
      array = (Colourcode *)malloc(number * sizeof(Colourcode)); // get memory to hold 'n' Colourcodes
      assert(array != NULL);
      int i;
      for (i=0; i<number && !readError; i++) {// fill the array
         if (scanf("%s %d", array[i].colour, &array[i].code) != 2) {
            readError = 1;
         }
      }
   } else {
      readError = 1;
   }
   if (!readError && number>0) {
      ///////////////////////////
      selsort(array, number); // sort the array of structs
      /////////////////////////
      printf("Sorted codes:");
      int i;
      for (i=0; i<number; i++) {
         printf(" %s:", array[i].colour);
         printf("%d", array[i].code);
      }
      putchar('\n');
   }
   return EXIT_SUCCESS;
}

void selsort(Colourcode array[], int length) { // selection sort
   int i;
   int min;
   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].code < array[min].code)
            min = i; // found a better min at location 'i'
      }
      Colourcode tmp;
      tmp = array[marker];
      array[marker] = array[min]; // swap element 'min' and 'marker'
      array[min] = tmp;
  }
}

    3. The only change required to sort the data by colour is the comparison in selsort(). The inner loop in this function should read: 

      for (i = marker+1; i<length; i++) {
   if (strcmp(array[i].colour, array[min].colour) < 0)
      min = i; // found a better min at location 'i'
}

  3. An implementation of the linear search function on stacks is 

    int linearSearch(Quack s1, Quack s2, int n) { // pop n items from s1, push to s2, except max
   int max = pop(s1);
   int i;
   for (i=1; i<n; i++) {
      int num = pop(s1);
      if (num > max) {
         int temp = max;
         max = num;
         num = temp;
      }
      push(num, s2);
   }
   return max;
}