Week 12 Tutorial — Sorting Algorithms

    1. Use selection sort to sort the array [4, 3, 2, 1], noting how many comparisons c are made, and how many swaps s are carried out.

    2. Is this the worst case? If so why? If not, what is the worst case and why?

    3. What is the best case? What are c and s in the best case?

    4. What is a formula for the number of comparisons and the number of swaps in the worst case for an array of n elements?

  2. Consider the selection sort from lectures: 

    // 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.

    1. Create a type called Colourcode to represent the input data.

    2. We want to sort the input data according to the numerical 'code'. For the above data the program should generate: 
      Sorted codes: white:0 blue:3 red:12 green:67

      • Consider what needs to be changed in the main function of selsort() to read the colour data into an array of these data structures, and print the data in this array.
      • Now consider what needs to be changed in the function selsort().

    3. 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

  3. 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:

    4. int linearSearch(Quack, Quack, int)