Lab 6: Algorithm Analysis

Lab Structure

  1. Pick a partner.
  2. Help each other with the code as needed. Do not type for your partner and avoid dictation, but make sure your partner is able to finish the assignment.
  3. Make sure that your partner understands the mergesort enough to take a test over it.
  4. Put your partner's name with yours in the header of the sort.c file.
  5. If your partner is unable to complete the lab, your maximum grade is a 90%.

Runtime Complexity of Sorts

Analysis of Insertion Sort pp. 264-266

  • The insertion sort has nested for loops, each of which can take N iterations: O(N2)
  • If the list is already sorted, the inner for loop condition will fail everytime. Therefore, if the list is sorted, the algorithm requires only N iterations.
  • The number of times the inner loop executes is based on the number of inversions in the list: an inversion is any two elements where the first element is larger than the second.
  • The runtime of the insertion sort is O(I+N), where I is the number of inversions.
  • A reverse sorted list has up to O(N2) inversions.
  • The insertion sort is O(N2).

Analysis of the Mergesort pp. 276-279

  1. The time to mergesort 1 element is 1: Time (1) = 1
  2. Time (N) = 2 Time (N/2) + N
  3. (Time (N))/N = (Time(N/2))/(N/2) + 1
  4. (Time (N/2))/(N/2) = (Time(N/4))/(N/4) + 1
  5. (Time (N/4))/(N/4) = (Time(N/8))/(N/8) + 1 . . .
  6. (Time (2))/(2) = (Time(1))/(1) + 1
  7. Now if we add up the equations, we get (Time(N))/N = (Time(1))/1 + log N.
  8. Therefore the runtime is O(N log N).

Analysis of the Quicksort pp. 287-290

The analysis is too long to cover in lab. However, here is the summary:
  1. In the worst case (the pivot is always the smallest or largest), the runtime is O(N2).
  2. In the best case (the pivot is always the middle value), the runtime is O(N log N).
  3. In the average case, the algorithm is O (N log N)

Analysis of the Bubblesort

  • Analyze the bubblesort.
  • In a file called analyze.txt, give the runtime complexity of the bubblesort and why you believe it is the right complexity.

Testing the Runtime

  1. Copy everything from /users/smatzko/212/public/ to your folder.
  2. Write the four (4) sorting algorithms. You should have the code for insertion sort, quicksort, and mergesort. You need to type in bubblesort. Use the code below as needed.
  3. Run the provided main to test your sorting algorithms.
  4. Use gnuplot to graph the resulting data:
    1. Type gnuplot
    2. Type plot "bubble.dat" with linespoints
    3. The points are hard to follow. Let's smooth it:
      Type plot "bubble.dat" smooth unique
    4. Now lets plot all of them with a smoothed result:
      Type plot "bubble.dat" smooth unique, \
      "insert.dat" smooth unique, \
      "merge.dat" smooth unique, \
      "quick.dat" smooth unique
    5. Since Bubblesort is so slow, type plotting without it:
      plot "insert.dat" smooth unique, \
      "merge.dat" smooth unique, \
      "quick.dat" smooth unique
    6. Plot each algorithm separately.
  5. In analyze.txt, state whether the results were as you expected. Which algorithm was the fastest? Which was slowest? Which graph did bubblesort match? Which graph did mergesort match?

Reference Code

#include <sys/types.h>
#include <vector>

using std::vector;

template<typename T> void bubblesort (vector<T> &list);
template<typename T> void insertionsort (vector<T> &list);
template<typename T> void mergesort (vector<T> &list);
template<typename T> void quicksort (vector<T> &list);

template<typename T> void insertionsort(vector<T> &list,uint left, uint right);
template<typename T> void mergesort (vector<T> &list, vector<T> &tmpArray,
                                     uint left, uint right);
template<typename T> void merge (vector<T> &list, vector<T> &tmpArray,
                                 uint leftPos, uint rightPos, uint rightEnd);
template<typename T> void quicksort (vector<T> &list, uint left, uint right);
template<typename T> void swap (T &first, T &second);
template<typename T> const T &median3 (vector<T> &list, uint left, uint right);

template <typename T>
void bubblesort (vector<T> &list) {
   bool swapped = true;
   while (swapped) {
      swapped = false;
      for (uint i=0; i < list.size(); ++i) {
         if (list[i] > list[i+1]) {
            swap (list[i], list[i+1]);
            swapped = true;
         }
      }
   }
}

template <typename T>
void insertionsort (vector<T> &list) {
   insertionsort (list, 0, list.size()-1);
}

template <typename T>
void insertionsort (vector<T> &list, uint left, uint right) {
   uint j;
   for (uint i=left+1; i <= right ; ++i) {
      T temp = list[i];
      for (j=i; j > 0 && temp < list[j-1]; --j) {
         list[j] = list[j-1];
      }
      list[j] = temp;
   }
}

template<typename T>
void mergesort (vector<T> &list) {
   vector<T> tmpArray (list.size());
   mergesort (list, tmpArray, 0, list.size()-1);
}

template<typename T>
void mergesort (vector<T> &list, vector<T> &tmpArray, uint left, uint right) {
   if (left < right) {
      uint center = (left + right)/2;
      mergesort (list, tmpArray, left, center);
      mergesort (list, tmpArray, center+1, right);
      merge (list, tmpArray, left, center+1, right);
   }
}

template<typename T>
void merge (vector<T> &list, vector<T> &tmpArray, uint left, uint right,
            uint rightEnd) {

   uint i, start = left, leftEnd = right-1;
   uint numElements = rightEnd - left + 1;
   for (i=0; left <= leftEnd && right <= rightEnd; ++i) {
      tmpArray[i] = (list[left] < list[right]) ? list[left++] : list[right++];
   }
   while (left <= leftEnd) {
      tmpArray[i++] = list[left++];
   }
   while (right <= rightEnd) {
      tmpArray[i++] = list[right++];
   }
   for (i=0; i < numElements; ++i) {
      list[start++] = tmpArray[i];
   }
}

template <typename T>
void quicksort (vector<T> &list) {
   quicksort (list, 0, list.size()-1);
}

template <typename T>
void quicksort (vector<T> &list, uint left, uint right) {

   if (left + 10 > right) {
      insertionsort (list, left, right);
   } else {
      T pivot = median3 (list, left, right);
      int i=left, j=right-1;

      for (;;) {
         while (list[++i] < pivot) {}
         while (pivot < list[--j]) {}
         if (i < j)
            swap (list[i], list[j]);
         else
            break;
      }
      swap (list[i], list[right-1]);
      quicksort (list, left, i-1);
      quicksort (list, i+1, right);
   }
}

template <typename T>
void swap (T &first, T &second) {
   T temp = first;
   first = second;
   second = temp;
}

template<typename T>
const T &median3 (vector<T> &list, uint left, uint right) {
   uint center = (left+right)/2;
   if (list[center] < list[left]) swap (list[left], list[center]);
   if (list[right] < list[left]) swap (list[left], list[right]);
   if (list[right] < list[center]) swap (list[center], list[right]);
   swap (list[center], list[right-1]);
   return list[right-1];
}

Turn in

Turn in all of the code, a Makefile, and your analyses.
Use sendlab.212.302 6 analyze.txt *.cpp *.h Makefile