Problems with sort()

[Somarl]

Hi, i am still trying to do the pancake glutton problem which is really got me stumped now (making me feel like im not cut out for this lark tbh as ive been trying it for a week) however i am having problems making sort work which is slowing me down and not helping me.

Ignore the headers (i use a template thing so i dont have to keep typing int main return 0 and system pause and all the headers etc so i just lumped everything i use, unless this is actually causing sort to not work)

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<Windows.h>
#include<ctime>
#include <cstdlib>
using namespace std;

//*******************************************//


int main()
{
    vector <int> person(9);
    //int a = 0, b = 0;
    cout << "\n Welcome to Pancake Glutton";
    cout << "\n\n\n There are 10 people,";
    
         //This seems to capture the values of "person" nicely
         for (int n=0; n<10; n++)
         {
             cout << "\n Please enter the number eaten by Person " << n << " : ";
             cin >> person[n];
             }
         //This seems to print the values of person just right so i can see whats what
         for (int n=0; n < 10; n++)
         cout << "\nPerson " << n << " ate " << person[n];
         
         //sort the vector from smallest to largest number
         sort(person.begin(), person.end());
         
        //Just for the hell of it, print out the values of the sorted vector to see if it is actually ordering them    
        cout << "\nThis is supposed to be some sort of order which it is apart from the last int in the person vector which seems to be unchanged.";
        cout << "\n\nPerson 0 has value " << person[0] << "\n";
        cout << "Person 1 has value " << person[1] << "\n";
        cout << "Person 2 has value " << person[2] << "\n";
        cout << "Person 3 has value " << person[3] << "\n";
        cout << "Person 4 has value " << person[4] << "\n";
        cout << "Person 5 has value " << person[5] << "\n";
        cout << "Person 6 has value " << person[6] << "\n";
        cout << "Person 7 has value " << person[7] << "\n";
        cout << "Person 8 has value " << person[8] << "\n";
        // by the time it gets to here, looking good so far, all values seem to be in ascending order but wait.....
        cout << "Person 9 has value " << person[9] << "\n";      
        // This last one seems to retain whatever value i inputted without moving it around like it has the others
system ("PAUSE");
return 0;
    }

At the moment i just wanted to see what sort does and see how it changes the vector (i havent even got a clue yet how to make it display person 2 had 16 pancakes or whatever in a for loop, not a clue), however if you run this you will notice is always keeps the last int in the vector the same. The program will only appear to work when person 9 has the highest number, try it without this and person 9 will always be the same and unordered.

What the hell have i done wrong, how can i fix it, if i can at least get past this step then i can move onto the nightmare of trying to make it display who had what in what order. Until then, there is no point because sort isnt even working properly.

By the way i am running this in dev c++ if that makes a difference, i dont think it should.

[sammy34]

Get angry! It helps hehe. I'm no expert, but I think it might help to initialise your vector to size 10 on line 16.

Forgetting about that though, I think we might need to take a step back and look at the way you've approached this. You are using the index numbers to represent your people numbers. When the user inputs the number of pancakes they've eaten, the correct number of pancakes gets stored in the i'th element, where i represents the person number.

