Homework assignment #5

Due Monday, December 13

There are many different ways of sorting lists of numbers. Probably the simplest is the bubble sort, which is less efficient but easier to understand than many of the more complex sorting algorithms. You can find a web page that discusses the bubble sort, complete with some example code and an animated view of how the sort works, at:

http://www.cs.princeton.edu/~ah/alg_anim/gawain-4.0/BubbleSort.html

In general, the bubble sort works by repeatedly looping over the array, swapping adjacent elements if they are out of order.

I would like you to take the scores program that we began in class, and change it to sort the scores and print them out. Since we didn't complete the median and standard deviation calculation functions, your program can just print 0 for these values.

My suggestion is that you do the sort in a separate function. This function should sort the array in place - that is, when it's done, the numbers in the scores array should have been shuffled around so that they're in ascending order. Refer to the web page mentioned above for information about sorting. There's a more complex sorting algorithm in your textbook; you're welcome to try that if you like instead.

Extra credit:

As extra credit, you may implement the CalculateMedian and CalculateStandardDeviation functions. Here's some information to help you if you choose to do one or both of these:

1) The median is simply the value that has an equal number of values above and below it. This is really easy to find if your numbers are sorted, since you just have to look at the center of the array. Of course, if the array has an even number of elements, this isn't possible; in that case, it's common to just take the average of the two central values in the array

2) The standard deviation is defined as being the square root of the variance. Variance is a way of measuring the variability of the values about the mean (average) value. If the mean value is m, we calculate the variance for the array by adding up, for each value x in the array, (m-x)^2, then dividing the whole sum by N-1 (where N is the number of values in the array). Symbolically, this is described like this:

You may use this code for your homework. I have put identical code into a MS Visual C++ project for you to use.

scores.zip

Here's what in there:

In file scores.c:

#include <stdio.h>

int InputScores (double *);
void PrintStats (double *, int);
void SortScores (double *, int);

int main (void)
{
    double scores[250];
    int numScores;

    printf ("Scores: a program to compute grade statistics.\n");
    printf ("Enter all scores, finish with –1:\n\n");

    /* Read in the scores */
    numScores = InputScores (scores);

    /* Sort the array from lowest to highest */
    SortScores (scores, numScores);

    /* Calculate and print average, median, and standard deviation */
    PrintStats (scores, numScores);

    /* Now you write the code to print the scores */
}

In file InputScores.c:

#include <stdio.h>

int InputScores (double *scores)
{
    int count = 0;
    double score;

    while (1) {
        scanf (“%lf”, &score);
        if (score < 0.0)
            break;
        scores[count++] = score;
}

    return count;
}

In file PrintStats.c:

#include <stdio.h>

double ComputeAverage (double *, int);
double ComputeMedian (double *, int);
double ComputeStandardDev (double *, int);


void PrintStats (double *scores, int num)
{
    double average;
    double median;
    double stdDev;


    average = ComputeAverage (scores, num);
    median = ComputeMedian (scores, num);
    stdDev = ComputeStandardDev (scores, num);


    printf ("Average: %5.1f\n", average);
    printf ("Median: %5.1f\n", median);
    printf ("Standard deviation: %5.1f\n", stdDev);
}


/*
 * ComputeAverage: calculate and return the average
 *     of the numbers in an array
 */
double ComputeAverage (double *array, int size)
{
    int i;
    double sum = 0.0;

    for (i = 0; i < size; ++i)
        sum += array[i];
    return sum/size;
}

/*
 * ComputeMedian: calculate and return the median value
 *     for the numbers in an array
 */
double ComputeMedian (double *array, int size)
{
    double median = 0.0;

    /* Extra credit */
    /* You fill in this function */

    return median;
}


/*
 * ComputeStandardDev: calculate and return the standard
 *     deviation for the numbers in an array
 */
double ComputerStandardDev (double *array, int size)
{
    double stdev = 0.0;

    /* Extra credit */
    /* You fill in this function */

    return stdev;
}

In file SortScores.c

/*
 * SortScores: sort an array from lowest to highest
 */
void SortScores (double *array, int size)
{
    /* You fill in this function */
}