Week 12 Laboratory — Sample Solutions

  1. llselsort.c 

    void selSortLL(NodeT *head) { // selection sort on a linked list
   NodeT *marker;

   for (marker=head; marker!=NULL; marker=marker->next) {
      NodeT *min = marker; // assume element 'marker' is minimum
      NodeT *rest;
      for (rest=marker->next; rest!=NULL; rest=rest->next) {
         if (rest->data < min->data) {
            min = rest;    // found a better min at location 'rest'
         }
      }
      if (marker != min) { // swap data inside marker and min nodes
         int temp = marker->data;
         marker->data = min->data;
         min->data = temp;
      }
  }
}

  2. llinsertsort.c 

    NodeT *insSortLL(NodeT *head) { // insertion sort on a linked list
   if (head != NULL) {
      NodeT *marker = head->next;
      head->next = NULL;        // cut off the rest from the head
                                // in order to reinsert these elements
      while (marker != NULL) {
         NodeT *cur = marker;          // take the current marker 'cur' ...
         marker = marker->next;        // (advance marker for next round)
         if (cur->data < head->data) { // ... and make 'cur' the new head ...
            cur->next = head;
            head = cur;
         } else {                      // ... or find the new predecessor of 'cur' ...
            NodeT *pred = head;
            while (pred->next != NULL && (pred->next)->data < cur->data) {
               pred = pred->next;
            }
            cur->next = pred->next;    // ... and insert 'cur' after 'pred'
            pred->next = cur;
         }
      }
   }
   return head;  // head may have changed, hence needs to be returned
}

    Alternative solution: 
    void insertSortLL(NodeT *head) { // insertion sort on a linked list
                                 // a data-copy version
   NodeT *marker = head;
   NodeT *cur;

   while (marker != NULL) {    // for element 'marker' ...
      cur = head;              // ... find the right position ... 
      while (cur != marker) {  // ... and move all other elements up ...
         if (marker->data < cur->data) { // ... by repeated swaps
            int save = marker->data;
            marker->data = cur->data;
            cur->data = save;
         }
         cur = cur->next;
      }
      marker = marker->next;
   }
}

  3. selsortQ.c 

    // selsortQ.c: implement a selection sort of the command-line arguments using 2 stacks
#include <stdio.h>
#include <stdlib.h>
#include "quack.h"

void selectionSort(Quack, int);
int linearSearch(Quack, Quack, int);

int main(int argc, char *argv[]) {
   int readError = 0;
   int retval = EXIT_SUCCESS;

   Quack sq;
   sq = createQuack();
   int i;
   int number;
   for (i=1; i<argc && !readError; i++) {
      if (sscanf(argv[i], "%d", &number) != 1) {
         fprintf(stderr, "Error in arguments\n");
         readError = 1;
         retval = EXIT_FAILURE;
      } else {
         push(number, sq);       // populate the first quack
      }
   }
   if (!readError) {
      printf("Original ");
      showQuack(sq);
      selectionSort(sq, argc-1);  // argc-1 arguments to be sorted
      printf("  Sorted ");
      showQuack(sq);
   }
   return retval;
}

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-1; i++) {
      int num = pop(s1);
      if (num > max) {
         int temp = max;
         max = num;
         num = temp;
      }
      push(num, s2);
   }
   return max;
}

void selectionSort(Quack s1, int size) {
   Quack s2;
   s2 = createQuack();
   if (!isEmptyQuack(s1)) {
      int n;
      for (n=size; n>1; n--) {
         int max = linearSearch(s1, s2, n);
         push(max, s1);
         while (!isEmptyQuack(s2)) {
            push(pop(s2), s1);
         }
      }
   }
}