How to sort array elements?

[WyntrHeart]

I am learn C++ on my own using the tutorial on this site. I am doing the exercises I found here http://www.cplusplus.com/forum/articles/12974/ and I am stuck on the one called "Pancake Glutton":

"Write a program that asks the user to enter the number of pancakes eaten for breakfast by 10 different people (Person 1, Person 2, ..., Person 10)
Once the data has been entered the program must analyze the data and output which person ate the most pancakes for breakfast.

★ Modify the program so that it also outputs which person ate the least number of pancakes for breakfast.

★★★★ Modify the program so that it outputs a list in order of number of pancakes eaten of all 10 people."

I have read everything up to "Data Structures" in the C++ Tutorial but I didn't see any way to sort array elements and I cant figure out how to do it on my own. The only way I can figure out would be a giant series of "if else" statements to check each element against all the other element until it finds one that is greater than all the others, is that what I should do?

[Josue Molina]

Hint: if you find yourself using lots of conditionals, consider using a loop.

[Duthomhas]

Sorting things is not an obvious kind of thing to do.

The very simplest method is what people normally do, it is called a selection sort.

    • Find the smallest number in your list of numbers. Copy it to the output array.

    • Find the next smallest number in your list of numbers. Copy it to the output array.

    • Repeat until you have no more numbers to sort.

I'm working on the explanation of other basic sorting algorithms at the FAQ right now. (Currently updating the counting sort -- don't use that one, it takes some effort both to implement and to understand.)

http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/

Two other sorting algorithms you might want to play with are bubble sort and insertion sort. (They are explained in the FAQ.)


If you don't want to mess with any of that, you can use the STL sorting algorithm:

#include <algorithm> 

int xs[ 1000 ];
int number_of_xs = 0;

// (fill xs[] with elements here, and update 'number_of_xs' to the correct value)
...

// Time to sort the xs
sort( xs, xs + number_of_xs );

Hope this helps.

[WyntrHeart]

thanks Josue, I figured out how to get the highest number with a loop. I cant figure out how to output them all in order for the four stars though

[tntxtnt]

- create a struct to hold a person's id and how many pancakes he/she eats.
- store 10 instances of that struct in an array.
- sort that array (descending) by pancakes eaten, using 1 of these sorting algorithms: insertion sort, selection sort, bubble sort.
http://en.wikipedia.org/wiki/Insertion_sort
http://en.wikipedia.org/wiki/Selection_sort
http://en.wikipedia.org/wiki/Bubble_sort

or use the build-in std::sort/std::stable_sort functions, which you may not understand how they work yet...

[Duthomhas]

I've been working very hard to make the FAQ much more readable than Wikipedia.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/insertion-sort/
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/bubble-sort/

To sort a structure, you'll need to have a function to compare two elements:

struct person
  {
  string   name;
  unsigned pancakes_eaten;
  };

bool compare_pancakes_eaten( const person& a, const person& b )
  {
  return a.pancakes_eaten < b.pancakes_eaten;
  }

person people[ 100 ];
unsigned number_of_people = ...

sort( people, people + number_of_people, compare_pancakes_eaten );

Hope this helps.

[WyntrHeart]

Since C++ has built in sorting algorithms is it worth the effort to learn sorting methods?

[Josue Molina]

Is it worth the effort to learn to multiply if we have calculators?

[WyntrHeart]

"Is it worth the effort to learn to multiply if we have calculators?"

Sometimes you don't have a calculator available when you need to multiply. I will always have a sorting algorithm available when I need to sort arrays so the comparison is invalid.

[Josue Molina]

What if your employer programs in Python?

[WyntrHeart]

Aren't there sorting algorithms written in Python?

[Josue Molina]

^ That's the response I was fishing for (it's really easy to sort in Python).

It seems you're results-oriented. In that case, it's unnecessary to study sorting algorithms. If you want to be a well-rounded computer scientist, however, I'd recommend it.

[LB]

If you are going to be an engineer (e.g. Computer Engineer) then it is important to learn sorting algorithm implementations. If you are going to be a scientist (e.g. Computer Scientist) then learning the implementations is just a fun thing to do in your spare time and it might help you be a better thinker.

EDIT: And if you don't know which you'll be, then I'd say better safe than sorry and learn the implementations of sorting algorithms.

But honestly, 99% of the time you will use the language's built-in sorting functions.

[Josue Molina]

L B,

I differ.

I would say that studying sorting algorithms is imperative for serious (often theoretical) computer scientists and unnecessary for programmers (code monkeys).

A CS grad student in algorithms and complexity will most likely begin their journey by studying the time complexities of the canonical sorting algorithms.

[WyntrHeart]

I think I will learn about sorting methods later then. I like to exercise my mind, but for now I will use the built in algorithm so I can continue learning the basics of the C++ language.

EDIT: My intent is primarily to learn to make video games so I would consider myself more of an aspiring artist than aspiring scientist. I still want to learn computer science but at this point I am more focused on what I need to learn.