1,105,288 Community Members

NEED HELP! Dynamic Array and Couting Sort Algorthim C++

Member Avatar
Ptap03
Newbie Poster
8 posts since Sep 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Hello, I'm new to this thread but have referenced to it before many times. I have finally joined thanks to all the great responses I have read in the past.

Okay, I recieved an assignment which is as follow...

"Declare a dynamic array of Person to store the information of each student. Implement a simple user interface that allows the enduser of your program to: (1) type in the total number of students at runtime from the keyboard; and (2) provide the specific value of every data member for each student. Then implement the counting sort algorithm to sort all the students in increasing order of age. You can assume a personʼs age is an integer and within a small interval, say, 15--90. For comparison purpose, print out the unsorted array before calling the sorting procedure and the sorted one after.

Note: Person is implemented as a struct and consists of: firstname, lastname, age,
birthdate, and salary.

birthdate is of type date which is implemented as a struct and consists of:
day, month, and year.

-----------------------------------------------------------------------------------------
My code this is what I have done so far

/******************************************************************************
                            Person Header File
*******************************************************************************/

#ifndef _PERSON_H
#define _PERSON_H

#include<iostream>
#include<string>

using namespace std;

struct Date {
       unsigned short day;                        //1-31
       unsigned short month;                      //1-12
       int year;
};

struct Person {
       string fname;                             //first name
       string lname;                             //last name
       unsigned short age;                       //person's age
       Date birthDay;                            //mm/dd/year
       double salary;                            //person's salary
};

Person init_Person(string& fname, string& lname,
                           unsigned short& age, Date& bdate, double& salary);
#endif

/******************************************************************************
                            Person Implementation File
*******************************************************************************/

#include "Person.h"

//Description: implementation of init_Person.  Initialize a Person object
Person init_Person(string& fname, string& lname,
                           unsigned short& age, Date& bdate, double& salary)
{
     Person someone;                      //someone is object of Person
     someone.fname = fname;
     someone.lname = lname;
     someone.age = age;     
     someone.birthDay.day = bdate.day;
     someone.birthDay.month = bdate.month;
     someone.birthDay.year = bdate.year;
     someone.salary = salary;     
     return someone;
}//end-of-init_Person(...)

/******************************************************************************
                            Person Test-Main File
*******************************************************************************/

#include "Person.h"

int main()
{
    string yourName;                               //Stores the name of the user
    int stuNum;                                    //Stores the # of students
    cout << "Please enter your name: ";
    getline(cin,yourName);
    cout << "Welcome, " << yourName << "!" << endl
         << "Please enter the number of students: ";
    cin >> stuNum;
    cout << endl;
    
    Person *darrPer;
    darrPer = new Person[stuNum];                 //Dynamic array of type person
    int i;                                        //Index of the dynamic array
    for(i = 0; i < stuNum; i++)
    {
          string firNam, lasNam;           //User entered data
          unsigned short ageOld;
          Date burDay;
          double salMon;
          
          cout << "Enter the first name: ";
          cin >> firNam;
          cout << "Enter the last name: ";
          cin >> lasNam;
          cout << "Enter the age: ";
          cin >> ageOld;          
          cout << "Enter the birth day: ";
          cin >> burDay.day;
          cout << "Enter the birth month: ";
          cin >> burDay.month;
          cout << "Enter the birth year: ";
          cin >> burDay.year;          
          cout << "Enter the salary: ";
          cin >> salMon;
          darrPer[i] = init_Person(firNam,lasNam,ageOld,burDay,salMon);
          cout << "\n" << endl;
    }
    
    //**************************THIS IS WHERE THE PROBLEM OCCURS*******************//
    for(i = 0; i < stuNum; i++)
          cout << darrPer[i] << endl;
    
    
    int k = 90;     //Assumed age range max at 90 in description of the problem.
    int j;
    Person *tempPer, *sortPerAge;
    tempPer = new Person[stuNum];
    for(i = 0; i < k; i++)
          tempPer[i] = 0;
    for(j = 1; j < stuNum; j++)
          tempPer[darrPer.age[j]] = tempPer[darrPer.age[j]] + 1;
    for(i = 1; i < k; i++)
          tempPer[i] = tempPer[i] + tempPer[i-1];
    for(j = stuNum; j > 0; j--)
    {
          sortPerAge[tempPer[darrPer.age[j]]] = darrPer.age[j];
          tempPer[darrPer.age[j]] = tempPer[darrPer.age[j]] - 1;          
    } 
    
    delete [] sortPerAge;
    delete [] tempPer;
    delete [] darrPer;
    return 0;
}//end-of-main()

