You are here:

C++/Sorting and Searching Array Problem

Advertisement


Question
QUESTION: My name is Ernest. I am trying to teach myself C++. I am currently working on a C++ problem that I found on the internet. It involves sorting and searching through arrays. Furthermore, I am having trouble solving the problem. I have spent a week on it. All I can say is that I am confused. My brain hurts! However, C++ is addictive to me I cant let it go. I was wondering if you could please steer me in the right direction; moreover, tell me what is going on in your mind as you solve the problem? How do you organize it in your mind and how you look at it? The C++ problem description is as follows:

Write a program that reads in a set of positive integers, representing test scores for a class, and outputs how many times a particular number appears in the list. You may assume that the data set has at most 100 numbers and -999 marks the end of the input data. The numbers must be output in increasing order.

Finally, below are my failed endeavors to solve this problem.

Attempt 1:

#include <cstdlib>
#include <iostream>

using namespace std;
void TestScoreInput(int);


int main(int argc, char *argv[])
{
  int nTest;
  cout << "Please input the number of testscores: ";
  cin  >> nTest;

  TestScoreInput(nTest);

  system("PAUSE");
  return EXIT_SUCCESS;
}

void TestScoreInput(int testScores)
{

         int num = 0, tnum = 0, nLoop, tLoop, cLoop;
         int iTestScore[testScores], telement, relement[testScores];
         int tScoreStore[testScores];

         for(nLoop = 0; nLoop < testScores; nLoop++)
         {
         num = num + 1;
         cout << "Enter testscore " << num <<":";
         cin  >> iTestScore[nLoop];
         }

         for(tLoop = 0; tLoop < testScores; tLoop++)
         {
         for(cLoop = 0; cLoop < testScores; cLoop++)
         {
         if(iTestScore[tLoop] == iTestScore[cLoop])
         {
         tnum = tnum + 1;
         }
         if(tnum == 1)
         {
         tScoreStore[tLoop] = iTestScore[cLoop];
         }
         }
         relement[tLoop] = tnum;
         tnum = 0;
         }

         cout <<"n"<<endl;
         cout  <<"Test Scores   Count"<<endl;
         for(tLoop = 0; tLoop < testScores; tLoop++)
         {
         cout  <<"     "<<tScoreStore[tLoop]<<"         "<<relement[tLoop]<<endl;
         }
         return;
}



Attempt 2:

#include <cstdlib>
#include <iostream>

using namespace std;

void TestScoreInput(int);
void deleteElement(int arr[], int%26 size, int position);

int main(int argc, char *argv[])
{
  int nTest;
  cout << "Please input the number of testscores: ";
  cin  >> nTest;

  TestScoreInput(nTest);

  system("PAUSE");
  return EXIT_SUCCESS;
}

void TestScoreInput(int testScores)
{

         int num = 0, tnum = 0, nLoop, tLoop, cLoop;
         int iTestScore[testScores], relement[testScores];
         int tScoreStore[testScores], eTestScores[testScores];

         for(nLoop = 0; nLoop < testScores; nLoop++)
         {
         num = num + 1;
         cout << "Enter testscore " << num <<":";
         cin  >> iTestScore[nLoop];
         }

         num = 0;

         for(nLoop = 0; nLoop < testScores; nLoop++)
         {
         tScoreStore[nLoop] = 0;
         }

         for(nLoop = 0; nLoop < testScores; nLoop++)
         {
         eTestScores[nLoop] = iTestScore[nLoop];
         }

         for(tLoop = 0; tLoop < testScores; tLoop++)
         {
         for(cLoop = 0; cLoop < testScores; cLoop++)
         {
         if(iTestScore[tLoop] == eTestScores[cLoop])
         {
         tScoreStore[tLoop] = iTestScore[tLoop];
         deleteElement(iTestScore, testScores, tLoop);
         deleteElement(eTestScores, testScores, cLoop);

         tnum = tnum + 1;
         }

         }

         relement[tLoop] = tnum;
         tnum = 0;
         }

         cout << " ";
         cout << "Test Score" <<" "<<"Count" << endl;
         for(nLoop = 0; nLoop < testScores; nLoop++)
         {
         cout << "    "<< tScoreStore[nLoop] <<"     "<<"    "<< relement[nLoop]<<endl;
         }
         return;
}
void deleteElement(int arr[], int%26 size, int position)
{
         int k;

         if(position >= size)
         {
         cout << "Error! You are attempting to delete an element beyone the size of the array";
         }
         else
         {
         for(k = position; k < size - 1; k ++)
         {
         arr[k] = arr[k+1];
         --size;
         }
         }
         return;
}

ANSWER: Hello Ernest.

I really appreciate you making an attempt at solving the problem. It shows you are serious, and have a good work ethic. It is also good for you as a programmer. However, if you don't mind, I will not look at your solutions too closely.

