qsort and compar

[rcast]

I'm having trouble with the beginners exercises originally posted by Blitz Coder here: http://www.cplusplus.com/forum/articles/12974/

Specifically, I'm having trouble with the "Pancake Glutton" that says I must output each array element, named by index in ascending order:

i.e.
Person 4: ate 10 pancakes
Person 3: ate 7 pancakes
Person 8: ate 4 pancakes
...
Person 5: ate 0 pancakes

I found qsort in the reference guide which works great. I've outputted the list in ascending order, however I cannot seem to produce the person array index for the element that it originally corresponded to. The complexity of the multiple pointers and vague description of the compar function leaves me puzzled.

compar looks like this:

int compar (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

Where the qsort looks like this:

  int n;
  qsort (values, 10, sizeof(int), compar);
  for (n=0; n<10; n++)
     printf ("%d ",person[n]);
  return 0;

I'm having trouble outputting the actual index integer, that the sorted value was stored in.

Here's my code for context, but don't just give me the answer if you can. Explain?

#include "stdafx.h"
#include <iostream>
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */
using namespace std;

#define PEOPLE 10

void doEating(int person[]) {
	for (int i=0; i<PEOPLE; i++){
		cout << "Enter the amount of pancake's ate by person " << i+1 << ": ";
		cin >> person[i];
	}
}

int compar (const void* a, const void* b) {
	return ( *(int*)a - *(int*)b );
}

int printList(int person[]) {
	int n;
	qsort(person, PEOPLE, sizeof(int), compar);
		for (n=0; n<10; n++)
			printf ("%d ",person[n]);
	return 0;
}

int main() {
	int person[PEOPLE];
	cout << "Pancake Glutton" << endl << endl;
	doEating(person);
	printList(person);
}

[cire]

There is a relationship between the person's identifier (which, in this case happens to be his position in the array) and the number of pancakes the person eats. This relationship is shattered when you sort the array.

One possible solution is to make each element of the array a structure which contains both the number of pancakes eaten, and the identifier of the person who ate them.

For instance:

struct person
{
    unsigned identifier ;
    unsigned pancakesEaten ;
};

qsort, by the way, is great if you're programming in C. Not so much if you're programming in C++. You might want to check out std::sort.

http://www.cplusplus.com/reference/algorithm/sort/

[toum]

You need to store the index with the value, so that they get sorted together, for example via a structure:

struct Person
{
    int index;
    int PancakeAmount;
};

Then you just have to declare person as an array of this structure and to modify compar() to sort according to the "PancakeAmount" field.

[rcast]

Sounds like another opportunity to practice using structure. Thanks both.

[rcast]

I've used the suggestions in creating a structure and abandoned the qsort and sort function in exchange for a bubble sort. However, I cannot get the index (represented now by p.id) to print for the correct pancakes eaten (represented by p.pancakes), sorted in order of least to greatest.

Any help? I'm a bit lost in the complexity of my first object.

// 4_PancakeGlutton.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;

#define PEOPLE 10

struct person {
	unsigned id;
	unsigned pancakes;
}p[PEOPLE];

void doEating(person p[]) {
	for (int i=0; i<10; i++){
		p[i].id = i;
		cout << "Enter the amount of pancake's ate by person " << i+1 << ": ";
		cin >> p[i].pancakes;
	}
}

void bubbleSort(person p[]) {
      bool swapped = true;
      int j = 0;
      int tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < PEOPLE - j; i++) {
                  if (p[i].pancakes > p[i + 1].pancakes) {
                        tmp = p[i].pancakes;
                        p[i].pancakes = p[i + 1].pancakes;
                        p[i + 1].pancakes = tmp;
                        swapped = true;
                  }
            }
      }
}

void printList(person p[]) {
	for (int i=0; i<PEOPLE;i++){
		cout << "Pancakes eaten by person " << p[i].id<< ": " << p[i].pancakes << endl;
	}
}


int main() {
	cout << "Pancake Glutton" << endl << endl;
	doEating(p);
	bubbleSort(p);
	printList(p);
}

[cire]

In your sort, the idea is to sort the person objects based on the pancakes members. Not to sort the pancakes members of the person objects.

            if (p[i].pancakes > p[i + 1].pancakes) {
                person temp = p[i] ;
                p[i] = p[i+1] ;
                p[i+1] = temp ;
                swapped = true ;
            }

or better:

            if (p[i].pancakes > p[i + 1].pancakes) {
                std::swap(p[i], p[i+1]) ;
                swapped = true ;
            }

[edit: Formatting mistake]

[rcast]

So close. Success. Thank you sir cire