Okay the error(s) I get from the compiler:

1)test-MainPerson.cpp no match for 'operator<<' in 'std::cout << *((+(((unsigned int)i) * 32u)) + darrPer)

2)Dev-Cpp\include\c++\3.4.2\bits\ostream.tcc:63 candidates are: std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(std::basic_ostream<_CharT, _Traits>&(*)(std::basic_ostream<_CharT, _Traits>&)) [with _CharT = char, _Traits = std::char_traits<char>]

3):\Dev-Cpp\include\c++\3.4.2\bits\ostream.tcc:63 std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(std::basic_ios<_CharT, _Traits>&(*)(std::basic_ios<_CharT, _Traits>&)) [with _CharT = char, _Traits = std::char_traits<char>]
.
.
.
.
.
The errors continue. Way too many.
Any insight will be greatly appreciated.

Member Avatar
VernonDozier
Posting Expert
5,632 posts since Jan 2008
Reputation Points: 2,218 [?]
Q&As Helped to Solve: 768 [?]
Skill Endorsements: 26 [?]
Featured
 
0
 

I don't see a << operator for your class. You need one. There are some good threads on the subject on Daniweb. Here's one.

http://www.daniweb.com/forums/thread137909.html

Member Avatar
Ptap03
Newbie Poster
8 posts since Sep 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

I don't see a << operator for your class. You need one. There are some good threads on the subject on Daniweb. Here's one.

http://www.daniweb.com/forums/thread137909.html

Is that overloading the << operator? Because we haven't learned that in class so we can't overload operators.

Member Avatar
VernonDozier
Posting Expert
5,632 posts since Jan 2008
Reputation Points: 2,218 [?]
Q&As Helped to Solve: 768 [?]
Skill Endorsements: 26 [?]
Featured
 
0
 

Is that overloading the << operator? Because we haven't learned that in class so we can't overload operators.

Yes, it's overloading the operator. If you can't overload the << operator then you can't have lines like this:

cout << darrPer[i] << endl;

So I guess you'll want a Display() function for your class and call it like this:

darrPer[i].Display();
Member Avatar
Ptap03
Newbie Poster
8 posts since Sep 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Yes, it's overloading the operator. If you can't overload the << operator then you can't have lines like this:

cout << darrPer[i] << endl;

So I guess you'll want a Display() function for your class and call it like this:

darrPer[i].Display();

Thanks for replying. I will go try out your suggestion and get back on here asap.
Wait the Display() what contents should be included? What's the return type? Void?

void Display()
{
     cout << "First name: " << fname << endl
          << "Last name: " << lname << endl
          //so on

}
Member Avatar
Ptap03
Newbie Poster
8 posts since Sep 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Okay so what I did was include a void Display(); in header file (Not inside the struct Person) I then typed in the definition (given below) into the implementation file. But I got a compile error which stated fname undeclared first use this function.

void Display()
{
     cout << "First Name: " << fname << endl;
     cout << "Last Name: " << lname << endl
          << "Social Security Number: " << ssn << endl
          << "Age: " << age << endl
          << "Birthday: " << birthDay.day << "/"
          << birthDay.month << "/" << birthDay.year << endl
          << "Salary: " << salary << endl;     
}//end-of-Display()

I tried to fix the error above by place "Person." infront of fname and the rest. So for example I changed fname to Person.fname. But this then gave me error: expected primary function before '.' token

Also, I noticed that you use class even though it is a struct. Are the two the same thing? Also, we have not covered any material on classes yet in the class.

What am I doing wrong?

Member Avatar
VernonDozier
Posting Expert
5,632 posts since Jan 2008
Reputation Points: 2,218 [?]
Q&As Helped to Solve: 768 [?]
Skill Endorsements: 26 [?]
Featured
 
0
 

You seem like you are coming from a C background? Classes and structs are the same thing except that structs default to "public" and classes default to "private". For your purposes here, you can use struct and class as synonyms. I guess I wasn't paying attention to the fact that you had it as a struct.


Display() is usually a void function, as you have it.

