Parallel Arrays

Section 1: Introduction

In many problems there are several pieces of information that are related.

• We could use multi-dimension arrays to store the data, but since we only know single-dimension arrays at this point we'll use two single-dimension arrays that are the same size.

For example, if you had name and scores, you might set up a string array for name and a numeric array for scores.

A particular score can be associated with a certain name because they have the same position, and therefore index, in their respective arrays.

Section 2: Example

Count the frequency of occurrence of grades in an array of scores.

If you were to do this by hand you would probably make a list of the grades that you want to count.

• Then you would start scanning the gradebook score-by-score, and when you encounter one of the grades that you are seeking you would put a hash mark by it in your list.

Such an algorithm can be used directly:

• The gradebook could be stored in a string array of scores called gradeBook.
• The list of grades whose frequency is to be counted can be read into an array of type string. That array will be called gradeList.
• To simulate recording a hash mark, use a second array called frequency that is the same size as the one containing the grade list (gradeList).
  • This parallel array will be numeric.

Loop through the grade array (gradeBook) one by one.

• For each grade, loop through the gradeList array, comparing the gradeBook entry to each gradeList entry to see if it is included in the list of grades to be counted.
• When a match is found use the index of the place in the array where the search item was found, and that index can be used as an index into the parallel array (frequency) to add one to that position.
• For example, if the first grade in our list is an "A", then each time an "A" is found the first slot in the frequency array is incremented by one.

for (studentPtr = 0; studentPtr < gradeBook.length; studentPtr++)
{
   var matched = false;
   var gradePtr = 0;

   while ((gradePtr < gradeList.length) && !matched)
   {
      if ( gradeBook[studentPtr] == gradeList[gradePtr] )
      {
         frequency [gradePtr] = frequency [gradePtr] + 1;
         matched = true;
      }
      else
      {
         gradePtr = gradePtr + 1;
      }
   }
}

Section 3: Sorting Parallel Arrays

Arrays are normally sorted using the array.sort() function.

One of the simplest types of sorts is the bubblesort.

In the following code, one will be adapted to handle parallel arrays.

• However, sorting parallel arrays is a bit more complex.
• When you rearrange the elements in one array, the corresponding elements in all parallel arrays must be rearranged as well.
• Therefore it is not possible to use array.sort().

//----------------------------------------------------------------------------------
// Compare the last item in the array with the item above it.
// If item n is smaller than item n-1, switch them.
// Compare item n-1 with item n-2.
// If item n-1 is smaller than item n-2, switch them.
// Compare item n-2 with item n-3.
// etc.
//
// Notes:
// 1. Since the largest element is put in its proper position on each pass,
// then the algorithm can consider one fewer elements on subsequent passes.
// In order to accomplish this, one can be added to the loop control variable i,
// and this sum can be used as the final value in a decrementing loop.
// The final value gets larger each pass.
// 2. The boolean "switch" is turned on only if a swap is made, and it stops the
// loop when no more swaps are made, reducing the number of iterations made.
//----------------------------------------------------------------------------------
function bubbleSort (arrayToSort, parallelArray1, order)
{
   var i = 0;
   var moreToSort = true;
   while ((order != "ascending") && (order != "descending"))
   {
      order = prompt("You must specify 'ascending' or 'descending': ", "ascending");
   }

   while ((i <= arrayToSort.length - 2) && moreToSort)
   {
      moreToSort = false;
      for (var j = arrayToSort.length-1; j >= i+1; j--)
      {
         if (order == "ascending")
         {
            if (arrayToSort[j] < arrayToSort[j - 1])
            {
               swap(arrayToSort, j, j - 1);
               swap(parallelArray1, j, j - 1);
               moreToSort = true;
            }
         }
         else // descending
         {
         if (arrayToSort[j] > arrayToSort[j - 1])
         {
            swap(arrayToSort, j, j - 1);
            swap(parallelArray1, j, j - 1);
            moreToSort = true;
         }
      }
   }
   i++;
   }
}

//----------------------------------------------------------------------------------
// Given an array and two indexes, swap the values. Nothing is returned except the modified array
// since arrays are passed by reference.
//----------------------------------------------------------------------------------
function swap ( arrayWithSwaps, one, two )
{
   var temp = arrayWithSwaps[one];
   arrayWithSwaps[one] = arrayWithSwaps[two];
   arrayWithSwaps[two] = temp;
}

If you wanted to sort an additional parallel array you could modify the lines in red:

• function bubbleSort (arrayToSort, parallelArray1, parallelArray2, order) // Add additional parameter for each parallel array
• swap(parallelArray1, j, j - 1);
• swap(parallelArray2, j, j - 1); // Add additional line for each parallel array

Parallel Array Demo