When you go and sort it, that mapping goes out the window. The indexes of the vector stay the same, but the values in these indexes would typically be switched around! That means that, before sorting, if person 0 has eaten 8 pancakes, he/she may have eaten 2 pancakes after sorting. Do you see where I'm going with this? I think I'm right (please correct me someone if I'm writing garbage).

I think a simple solution would be to create a struct that stores the person number and the number of pancakes. Now, sorting a collection of these structs is a bit harder, and I'm not too sure about the best way to go. I think the best way would be to define a Comparison function which takes two of these structs, and then pass this function in as a parameter in the sort() function which takes three arguments (http://www.cplusplus.com/reference/algorithm/sort/).

[sammy34]

Oh and by the way, your apparent tenacity with this problem is a good thing, and it probably means that you are cut out for this sort of stuff. I'm sure even the people on here with 1000+ posts had such thoughts once, so stay positive :)

[Somarl]

Thanks very much for the support, i went out of the house for a while to cool my head and stop it from exploding, had a discussion with my friend aswell who is also doing this but a bit stuck on assigning the number eaten to the person number etc.

Anyway, the reason i posted this was for one i saw that sort() seems to have something wrong with it. You are right that the next problem i will face will be whatever person 3 ate now would be different after sorting, its apparent to me now i was going about that all wrong as i would always face that problem, but the fact that sort() refuses to touch the last in the sequence worries me that something so simple has gone wrong. Id love to know what is wrong with it.

Now another thing, i am going to make my vector about 10 big so i can try and ignore the person[0] thing, it is in fact what i ddi at the start but because of the errors i decided to simplify it as much as i could to determine what was wrong with sort(), so after that i will be popping it back to what it was as i do want it to list the persons number from 1-10 rather than 0-9.

Lastly, the way i am trying to do this is avoiding classes and structures as i have not encountered them yet and as part of the beginner exercise program on here it says you can do it without using them. Now your right in that classes/structures is more likely the best way to do it, i think i have seen a solution for it using classes and its great and works very well, but with me its the principle of the matter of not being able to get it to work the simple mans way. I should be able to do it (according to the beginner exercise thing) using knowledge of the following only:

variables, data types, and numerical operators
basic input/output
logic (if statements, switch statements)
loops (for, while, do-while)
arrays

Which in a way i guess i do have (though im not to clever with them just yet :) ) So i am still struggling on a way to make this work by using only those and that sort() method. I suppose i may get it eventually but does anyone know why sort() is ignoring the last input in that vector as that could surely turn out to be a bit of a problem if i use it in another program some other time.

Once again though, thanks very much for the replies, i need help AND encouragement at the moment as im losing hair over it lol :)

[vulee]

//sort the vector from smallest to largest number
         sort(person.begin(), person.end());

I am quite new to C++ as well. Since the API stated as follow. What would be the efficient way to get around this?

1. allocate a vector of 11 elements (seem like the last element is wasted)
2. point to an iterator beyond the last one. e.g. person.end() + 1 (don't know whether it work...)

first, last
Random-Access iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but *not* the element pointed by last.

[dan1973]

Hello Somarl,

I fully sympathize with your pancake predicament. I have, however, after many hours puzzeling come out of the other side. Since i too am an absolute novice and only have a passing knowledge of the areas mentioned in the problem in question - variables, logic, loops etc - those were the only things i used. I don't even know what a vector is! (although i'm going to look it up after this post).

The key thing i found, was a basic understanding of 'arrays'.

As an example, the following code puts 10 numbers into the array. They are in spots array [0], [1] ... .. . ... to array [9]. and then prints them out. It is a good starting point - but read some about arrays. Must say - the satisfaction is in proportion to the effort put in - your heading for some big pay-off - pancakes all round!!!!!!!!!

#include <iostream>

using namespace std;

int main ()
{

int my_array [10];	//sets up an array positions [0] to [9]

int y;				//going to use this to cycle through the customer numbers and through array numbers

for (y = 1; y <=10; y++)	// loop which starts y at 1, lasts till y is 10 and increases y by 1 each pass
	{
	cout << "How many pancakes did customer number " << y << " have? ";
	cin >> my_array[y-1];					//using y-1 because the array entries start at 0 but customers start at 1
	}

for (y =0; y < 10; y++) // needs to continue only until y=9 as this is entry number 10 in the array
	{
	cout << my_array [y] << endl;
	}
return 0;
}

[Somarl]

Thanks for the help folks, very much appreciated, slowly but surely i am getting the hang of this.

Right now i can input values into the vector, print them out, organise them lowest to highest, then print them out reorganised with this:

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<Windows.h>
#include<ctime>
#include <cstdlib>
using namespace std;

//*******************************************//


