CSC 311 Winter 2002

Assignment 1

Due: Monday, January 14th

This is a warm-up assignment, reviewing material from CSC 310.

First, please read the programming style rules on the Assignments page.

Second, consider the following (slightly incorrect) implementation of selection sort:

void selectionSort(int a[], int n)
{
  int minIndex;
  for (int i = 0; i < n-1; i++) {
    minIndex = findMinIndex(a, i, n);
    swap(a[i], a[minIndex]);
  }
}

int findMinIndex(int a[], int start, int n)
{
  int minIndex = start;
  for (int i = start; i < n-1; i++) {
    if (a[i] < a[minIndex])
      minIndex = i;
  }
  return minIndex;
}

void swap(int x, int y)
{
  int temp = x;
  x = y;
  y = temp;
}

With this code, please do the following:

1. Fix the implementation.  Use the following test program to check whether it works.

  #include <iostream.h>

  void displayArray(int a[], int n)
  {
    for(int i = 0; i < n; i++)
      cout << a[i] << endl;
  }

  int main()
  {
    int a[5] = {5, 4, 3, 2, 1};

    selectionSort(a, 5);
    displayArray(a, 5);
    return 0;
  }
  

2. Templatize the sort. Use the following test program to check whether your templatized version works.

  #include <iostream.h>

  template <class T>
  void displayArray(T a[], int n)
  {
    for(int i = 0; i < n; i++)
      cout << a[i] << endl;
  }

  int main()
  {
    int a[5] = {5, 4, 3, 2, 1};
    double b[7] = {10.5, 9.4, 8.3, 7.2, 6.1, 5.0, 4.9};

    selectionSort(a, 5);
    displayArray(a, 5);
    cout << endl;

    selectionSort(b, 7); 
    displayArray(b, 7); 
    cout << endl; 

    return 0;
 } 

3. Analyze the running time of the sort, expressing it in big-Oh notation. Explain briefly how you derived your answer.

What to submit

Please submit this in two e-mail messages sent to jrogers@cs.depaul.edu.  

• The first should have attached a single .cpp file containing the templatized version of the sort (5 points) and which includes the three functions selectionSort, findMinIndex, and swap.  Its subject line must read: CSC 311, your last name, selection sort.
   
• The second e-mail should have attached a Word document containing a write-up of the running time analysis (5 points).  Its subject line must read: CSC 311, your last name, analysis.

Subject lines containing anything else will not be considered assignment submissions.