Paralell Arrays

Suppose that we wanted to write a program that will post a list of test scores for a class of students (at most 40 students per class) To keep the results anonymous, we are posting only the student number(a number) and the the test percentages (midterm and final. Results are floats). How would we store this information?

There are up to 40 students per class. For each student we need to record:

• student number (int)
• a midterm test (float) * a final test (float)

Let us consider the tools we have encountered up to this point for aggregate types:

• array - multiple items all must be the same type
• struct - puts together related info that can be different types

Paralell Arrays

One solution to our problem is that we can use something called paralell arrays. A parallel array consists of two or more arrays. Things that are stored in the same index are considered to be related.

For example suppose we have 3 students with the following information:

Student 1:

• student number: 123456
• midterm: 63.5
• final: 65.0

Student 2:

• student number: 654321
• midterm: 70.5
• final: 75.3

Student 3:

• student number: 345678
• midterm: 91.5
• final: 82.3

We would create our 3 arrays as follows:

int studentNumber[40] = {123456, 654321,345678};
float midterm[40] = {63.5, 70.5, 91.5};
float finals[40] = {65.0, 75.3, 82.3};

The above code creates this:

Return Weighted Average

Suppose we wanted to write a function that will calculate the weighted average of a student's grade given their student number. The weighted of the midterm is 40%, the weight of the final is 60%. How would we do this? We can assume that a match to the student number will always be found.

Forming the function prototype

When we want to write a function, the first step is to determine the function prototype.

Name the array:

weighteAvg seems like it will be a good name as it is meaningful and states what the function will calculate

Determine Parameters:

• We need to know the student number we are looking for
• We need the three arrays in order to find the information we need
• All arrays require a number indicating how much of the array is actually being used

The data we need to look at is stored in the three paralell arrays so we will want to pass those to the array. As we are working with arrays we want to know how many items are stored in those aways. The value we are looking for is a single student number. The result is an average which is floating point point

Determine Return Type:

• The result of this calculation will also be floating point

Putting it all together

Putting this together this is the result:

/*
This function is passed a key (the student number we are searching for), 3 parallel
arrays of student numbers, midterms and finals, and the number of elements used in
the arrays.  The function returns the weighted average of of midterm and finals (40%
midterm, 60% final)
*/
float weightedAvg(int key, int studentNumber[], float midterms[], float finals[], int used);

Writing the Function

To calculate the weighted average, we first need to know which midterm and which final we want to work with. We do this by looking for the location (array index) of key within the studentNumber array first. Once we have that we use that same index to access specific elements of midterm and finals then use that to do the weighted average calculation.

/*
This function is passed a key (the student number we are searching for), 3 parallel
arrays of student numbers, midterms and finals, and the number of elements used in
the arrays.  The function returns the weighted average of of midterm and finals (40%
midterm, 60% final)
*/
float weightedAvg(int key, int studentNumber[], float midterms[], float finals[], int used)
{
    int idx = -1;
    int i;
    //look for idx, this loop stops when we find a matching number or we get to end of array
    for(i = 0; i < used && idx == -1;i++){
        if(key == studentNumber [i]){
            idx = i;
        }
    }

    //we assumed the student number always exists so no error checking is done here
    return midterms[idx]*0.4 + finals[idx]*0.6;
}

Sort Data based on Student Number

Suppose we wanted to reorder our arrays so that the data is ordered by student numbers in ascending order. To do this we can apply one of the standard simple sorting algorithms. Sorting is a well studied computer problem. There are many sorting algorithms that are available. The simplest of the sorting algorithms are:

• Bubble sort
  • starting at the beginning of the array, swap adjacent elements if they are not in the correct order
  • after passing through the array one time, the largest number will have "bubbled" to the end of the array
  • if we do it (n-1) times where n is the number of items in the array, we will get a sorted array
  • click here for animation
• Insertion sort
  • start with the second element of the array and move it into a temporary variable
  • the array is split in two partss, the first parts is sorted, the second is unsorted.
  • the initial first part consists of the first element an an empty spot (the second element that we had emptied). Since one single value is "sorted", we have a sorted array.
  • the item in the temporary storage is then "inserted" back into the sorted part of the array maintaining sorted order
  • repeat this process for every other element of the array to get a sorted
  • click here for Animation
• Selection sort
  • initially the entire array is unsorted.
  • find the smallest value in the array
  • swap it with the start of the unsorted part of the array.
  • make that element part of the sorted part of the array. The unsorted part now has one less value
  • repeat until every value is sorted
  • click here for Animation

All sorting algorithms do the same thing in different ways. For this exercise we will use bubble sort.

/*
this is the standard bubble sort algorithm working on a single array of
integers. It is passed an array and the number of elements in use for
that array
*/
void bubbleSort(int array[], int used)
{
    int i;          //index for outer loop
    int j;          //index for inner loop
    int tmp;        //used for swapping
    //repeat going through the array n-1 times
    for (i=0; i<used-1; i++){
        //go from start of array up to the end of the unsorted part
        for(j=0; j<used-1-i; j++){
            //if the adjacent values are not in order swap them
            if(array[j] > array[j+1]){
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
            }
        }
    }
}

Applying the above algorithm to our problem we would need to pass in 3 arrays and any time we swap, we need to swap in all 3 arrays because we need to make sure that the arrays stay parallel:

void sortStudents(int studentNumber[], float midterms[], float finals[], int used)
{
    int i;          //index for outer loop
    int j;          //index for inner loop
    int tmp;        //used for swapping
    float tmpFloat; //used for swapping floats
    //repeat going through the array n-1 times
    for (i=0; i<used-1; i++){
        //go from start of array up to the end of the unsorted part
        for(j=0; j<used-1-i; j++){
            //if the adjacent values are not in order swap them.  Note how
            //you only check student number since we are ordering just by
            //student numbers.. but if we  have to swap, we swap elements
            //in all 3 arrays
            if(studentNumber[j] > studentNumber[j+1]){
                //swap student numbers
                tmp = studentNumber[j];
                studentNumber[j] = studentNumber[j+1];
                studentNumber[j+1] = tmp;

                //swap midterms values
                tmpFloat = midterms[j];
                midterms[j] = midterms[j+1];
                midterms[j+1] = tmpFloat;

                //swap finals values
                tmpFloat = finals[j];
                finals[j] = finals[j+1];
                finals[j+1] = tmpFloat;

            }
        }
    }
}

Summary

• Parallel arrays allow you to use multiple arrays to store information
• Data stored at the same index is related to each other.
• If we were to alter our arrays, we have to maintain parallelness of the arrays