Pancake Gluton Problem

[anzhit]

I was attempting the pancake glutton problem http://www.cplusplus.com/forum/articles/12974/ the last part where we need to sort the people. After lots of thinking i came up with the below code it works fine but i was wondering whether there is a more efficient way and or ways to improve my code.

  #include <iostream>
using namespace std;

struct PersonPancake
{ int name ;
  int pc   ;
};

PersonPancake person[10] ;

// using an insertion sort algorithm
int findSmallestRemainingElement (PersonPancake array[], int size, int index);
void swap (PersonPancake array[], int first_index, int second_index);

void sort (PersonPancake array[], int size)
     {
        for ( int i = 0; i < size; i++ )
           {
             int index = findSmallestRemainingElement( array, size, i );
             swap( array, i, index );
               }
        }
int findSmallestRemainingElement (PersonPancake array[], int size, int index)
    {
       int index_of_smallest_value = index;
       for (int i = index + 1; i < size; i++)
          {
            if ( array[ i ].pc < array[ index_of_smallest_value ].pc )
                  {
                    index_of_smallest_value = i;
                     }
              }
        return index_of_smallest_value;
    }
void swap (PersonPancake array[], int first_index, int second_index)
    {
        PersonPancake temp = array[ first_index ];
        array[ first_index ] = array[ second_index ];
        array[ second_index ] = temp;
    }

int main()
{ for(int i = 0 ;i<10;i++)
   {
    cout << "Enter number of cakes eaten by person " <<i+1<<": " ;
    cin>>person[i].pc ;
    person[i].name = i+1 ;
    }
  sort(person, 10) ;

  for(int i = 0 ; i<10 ; i++)
  {
    cout<<"Person "<<person[i].name<<" ate "<<person[i].pc<<" pancakes"<< endl ;
  }
}

[nkendra]

Here are my comments:

1 - Don't use globals
The person global is only used in main anyway, but globals should be avoided in general as the make code less modular (and anti object oriented programming), making it harder to reuse code. Global variables can also lead to subtle bugs beyond naming conflicts.

2 - STL algorithms and containers
The swap and sort functions look fine. The Standard Template Library (STL) defines all of these functions, also. It's very good to implement these yourself in order to learn the basics of the language. It's also very important to learn what is already defined in the STL because it will save you time and you will come across them when reading more advanced code. If you want to become a really good C++ programmer, try to learn and incorporate the stl and standard library as much you can.

Check out:
http://www.cplusplus.com/reference/algorithm/swap/
http://www.cplusplus.com/reference/algorithm/sort/

Also, use std::vector instead of an array. Vectors are awesome.

I highly suggest trying to rewrite your code using std::sort because it will push you to learn more advanced techniques. Try using vector first, then swap, then sort; and watch your code shrink!

3 - Function declaration/definition style
It's generally considered good style to put the function declarations at the top (just as you did) and put the definitions after main(), and higher-level functions above lower-level functions. This means helper functions come after functions that use those helper functions, which you did anyway.

If you have trouble using std::sort() or other std things, just repost.

[giblit]

http://www.cplusplus.com/forum/beginner/104532/

[anzhit]

thanks nkendra ill try learning the sort function and vectors

[anzhit]

i was trying using vectors but couldnt figure out how to load data in to the vector as i am using a vector of a structure ??

[nkendra]

A vector of whatever size can be created by passing a size to the constructor.

int main()
{
   vector<PersonPancake> person(10); / / make 10 persons
   for(int i = 0 ;i<10;i++)
   {
    cout << "Enter number of cakes eaten by person " <<i+1<<": " ;
    cin>>person[i].pc ;
    person[i].name = i+1 ;
    }
  //.... 

// Or you can add data to the vector as you go:

int main()
{
   vector<PersonPancake> person; // make an empty vector
   for(int i = 0 ;i<10;i++)
   {
    cout << "Enter number of cakes eaten by person " <<i+1<<": " ;
    PersonPancake p;
    cin>>p.pc ;
    p.name = i+1 ;
    person.push_back(p)
    }
  //.... 

The function declarations would have to change too.

// make sure to put the & after the vector declaration in order to pass by reference.
int findSmallestRemainingElement (vector<PersonPancake>& array, int size, int index);

void swap (vector<PersonPancake>& array, int first_index, int second_index)

[anzhit]

while using arrays i didnt have to use pass by reference then why do i have to do so using vectors ??
Also i couldnt figure out how to use the standard sort function (havent read about it yet)
Thanks for the help !!

[nkendra]

std::sort would be called in this way:

sort(person.begin(), person.end());

std::sort takes a range to sort over so we give it an iterator (like a pointer) to the beginning and end of the vector. Now, you're probably running into a problem with the comparing of PersonPancake objects. Sort needs a way to determine if one object is less than another object. This is already defined for built in types like integers but when a new class or structure is made (PersonPancake in this case), no default comparison exists.

We can solve this two ways: we can supply std::sort with a comparison functor; or define a less than operator (operator<) for PersonPancakes.

First, the simple way: create the less than operator

bool operator<(const PersonPancake& p1, const PersonPancake& p2)
{
    return p1.pc < p2.pc;
}
//...
sort(person.begin(), person.end());

Second, the more complicated but probably more correct way, a functor:

// ..outside of main, probably right below struct PersonPancake{}
struct LessPancakesFunctor
{
    bool operator()(const PersonPancake& p1, const PersonPancake& p2)
    {
        return p1.pc < p2.pc;
    }
};
//...
// create a LessPancakeFunctor and pass it as a comparison for sort to use
sort(person.begin(), person.end(), LessPancakesFunctor());

Functors come up a lot in advanced C++ programming. This is pretty complicated stuff, especially hard when first starting out.

Oh, you also need to #include <algorithm>

[nkendra]

C++ has two ways of passing function arguments: by value (which is the default way) and by reference.

When passing by value, a new copy is constructed and handed over to the function. Any modifications made to the value only affect the functions copy and not the original.

When passing by reference, no copy is made and any changes made to the value inside the function, affect the original. This is really important for functions like your sort, because you want the changes to affect the original object and not just some copy.

Pointers are weird and confuse a lot of programmers - even experienced programmers who haven't used C or C++ in a while.

Under the hood, PersonPancake person[] is the same as PersonPancake* person. And person[4] is the same as *(person+4). Why does this matter? Well, when PersonPancake array[] is passed to a function, it's the same as passing a pointer and a pointer is very close to the same thing as a reference. There are important distinctions between references and pointers which I'm sure other programmers reading this post could criticize. But, in the spirit of keeping things simple, passing an array is just like passing by reference.

So when to pass by reference and when to pass by value is something to keep in mind.