int main()
{
    vector <int> person(11);
   
    cout << "\n Welcome to Pancake Glutton";
    cout << "\n\n\n There are 10 people,";
    //cout << "Person 10 = " << person[10];
         //This seems to capture the values of "person" nicely
         for (int n=1; n<11; n++)
         {
             cout << "\n Please enter the number eaten by Person " << n << " : ";
             cin >> person[n];
             }
         //This seems to print the values of person just right so i can see whats what
         for (int n=1; n < 11; ++n)
         cout << "\nPerson " << n << " ate " << person[n];
         
         //sort the vector from smallest to largest number
         sort(person.begin()+1, person.begin()+11);
                
        //Just for the hell of it, print out the values of the sorted vector to see if it is actually ordering them    
        cout << "\n\nPerson 1 has value " << person[1] << "\n";
        cout << "Person 2 has value " << person[2] << "\n";
        cout << "Person 3 has value " << person[3] << "\n";
        cout << "Person 4 has value " << person[4] << "\n";
        cout << "Person 5 has value " << person[5] << "\n";
        cout << "Person 6 has value " << person[6] << "\n";
        cout << "Person 7 has value " << person[7] << "\n";
        cout << "Person 8 has value " << person[8] << "\n";
        cout << "Person 9 has value " << person[9] << "\n";
        cout << "Person 10 has value " << person[10] << "\n";    
        //This does order them with no errors providing input is reasonable (like no minus entries)  
       
    system ("PAUSE");
return 0;
    }

Now this is all very well but i am struggling to attach a value to the person and keep it that way so that it sticks with it. I know why its doing it but i cant come up with a different way of doing it so it retains the person number to the value.

At the moment i get this:

Person 1 = 2
Person 2 = 6
Person 3 = 4 etc

Then it orders itself and prints

Person 1 = 2
Person 2 = 4
Person 3 = 6

Instead of what it should be which is

Person 1 = 2
Person 3 = 4
Person 2 = 6 etc etc.

Like i said i just cant seem to think of a way to make 2 values that bind themselves to each other so ordering them orders one value (the amount) but drags another value (the person number) along with it.

Sorry for the horrible explanation but i cant think of another way to write it. Im thinking i have to scrap what i have started in order to get it to do what i need to because the position of vector [1] (or whatever) is always going to remain, shuffling one set of numbers will not shuffle that with it, i understand this, but cant think how to start.

edit: the code above is not meant to deal with the order of the person number being attached to the value that the vector holds, just to point out that i can organise that data from lowest to highest, i realise that i havent put in a way to make it come out right.

[m4ster r0shi]

sammy34 said some very important things in his first post...

You are using the index numbers to represent your people numbers.

When you go and sort it, that mapping goes out the window.

I think a simple solution would be to create a struct that
stores the person number and the number of pancakes.

A simple implementation of what sammy34 suggests could be the following:

#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct PersonInfo
{
       int id;
       int pancakes;
};

bool is_less(const PersonInfo & p1, const PersonInfo & p2)
{
     return p1.pancakes<p2.pancakes;
}

void input(vector<PersonInfo> & p);
void output(vector<PersonInfo> & p);

const int number_of_people=10;

int main()
{
    vector <PersonInfo> person_info(number_of_people);
    int n;
   
    cout << "Welcome to Pancake Glutton" << endl;
    cout << "There are " << number_of_people << " people\n" << endl;
    
    //get the data
    input(person_info);
    
    //print unsorted data
    cout << "\nprinting unsorted data..." << endl;
    output(person_info);
    
    //do the sorting
    sort(person_info.begin(), person_info.end(),is_less);
           
    //print sorted data
    cout << "\nprinting sorted data..." << endl;
    output(person_info);
           
    system ("pause");
    return 0;
}

void input(vector<PersonInfo> & p)
{ 
    int size=p.size(); 
    for (int n=0; n<size; n++)
    {
        cout << "Please enter the number eaten by Person " << n+1 << ": ";
        cin >> p[n].pancakes;
        p[n].id=n+1;
    }
}

void output(vector<PersonInfo> & p)
{
    int size=p.size();   
    for (int n=0; n<size; n++)
    {
        cout << "Person " << p[n].id << " ate ";
        cout << p[n].pancakes << " pancake(s)!" << endl;
    }
}

[kempofighter]

The root cause of the original problem was that you created a vector of 9 elements but tried to access a 10th element which causes undefined behavior. I do not think that anyone pointed this out to you.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<Windows.h>
#include<ctime>
#include <cstdlib>
using namespace std;

//*******************************************//


int main()
{
    vector <int> person(9); // 9 elements.  Can only be indexed with 0-8
    //int a = 0, b = 0;
    cout << "\n Welcome to Pancake Glutton";
    cout << "\n\n\n There are 10 people,";

    //This seems to capture the values of "person" nicely
    // this loop is undefined behavior!  Person[9] doesn't exist
    for (int n=0; n<10; n++)
    {
	cout << "\n Please enter the number eaten by Person " << n << " : ";
	cin >> person[n];
    }
    //This seems to print the values of person just right so i can see whats what
    for (int n=0; n < 10; n++)
	cout << "\nPerson " << n << " ate " << person[n];

    //sort the vector from smallest to largest number
    // sorts persons 0-8 because there are 9 elements (0..8)
    sort(person.begin(), person.end());

    //Just for the hell of it, print out the values of the sorted vector to see if it is actually ordering them    
    cout << "\nThis is supposed to be some sort of order which it is apart from the last int in the person vector which seems to be unchanged.";
    cout << "\n\nPerson 0 has value " << person[0] << "\n";
    cout << "Person 1 has value " << person[1] << "\n";
    cout << "Person 2 has value " << person[2] << "\n";
    cout << "Person 3 has value " << person[3] << "\n";
    cout << "Person 4 has value " << person[4] << "\n";
    cout << "Person 5 has value " << person[5] << "\n";
    cout << "Person 6 has value " << person[6] << "\n";
    cout << "Person 7 has value " << person[7] << "\n";
    cout << "Person 8 has value " << person[8] << "\n";
    // by the time it gets to here, looking good so far, all values seem to be in ascending order but wait.....
    // this is undefined behavior!  Person[9] doesn't exist
    cout << "Person 9 has value " << person[9] << "\n";      
    // This last one seems to retain whatever value i inputted without moving it around like it has the others
    system ("PAUSE");
    return 0;
}

[kempofighter]

Now in your later examples you seem to have tried something different with sorting and looping due to not understanding the root cause of the original problem. The call to sort was correct in your original code. the problem was your looping and cout statements.

In your latest example you are starting your loops at n=1 for some reason.

// This should not be necessary.  You misunderstood the original problem.
sort(person.begin()+1, person.begin()+11);

// works just fine and sorts all 11 elements.  update your for loops to start at n=0 and end
// when n < person.size()
sort(person.begin(), person.end()); 

Also get in the habit of using the vector interface in your loops like so.

std::vector<int> persons(11);

// Later when you loop

for(int n = 0, int size(persons.size()); n < size; ++n)
{
   std::cout << persons[n];
}

// alternatively use iterators
for(std::vector<int>::iterator pos(persons.begin()); pos != persons.end(); ++pos)
{
   std::cout << *pos;
}

[kempofighter]

Last but not least, make sure that you are getting valid user input.
http://www.parashift.com/c++-faq-lite/input-output.html#faq-15.3

[m4ster r0shi]

@kempofighter
did you bother to see the previous posts?

kempofighter:

The root cause of the original problem was that you created a vector of 9 elements but tried to access a 10th element which causes undefined behavior. I do not think that anyone pointed this out to you.

sammy34:

I'm no expert, but I think it might help to initialise your vector to size 10 on line 16.

And then dan1973 even gave him an example on using arrays...

His problem wasn't the size of the array, he fixed that a while ago. His problem was that he didn't have something to hold each individual's id. Where exactly in your solution do you propose something that solves this matter?...

[Zhuge]

[/quote=kempofighter]struct PersonInfo
{
int id;
int pancakes;
};[/quote]
Here, at least.

[m4ster r0shi]

@Zhuge:
um... in case you didn't notice yet... I am the one who wrote that... -.-

[dan1973]

Small suggestion,

If one had one array which filled up with the pancake numbers... THEN

Another array with the customer numbers... THEN

Perform a simple substitution sort on both arrays to order them from say smallest to largest ....

I know you have your heart set on solving things with the 'vector' , however take a look at this - it uses only those basic forms asked for in the problem itself and has the added bonus of clarity - very important at the early stages.

#include <iostream>

using namespace std;