But the difference is that you aren't really using the full power of a C++ struct, but are rather using it more like a C struct. In C, structs are used to store data and that's it. In C++ they have constructors, destructors, operators, and other functions. It's a different approach, one that you aren't using (i.e. you don't have any constructors. You have an "init_Person" function).


So my advice would be either continue on with the way you're doing it or convert what you have so far to the "normal" C++ way, THEN start tackling the Display function.

If you continue in the style you are using, you won't use the dot(.) or arrow (->) or operators when calling functions, but you'll do this:

struct Person {
string fname; //first name
string lname; //last name
unsigned short age; //person's age
Date birthDay; //mm/dd/year
double salary; //person's salary
};

void Display(const Person& person);  // note this is OUTSIDE of the struct


void Display(const Person& person)
{
   // implementation
}

If you were doing things the Object oriented way, it would look more like this:

struct Person {
string fname; //first name
string lname; //last name
unsigned short age; //person's age
Date birthDay; //mm/dd/year
double salary; //person's salary

void Display();  // note this is INSIDE of the struct

};



void Person::Display()
{
   // implementation
}

Presuming you do it the FIRST way, you'd do this:

Person person;
Display(person);

Two styles, the first more C-like and the second more Object oriented/C++ like. If you stick with C++, most likely you'll migrate to the second way. If the second way is all new to you and you want to go with that, I'd take a few tutorials and get the hang of it, then come back to the assignment. The difference is that C has no "member functions" of a struct/class and C++ does. The "::" denotes that it is a member function and is PART of the class (hence my "inside" versus "outside" comment).

Member Avatar
Ptap03
Newbie Poster
8 posts since Sep 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

VernonDozier

Thanks for your replies. I did get the display to work properly; however now i'm having trouble with the sort alog. This assignment was due last week so I have already turnted in what I had but I would like to continue our discussion so I can understand the sort alg. as well. At the moment I have assembly project due so I'm working on that. Again, Thanks.

Member Avatar
Ptap03
Newbie Poster
8 posts since Sep 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Again, thank you for your help.

I added the display function to the struct and implemented it using the following in the implementation file

void Person::Display()
{
     cout << "First Name: " << fname << endl
          << "Last Name: " << lname << endl
          << "Social Security Number: " << ssn << endl
          << "Age: " << age << endl
          << "Birthday: " << birthDay.day << "/"
          << birthDay.month << "/" << birthDay.year << endl
          << "Salary: " << salary << endl;     
}//end-of-Display()

This worked perfectly. Now my next problem is when I use the sort algorthim I do not get the proper result. Let me post the alg.

//This alg. is in main()
//Sort person by age

//stuNum is number of students entered by the user at runtime.
//i and j are used to keep track of index    
    int k = 90;     //Assumed age range max at 90 in description of the problem.
    int j;
    unsigned short tempPer[k], sortPerAge[stuNum];
    for(i = 0; i < k; i++)
          tempPer[i] = 0;
    for(j = 1; j < stuNum; j++)
          tempPer[darrPer[j].age] = tempPer[darrPer[j].age] + 1;
    for(i = 1; i < k; i++)
          tempPer[i] = tempPer[i] + tempPer[i-1];
    for(j = stuNum; j > 0; j--)
    {
          sortPerAge[tempPer[darrPer[j].age]] = darrPer[j].age;
          tempPer[darrPer[j].age] = tempPer[darrPer[j].age] - 1;          
    }
    
    for(i = 0; i < stuNum; i++)
          cout << sortPerAge[i] << ", " << endl;

-----------------------------------------------------------------------------------------
The output when I run this code:
COMMENT: I added the SSN field... A minor change
OUTPUT:

Please enter your name: Chris Redfield
Welcome, Chris Redfield!
Please enter the number of students: 3

Enter the first name: Lora
Enter the last name: Craft
Enter the social security number: 123456789
Enter the age: 26
Enter the birth day: 08
Enter the birth month: 08
Enter the birth year: 1984
Enter the salary: 150000


Enter the first name: Jill
Enter the last name: Valentine
Enter the social security number: 987654321
Enter the age: 25
Enter the birth day: 08
Enter the birth month: 08
Enter the birth year: 1985
Enter the salary: 200000


Enter the first name: Crash
Enter the last name: Bandicooooooot
Enter the social security number: 543216789
Enter the age: 27
Enter the birth day: 08
Enter the birth month: 08
Enter the birth year: 1983
Enter the salary: 100000


First Name: Lora
Last Name: Craft
Social Security Number: 123456789
Age: 26
Birthday: 8/8/1984
Salary: 150000
First Name: Jill
Last Name: Valentine
Social Security Number: 987654321
Age: 25
Birthday: 8/8/1985
Salary: 200000
First Name: Crash
Last Name: Bandicooooooot
Social Security Number: 543216789
Age: 27
Birthday: 8/8/1983
Salary: 100000

4,
25,
27,

-----------------------------------------------------------------------------------------
As you can see the sort is not working properly. 4, 25, 27 are not in the proper order matter fact 4 is not even an age. The ages I entered are 4, 25, 27. What am I doing wrong?

Thanks

Member Avatar
kes166
Practically a Master Poster
645 posts since Aug 2010
Reputation Points: 37 [?]
Q&As Helped to Solve: 32 [?]
Skill Endorsements: 0 [?]
 
0
 

When you create the new person from your Op post

tempPer = new Person[stuNum];

Using your example, you create 3 objects: 0, 1, 2. In your for loops

for(j = 1; j < stuNum; j++)
          tempPer[darrPer[j].age] = tempPer[darrPer[j].age] + 1;
 for(i = 1; i < k; i++)
          tempPer[i] = tempPer[i] + tempPer[i-1];
 for(j = stuNum; j > 0; j--)    {
          sortPerAge[tempPer[darrPer[j].age]] = darrPer[j].age;
          tempPer[darrPer[j].age] = tempPer[darrPer[j].age] - 1;
 }

You never reference tempPer[0]. I'm not sure if the for loops are doing exactly what you want, so I will try to break down what each loop is doing.

for(j = 1; j < stuNum; j++)
   tempPer[darrPer[j].age] = tempPer[darrPer[j].age] + 1;

[darrPer[j].age] is going to be darrPer[1].age which in your examples case will be 25, Jills age, which makes tempPer[25] = tempPer[25] + 1. I'm not sure what that does, and I'm surprised that line doesn't give an error or a warning. The second iteration, it will reference tempPer[27]. Basically, this for loop does nothing with memory that is in bounds.

for(i = 1; i < k; i++)
   tempPer[i] = tempPer[i] + tempPer[i-1];

this will set tempPer[1] = tempPer[1] + tempPer[0] in the first pass
then tempPer[2] = tempPer[2]+tempPer[1]
...
finally tempPer[89] = tempPer[89] + tempPer[88]

Again, I'm not sure what you are trying to accomplish here.

In the last loop

for(j = stuNum; j > 0; j--)    {
          sortPerAge[tempPer[darrPer[j].age]] = darrPer[j].age;
          tempPer[darrPer[j].age] = tempPer[darrPer[j].age] - 1;
              }

in the first pass, darrPer[j].age = darrPer[3].age = unknown because darrPer[3] doesn't exist.

The second pass, darrPer[2].age = 27. tempPer[27] = unknown
So we have sortPerAge[unkwown]

The third pass, darrPer[1].age = 25. Again, you will reference an unknown with sortPerAge.

darrPer[0] will never be touched because the for loops states j > 0. Ironically enough, your output is 4, 25, 27. 4 I'm assuming is a random value and 25, 27 may be garbage values as well, or some how related to the darrPer[1].age and darrPer[2].age.

Member Avatar
Ptap03
Newbie Poster
8 posts since Sep 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

When you create the new person from your Op post

tempPer = new Person[stuNum];

Using your example, you create 3 objects: 0, 1, 2. In your for loops

for(j = 1; j < stuNum; j++)
          tempPer[darrPer[j].age] = tempPer[darrPer[j].age] + 1;
 for(i = 1; i < k; i++)
          tempPer[i] = tempPer[i] + tempPer[i-1];
 for(j = stuNum; j > 0; j--)    {
          sortPerAge[tempPer[darrPer[j].age]] = darrPer[j].age;
          tempPer[darrPer[j].age] = tempPer[darrPer[j].age] - 1;
 }

You never reference tempPer[0]. I'm not sure if the for loops are doing exactly what you want, so I will try to break down what each loop is doing.

for(j = 1; j < stuNum; j++)
   tempPer[darrPer[j].age] = tempPer[darrPer[j].age] + 1;

[darrPer[j].age] is going to be darrPer[1].age which in your examples case will be 25, Jills age, which makes tempPer[25] = tempPer[25] + 1. I'm not sure what that does, and I'm surprised that line doesn't give an error or a warning. The second iteration, it will reference tempPer[27]. Basically, this for loop does nothing with memory that is in bounds.

for(i = 1; i < k; i++)
   tempPer[i] = tempPer[i] + tempPer[i-1];

this will set tempPer[1] = tempPer[1] + tempPer[0] in the first pass
then tempPer[2] = tempPer[2]+tempPer[1]
...
finally tempPer[89] = tempPer[89] + tempPer[88]

Again, I'm not sure what you are trying to accomplish here.

In the last loop

for(j = stuNum; j > 0; j--)    {
          sortPerAge[tempPer[darrPer[j].age]] = darrPer[j].age;
          tempPer[darrPer[j].age] = tempPer[darrPer[j].age] - 1;
              }

in the first pass, darrPer[j].age = darrPer[3].age = unknown because darrPer[3] doesn't exist.

The second pass, darrPer[2].age = 27. tempPer[27] = unknown
So we have sortPerAge[unkwown]

The third pass, darrPer[1].age = 25. Again, you will reference an unknown with sortPerAge.

darrPer[0] will never be touched because the for loops states j > 0. Ironically enough, your output is 4, 25, 27. 4 I'm assuming is a random value and 25, 27 may be garbage values as well, or some how related to the darrPer[1].age and darrPer[2].age.

Thanks for replying

Well the objective was to create a sort alg. to sort all objects of Person by age. And obviously my understanding of counting sort alg. is flawed. Let me post the base I used to create the alg.

COUNTING-SORT
/*A is what we are sorting. C is a temp Array with range of
values of A(0..k) as index of A. B is the sorted A*]
1. let c[0..k] be a new array
2. for i = 0 to k
3. c = 0
4. for j = 1 to A.length
5. C[A[j]] = C[A[j]] + 1
6. // C now contains the number of elements equal to i
7. for i = 1 to k
8. C = C + C[i-1]
9. //C now contains the number of elements less than or equal to i
10.for j = A.length downto 1
11. B[C[A[j]]] = A[j]
12. C[A[j]] = C[A[j]] - 1

After the for loop of lines 2-3 initializes the array C to all zeros,
the for loop of lines 4-5 inspects each input element. If the value of
an input element is i, we increment C. Thus after line 5, C holds
the number of input elements equal to i for each integer i = 0,1.... k.
Line 7-8 determine for each i = 0,1.....k how many input elements are less
than or equal to i by keeping a running sum of array C. Finally, the for
loop of lines 10-12 place each element A[j] into its correct sorted position
in the ouput array B. If all n elements are distinct, then when we first enter
line 10, for each A[j], the value C[A[j]] is the correcct final position of
A[j]. Because the elements might not be distinct, we decrement C[A[j]] each
time we place a value A[j] into the B array.

HERE IS AN EXAMPLE OF VALUE OF K
int a[] = {7, 5, 2, 10, 1}
int n = 5, k = 10; //n is number of values, k is the highest value.

That is what I am trying to accomplish...

declare tempPer[k] //k is the age of the oldest person
initiate tempPer[] to 0 //all index of tempPer have value 0.
now everytime we find a age in darrPer which is equivalent to the index in tempPer
the value at that index is increased by 1. And then begin to place the sorted values into sortPerAge.

Member Avatar
VernonDozier
Posting Expert
5,632 posts since Jan 2008
Reputation Points: 2,218 [?]
Q&As Helped to Solve: 768 [?]
Skill Endorsements: 26 [?]
Featured
 
0
 

I suggest using a well known, easy to implement sort like Bubble Sort instead of making your own sort. Add a comment like "Sorting A[] array by age using a bubble sort". That way everyone knows exactly what you're trying to do. The variables are named OK, so we can sort of see what you're doing, but the algorithm's a new one for me. Is this an algorithm you made yourself?

Anyway, unless there's a reason to make your own, I'd implement one of the standard ones. Use whichever you like (bubble, insertion, merge, etc.). Bubble is generally considered the simplest to implement and understand. You won't need the extra C array. And do you need the B array? Or just the A array. Anyway, Bubble Sort takes one array and one temporary object. You'll need to have a way to compare records and swap them. Since you're programming C-Style apparently, don't make any operators, copy constructors, etc.

Anyway, again, if there's no need to make your own sorting algorithm, use one of the standard ones and then, at the very minimum, people will know exactly what you're trying to do, so it's easier to spot any errors.

Question Answered as of 3 Years Ago by VernonDozier and kes166
You
This question has already been solved: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: