You are here:

# C++/Searching and Sorting Array Problem

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;
}

[Note: I am not going to show too much C++ code here as I am sure you notice I do not write code for you and of course you were good enough not to ask me to - thanks]

OK the _first_ thing to do is Don't Panic.

Next is to make sure you really understand the requirements. In larger projects this may not necessarily happen easily or in one go. However in this instance the whole of the requirements are stated in the question.

So make sure you have read the question very, very carefully - several times probably!

Have you noticed for instance that in this case there is _no_ requirement to (necessarily) store the raw input data?

Have you also noticed that you can have only up to 100 entries and that they are terminated by a value of -999 - I see nowhere in your code that indicates you even noticed these points.

The reason for the only up to 100 entries and that the user is to specify a special end of data value is to make it _easy_ for you the student. You do not have to bother with working out in advance how many questions there are and sizing an array to suit - something I am sure you found you cannot do with the C/C++ you have already - yes that is right I said C/C++ - your code is mostly C like with a thin veneer of C++ (use of std::cin and std::cout).

As an aside I do not see that either of your attempts actually compiled without error: you cannot define local or global arrays using a variable for the number of elements as you do in your attempts:

void TestScoreInput(int testScores)
{
int num = 0, tnum = 0, nLoop, tLoop, cLoop;
int iTestScore[testScores], telement, relement[testScores]; // BAD C and C++ - testScores is variable

This is because the compiler is responsible for arranging storage for such arrays and obviously it cannot do so if the number of elements is only known at runtime.

While I am here as you are not using command line arguments you could also use the variant of main that takes no arguments:

int main()
{
// ...
}

On the other hand I am not sure I am clear on what numbers are referred to by the last sentence:"The numbers must be output in increasing order". Which numbers - the mark values or the number of students attaining that mark? And if the latter should the mark value be output as well?

So initially what you require is a mapping of mark to number of students attaining that mark.

Next we need to sort these values, I am going to assume by number of students attaining each mark.

It is also probable that we do not loose the mark value in this process.

Finally, we need to output the resulting set of values.

We can break the problem down like so:

Input data from user
up to 100 positive integers entered as exam marks
-999 indicates end
Process data
require (mark,count) pairs sorted by count ascending
Output results to user

This then is a classic program structure: IPO - Input, Process, Output.

Notice that the form and comments come from the question. It is essential that you learn to break problems down into small easily handled parts. I notice that your attempts both have a function called TestScoreInput that does not _just_ do what it says it is more like InputTestScoresProcessAndOutputResults - it is doing too much.

So from the output and comments above we might try a program outline like so:

Main
Validate data
Process input data - create result data
Set counts
Sort by counts
Output result data

End.

Each of those lines could be a function (except End. at the end), although in this simplified top level scheme exactly when a function is called and with what is left for later - the function that handles Validate data for example would most likely be called for _each_ datum entered and not the data set as whole. You could create the data structures (probably arrays in this case) you need in main at the point you require them and pass them into (and out of) functions as required. Note that C and C++ do _not_ allow arrays as return types.

Now there are various ways we can tackle the details of this problem.

For example if we know that the exam marks are in the range 0 to 100 then maybe be could just create an array of mark counts where each element represents one mark and its value is the number of students that attained that mark. Initially all elements would be zero and on reading each mark from the user - after validating they are valid integers in range and not the end-of-data value - we just use the entered mark as an index into this array and increment that element's value, the idea in rough pseudo-code showing just this facet is:

If ( Validate(mark)==OK )
Increment markCounts[mark]
End If

Now we could apply a sort to this markCounts array but in doing the count values will be re-arranged and so we effectively loose the association between mark value (the index into the array) and count of students attaining that mark. So if all that were required were the count values output in order this would suffice. However, if we needed to also show which mark was associated with that count of students attaining it then we need to think of something else. Now I hope you see why having a very clear understanding of what is required is essential.

We could use a second array as an index into the first (maybe called something like sortedIndex) that contains as values mark values. These values are in fact index values into the markCounts array. We initially order the values so that sortedIndex[i] = i. That is every value in the sortedIndex array has a value the refers to the equivalent entry in the markCounts array. We then apply a sort on this array but use the value of markCount[sortedIndex[i]] as the values - i.e. the mark count values.

The idea is to leave the markCounts array untouched and instead sort - which swaps values - references to the values in a second array.

Let us look at a simple 3 value example:

markCounts[0] = 3
markCounts[1] = 5
markCounts[2] = 1

We want to be able to output something like:

1 student  attained 2 marks
3 students attained 0 marks
5 students attained 1 mark

If we just sort the markCounts array we get:

markCounts[0] = 1
markCounts[1] = 3
markCounts[2] = 5

And the output would be

1 student  attained 0 marks
3 students attained 1 marks
5 students attained 2 mark

Because by swapping around the values we destroy the information of which mark went with which count.

So we introduce a second array thus:

markCounts[0] = 3 <- sortedIndex[0] = 0
markCounts[1] = 5 <- sortedIndex[1] = 1
markCounts[2] = 1 <- sortedIndex[2] = 2

So for example markCount[sortedIndex[0]] = 3 initially

We then sort on the values in markCount but modify the values in the sortedIndex array:

markCounts[0] = 3 <- sortedIndex[1] = 0
markCounts[1] = 5 <- sortedIndex[2] = 1
markCounts[2] = 1 <- sortedIndex[0] = 2

Or in increasing order of sortedIndex index values:

sortedIndex[0] = 2 -> markCounts[2] = 1
sortedIndex[1] = 0 -> markCounts[0] = 3
sortedIndex[2] = 1 -> markCounts[1] = 5

We then loop through the sorted index array printing out something like so:

std::cout << markCounts[ sortedIndex[i] ]
<< " students attained "
<< sortedIndex[i]
<< " marks\n"
;

This of course is just one way to approach the problem - and relies on a nice small finite range of valid positive integer mark values. If marks in the range of say 0 to 2,000,000,000 were valid then we would need to think again.

Here is another take on the problem using the facilities of the C++ standard library containers, specifically sorted associative container types - maps and multimaps. I do not expect you to understand it all immediately but I thought you might like to look at a solution using more C++ styles and facilities.

#include <iostream>
#include <ios>
#include <map>
#include <limits>
#include <utility>

// Type-alias for mapping of marks to counts. In this mapping marks are
// unique keys and the counts are the values - which need not be unique.
typedef std::map<unsigned int, unsigned int> MarkCountsMap;

// Reverse counts to marks mapping. This has to be a multimap because in
// this case the keys (the counts) are NOT unique. That is we can have
// many marks with the same count.
typedef std::multimap<unsigned int, unsigned int> CountsMarkMap;

unsigned int const MaxMarks(100);
unsigned int const MinMarkValue(0);
unsigned int const MaxMarkValue(100);

int const EndOfDataValue(-999);

bool Validate( std::istream const & in, int value )
{
bool ok( true ); // all good until shown otherwise

if ( in.eof() )
{
throw std::ios_base::failure("unexpectedly at end of file");
}
if ( in.fail() )
{
{
throw std::ios_base::failure("in an unrecoverable bad state");
}
ok = false;
}
else
{
ok = (value>=MinMarkValue && value<=MaxMarkValue) || value==EndOfDataValue;
}
if (!ok)
{
std::cerr << "Expected a positive integer between " << MinMarkValue
<< " and " << MaxMarkValue << " or " << EndOfDataValue
<< std::endl
;
}
return ok;
}

void GetMarkCounts( MarkCountsMap & mc )
{
unsigned int marksCount(1);
int rawValue(0);
do
{
std::cout << "Enter mark value or " << EndOfDataValue << " to stop ("
<< marksCount << " of upto " << MaxMarks << "): "
;
std::cin >> rawValue;
if ( !Validate(std::cin, rawValue) )
{
--marksCount;     // discount this bad entry.
std::cin.clear(); // clear all flags (including fail flag)
std::cin.ignore
( std::numeric_limits<int>::max()
, '\n'
);      // ignore rest of line
}
else if ( rawValue != EndOfDataValue )
{
mc[static_cast<unsigned int>(rawValue)] += 1;
}
}
while ( marksCount++ < MaxMarks && rawValue != EndOfDataValue );
}

void CreateCountsMarkMapping( CountsMarkMap & cm, MarkCountsMap const & mc )
{
MarkCountsMap::const_iterator  position(mc.begin());
MarkCountsMap::const_iterator  finish(mc.end());
for(; position!=finish; ++position )
{
// We can dereference iterator positions like pointers
// In the case of C++ standard library maps this returns a reference to a
// pair object with the first item being the key and the second the value.
// We use these to create the entry in the reverse-mapping of counts to marks
cm.insert( std::make_pair(position->second,position->first) );
}
}

void DisplayCountsForMarks( CountsMarkMap const & cm )
{
CountsMarkMap::const_iterator  position(cm.begin());
CountsMarkMap::const_iterator  finish(cm.end());
for(; position!=finish; ++position )
{
unsigned int count(position->first);
unsigned int mark(position->second);
std::cout << count << ( count!=1 ? " students " : " student " )
<< "attained "
<< mark << ( mark!=1 ? " marks.\n" : " mark.\n" )
;
}
}

int main()
{
MarkCountsMap markCounts;
CountsMarkMap countsMarks;
try
{
GetMarkCounts( markCounts );
CreateCountsMarkMapping( countsMarks, markCounts );
DisplayCountsForMarks( countsMarks );
}
catch ( std::ios_base::failure & e )
{
std::cerr << "Mark reading input stream is " << e.what()
<< ". Exiting." << std::endl
;
}
catch (...)
{
std::cerr << "Unanticipated error occurred. Exiting." << std::endl;
}
}

Hope this has given you some ideas at least and maybe a little idea of how to break down a problem towards a solution.

C++

Volunteer

#### Ralph McArdell

##### Expertise

I am a software developer with more than 15 years C++ experience and over 25 years experience developing a wide variety of applications for Windows NT/2000/XP, UNIX, Linux and other platforms. I can help with basic to advanced C++, C (although I do not write just-C much if at all these days so maybe ask in the C section about purely C matters), software development and many platform specific and system development problems.

##### Experience

My career started in the mid 1980s working as a batch process operator for the now defunct Inner London Education Authority, working on Prime mini computers. I then moved into the role of Programmer / Analyst, also on the Primes, then into technical support and finally into the micro computing section, using a variety of 16 and 8 bit machines. Following the demise of the ILEA I worked for a small company, now gone, called Hodos. I worked on a part task train simulator using C and the Intel DVI (Digital Video Interactive) - the hardware based predecessor to Indeo. Other projects included a CGI based train simulator (different goals to the first), and various other projects in C and Visual Basic (er, version 1 that is). When Hodos went into receivership I went freelance and finally managed to start working in C++. I initially had contracts working on train simulators (surprise) and multimedia - I worked on many of the Dorling Kindersley CD-ROM titles and wrote the screensaver games for the Wallace and Gromit Cracking Animator CD. My more recent contracts have been more traditionally IT based, working predominately in C++ on MS Windows NT, 2000. XP, Linux and UN*X. These projects have had wide ranging additional skill sets including system analysis and design, databases and SQL in various guises, C#, client server and remoting, cross porting applications between platforms and various client development processes. I have an interest in the development of the C++ core language and libraries and try to keep up with at least some of the papers on the ISO C++ Standard Committee site at http://www.open-std.org/jtc1/sc22/wg21/.

Education/Credentials