int main ()
{
int array_amount[10]; //one for no. of things
int array_person[10]; //one for person no.

int y; 				//integer to use to cycle through positions
int temp;			//general purpose holding integer

int smallest_position;	//integer to be used in sorting to indicate position in  array of smallest amount
int current_position;	//integer to be used in sorting to indicate the position being campared to smallest position

for (y =0; y <=10; y++)		
	{
	array_person[y] = y+1;	// places consecutive numbers 1-10 in an array
	}
for (y = 1; y <=10; y++)	// loop which starts y at 1, lasts till y is 10 and increases y by 1 each pass
	{					
	cout << "How many pancakes did customer number " << y << " have? ";
	cin >> array_amount[y-1];	//places amounts into a parallel, same size array
	}

	//now need to sort these arrays in the same way so as to keep a link between customer number and amount.
	//you can find many different simple 'algorithms' to order arrays. I think the following suited me as it 
	//was the simplest to grasp. 
	
for (smallest_position = 0; smallest_position < 9; smallest_position++) 
	{
		for (current_position = smallest_position + 1; current_position < 10; current_position++)
		{
		if (array_amount[current_position] < array_amount[smallest_position]) // if this is the case, need to swap places
			{
			temp = array_amount[smallest_position];								//
			array_amount[smallest_position] = array_amount[current_position];	// with each pass, any smaller integers are 
			array_amount[current_position] = temp;								// placed into smallest position in the array
		
			temp = array_person[smallest_position];								//need to remember to do the same substitution with 
			array_person[smallest_position] = array_person[current_position];	//the array of customer numbers  
			array_person[current_position] = temp;	
			}
		}
	}

for (y = 9; y >= 0; y--)
	{
	cout << "person no. " << array_person[y] << " ordered " << array_amount[y] << " pancakes." << endl;
	}
return 0;
}

I will be watching the vector development with interest as I'm pretty certain there's a solution there somewhere!

Good luck

Dan

[sammy34]

+1 to Dan's "small" suggestion. I like that it uses only what is asked in the problem. One could further optimise this with a better sort implementation, but that's beyond scope for this problem.

[kempofighter]

@kempofighter
did you bother to see the previous posts?

In the original post, the OP complained that sort wasn't sorting the last element. That wasn't true at all. The problem is that the OP was trying to access a 10th element and print the value but there was no 10th element in the container so the behavior was undefined.

Not one of you pointed out that there was undefined behavior in the original program due to accessing 1 element beyond the end of the array. I thought it might be useful to point that out since nobody else did. I have no problem with any of the other suggestions. I agree that he should use a data structure but saw no point in writing what others had already written. Those are the kinds of problems that occur when you hard code numbers throughout the program instead of justing the size member function of the container or container iterators. The suggestions that I made are all still valid suggestions in addition to the other suggestions of using the data structure. There is nothing wrong with using a regular c-array either if that is what you would prefer. It is a fairly simple program.

There never really was any problem with the std::sort, therefore there isn't any optimization that is needed. If you choose to use struct instances then it might be better to use a std::list which has its own sort member function. sorting a c-array won't be any more or less efficient than sorting a std::vector since both are contiguous arrays of data.

[m4ster r0shi]

dan1973++;

your small suggestion made me think "how else can this be done without structs and vectors?..." and I came up with this one:

#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    unsigned long data[10];
    unsigned short temp;
    int i;
    
    //get data
    for (i=0; i<10; i++)
    {
        cout << "enter pancakes eaten by person " << i+1 << ": ";
        cin>>temp;
        
        //I set the higher 16 bits to the number of pancakes
        //and the lower 16 bits to the person id
        //so that when I sort it later it is sorted by
        //the number of pancakes eaten
        data[i]=(temp<<16)+i+1;
    }
    
    //print unsorted data
    cout << "\nunsorted data..." << endl;
    for (i=0; i<10; i++)
    {
        cout << "person " << (data[i]&65535);
        cout << " ate " << (data[i]>>16) << " pancake(s)!" << endl;
    }
    
    //sort
    sort(data,data+10);
    
    //print sorted data
    cout << "\nsorted data..." << endl;
    for (i=0; i<10; i++)
    {
        cout << "person " << (data[i]&65535);
        cout << " ate " << (data[i]>>16) << " pancake(s)!" << endl;
    }
    
    system("pause");
    return 0;
}

[helios]

What if sizeof(long)<4?

[m4ster r0shi]

What if sizeof(long)<4?

can't happen. ISO forbids it. That's why I used long and not int. sizeof(int) can be less than 4