CSCI 161 lab exercise 5: recursion and sorting

Lab exercise 5 is to be submitted electronically by 10 a.m. Apr. 8th, and covers the work from the lab sessions of Mar. 25-27, suitably cleaned up to adhere to standards. The submission mechanism is detailed below, and must be followed to obtain credit for the lab.

The exercise will be marked out of 10, and is worth 5% of your total grade.

Late submissions will be penalized 2.5 marks per day late or part thereof.

Exercise details:

For lab exercise 5 you will be implementing a recursive sorting function, quicksort, the partition function it utilizes, and a supporting swap function.

Two files are provided, sort.h and labex5.C, containing the code to drive the sorting application and the prototypes for quicksort, partition, and swap.

You will create sort.C, containing the implementation of the functions prototyped in sort.h.

Nothing should be altered in sort.h or labex5.C, and you must follow the quicksort and partition algorithms as closely as possible:
Algorithms to use
Quicksort
   if upper > lower
      call partition, store returned midpt
      call recursively on lower..midpt-1
      call recursively on midpt+1..upper

Partition
   mid = lower
   if upper <= lower 
      return lower
   otherwise
      pivot = arr[lower]
      mid = lower
      swap arr[lower] with arr[upper]
      for pos = lower .. upper-1
          if arr[pos] < pivot
             swap arr[pos] with arr[mid]
             and increment mid
      swap arr[mid] with arr[upper]
      return mid

The code is available here labex5.C , sort.h 
// sort.h
#ifndef SORT_H
#define SORT_H

// recursively sort the array segment   
void quicksort(float arr[], int lower, int upper);

// divide the array segment into small/large values, and
// return the array position marking the changeover point
int partition(float arr[], int lower, int upper);

// exchange the values in two floats
void swap(float &a, float &b);

#endif

// labex5.C
#include "sort.h"
#include <iostream>
using namespace std;

// get the user to supply a collection of floats,
//     store them in an array
void getValues(float* &arr, int &size);

// display the array contents, one number per line
void printArr(float* arr, int size);

int main()
{
   float *data;
   int    size;
   getValues(data, size);
   if (data != NULL) {
      cout << "---Original data---\n\n";
      printArr(data, size);
      cout << "\n---Sorting...\n";
      quicksort(data, 0, size-1);
      cout << "\n---Sorted data---\n";
      printArr(data, size);
      delete [] data;
   } else {
      cout << "Unable to allocate data storage" << endl;
      cout << "Shutting down" << endl;
   }
   return 0;
}

// get the user to supply a collection of floats,
//     store them in an array
void getValues(float* &arr, int &size)
{
   cout << "Specify the number of values to sort: ";
   cin >> size;
   arr = new float[size];
   if (arr != NULL) {
      cout << "Enter the " << size << " numeric values:\n";
      for (int i = 0; i < size; i++) {
          cin >> arr[i];
      }
   }
}

// display the array contents, one number per line
void printArr(float* arr, int size)
{
   if (arr != NULL) {
      for (int i = 0; i < size; i++) {
          cout << arr[i] << endl;
      }
   }
}

Submission mechanism

You will be submitting your sort.C file (correct spelling and capitalization is essential for the submission to work correctly).

To submit the assignment, cd to the directory that contains your sort.C file and type the following command: 

   /home/faculty/wesselsd/bin/submit  161  sort.C
Note that each submission overwrites any previous submission you have made.

Marking guidelines:

Marks will be based on:

Code standards:

The submission must follow the code standards for labex4,