Sometimes you need to step back from a problem and think about it a different way. You are counting simple numbers. You are not associating the numbers with any other data, like student names. You know you are dealing with test scores so you can make assumptions about the kind of numbers you are counting. They will be between 0 and some reasonable value, usually 100, of 150 or 200. Lets say that we can assume a reasonable maximum test score. Call it MAX_ALLOWED_SCORE. Now the problem becomes quite straightforward.

Create an array of (MAX_ALLOWED_SCORE+1) integers. The index into the array is the score, and the contents of an array element is the count for that score. The array can even be of type unsigned char since you know that there will be at most 100 tests, so no count can be greater than 100.

Don't forget to initialize the array to all 0.
Put in some error checking to ensure that every score entered is <= MAX_ALLOWED_SCORE.
Choose MAX_ALLOWED_SCORE to be sufficiently high, like 1000.

When all inputs are done, go through the array, starting at element 0, and print out all non-zero elements. Your test scores will automatically be in ascending order.

I first read about this in the book "Programming Pearls" by Jon Bently. See http://www.cs.bell-labs.com/cm/cs/pearls/

What you need to do is read as much as you can about algorithms, design patterns, and general programming wisdom like that book. If you are going to be a programmer, don't stop you learning when you leave school.

Best regards
Zlatko.

---------- FOLLOW-UP ----------

QUESTION: I understand that I must associate students names with my test scores. How I can count the number of repeat numbers and remove the repeat numbers?

Answer
Hello Ernest.

I'm not sure I understand the problem, especially since you did not have processing of student names in your two attempts. You should post the exact text of your assignment so that I don't lead you down the wrong path. From what you describe, you need to associate a list of students with a mark, and the marks should not duplicate.

I get the feeling you're not quite satisfied with my first answer and you'd really like to see the removal of repeats.

Ok, to make things easier, you should divide the program into phases, and conquer each one in a separate function. First, do the input, then sort the input array. A sorted array will be much easier to work with. Then count the number of unique scores, placing the unique scores into another array. Then do the output. You asked for my thought process. The first thought is divide and conquer. Here is the main program featuring division of labour into functions.

int main(void)
{
#   define MAX_SCORES 100

   int scores[MAX_SCORES];
   int uniqScores[MAX_SCORES];
   int counts[MAX_SCORES];

   int inputCount;
   int uniqCount;
   
   // Step 1 input
   inputCount = input(scores, MAX_SCORES);
   // Step 2 sort
   sort(scores, inputCount);
   // Step 3 condense
   uniqCount = uniq(scores, uniqScores, counts, inputCount);
   // Step 4 output
   output(uniqScores, counts, uniqCount);
}

My sort routine is a simple bubble sort:

// A simple bubble sort
void sort(int data[], int length)
{
  int end = length - 1;
  for (int i = 0; i < length; ++i)
  {
      for (int j = 0; j < end; ++j)
      {
         if (data[j] > data[j+1])
         {
         int tmp = data[j];
         data[j] = data[j+1];
         data[j+1] = tmp;
         }
      }
      --end;
  }
}

The tricky part is the uniq function. It takes an array of sorted scores, and puts unique scores into uniqScores and the counts into the counts array.


Consider the sorted scores array:
1 2 2 3 4 5 5 7 9 9
It helps to draw it out as a diagram. A diagram helps the thought process.

You can imagine traversing the array. As you move to a new number, if the number changes, you need to move to a fresh spot on the uniq array, move the number into the fresh spot, set the count to 1. If the number is the same as the previous, you need to simply increment the count in the count array.

Here is the uniq function, followed by the output function:

/*
uniq, takes a scores array as input, and outpus into uniqScores, and counts.
The inputCount is the amount of data in the scores array.
The function returns the number of unique scores.
*/
int uniq(int scores[], int uniqScores[], int counts[], int inputCount)
{
   /*
       We have 2 indicies into the arrays. The scoresIx, indexes the scores array,
       the uniqIx indexes the uniqScores array, and the counts array.
       You have to make sure you match up the indicies with their arrays correctly.
   */
   int uniqIx = -1;
   int scoresIx = 0;
   int currentScore = -1;

   while(scoresIx < inputCount)
   {
       if (currentScore != scores[scoresIx])
       {
         ++uniqIx;
         currentScore = scores[scoresIx];
         uniqScores[uniqIx] = currentScore;
         counts[uniqIx] = 1;
       }
       else
       {
         ++counts[uniqIx];
       }
       ++scoresIx;
   }
   return uniqIx+1;
}

How did I know to start uniqIx at -1? I didn't. Initially I had it at 0, but in tracing through it with the debugger, I saw that it was wrong. That's another technique. Make something that seems close, then watch it run step by step and see where it deviates from your assumptions.

I hope that helps. Follow up if you need to.
Best regards
Zlatko

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Zlatko

Expertise

No longer taking questions.

Experience

No longer taking questions.

Education/Credentials
No longer taking questions.

©2016 About.com. All rights reserved.