Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Well I already read a little about sorting algorithms on wikipedia, the subject seems vast, especially when dealing with some cases where some algos are faster than others.

That might need some quick sum up, but before that, can somebody tell me if there are subjects of game programming where sorting is necessary ? (or optional, for execution time matters).

Maybe in a depth buffer?

share|improve this question

6 Answers 6

up vote 18 down vote accepted

I'm going to say yes, to your question as phrased, but with important caveats.

Yes, you need to know how to sort things in programming game development. There's lots of sorting goes on, in a wide variety of situations. No, you don't need to know the details of how all (or even many) the various sorting algorithms work, it's almost always sufficient to look it up in a reference (online or book) when you need to.

What's important is not the how and why of each algorithm, it's a deeper understanding of why some algorithms work better in some situations. It's understanding exactly which situation you have (do I need to sort in-place, can I insert items in the list cheaply). It's knowing the most common and flexible algorithms, not so much the details of how they work, but more the situations where they should not be used.

And finally, it's knowing when sorting performance is important (when you have many, many items and you need to sort them a lot) and when it's not so important (when you have just a few items, and/or you only need to sort when the list changes). In the latter case, just throw the list through quicksort. If your objects are large, then sort a list of indices to the objects rather than the objects themselves. In the last dozen or so years I've been developing professionally, I can count the number of times I've needed a more tuned or specific sorting algorithm, and it's probably less than 20.

share|improve this answer
2  
did you sort that list of tuned specific algorithms? –  slf Nov 22 '10 at 14:24

Yes, you sort things all the time. One common example is graphics calls.

Whether you need to know how to implement every sorting algorithm off the top of your head is another question, but you should at least be able to answer questions like:

  • What sort do I use if I need an in-place sort with minimal stack overhead? (Iterative or tail-recursive quicksort.)
  • How can I sort a large list of strings as fast as possible? (Burstsort, radix sort, or quick sort depending on architecture.)
  • How do I sort these assets in dependency order? (Topological sort.)
  • I just need to sort some unknown data in a reasonable way? (Timsort, quicksort.)

All of these situations come up in all kinds of software, including games.

Again, you don't need all of these memorized, but you need to be able to open a book of sorting algorithms, read a brief description of each one, and pick the right one. That means understanding time and space (big-O) requirements, and having an idea of how different sorting algorithms work (merging, selecting, swapping).

Sorting algorithms also feature prominently in job interviews; usually the questions are not "implement quicksort", but "here's a description of the kinds of input, what sorting algorithm works well for this?"

share|improve this answer

There are lots of cases where you might need to sort things, depending on what kind of game programming you are doing:

  • Sort opaque objects by distance from camera before drawing (reverse painter's algorithm)
  • Sort transparent triangles by distance from camera before drawing them in reverse order.
  • Topological sort of goal dependency graph to work out a sensible order to attempt to achieve goals in (useful in AI, or in giving automated hints).
  • Sort objects along some co-ordinate for fast collision testing.
  • Sort events by time to work out which one to handle next.
  • Sort objects by unique id to get canonical order for comparison or serialization.
  • Sort profiling statistics to work out which areas would be most profitable to optimize.

It's rare that you'll need to implement your own sort algorithm: generally you'll just pick an appropriate function from a library. But studying and writing sorting algorithms is good general practice for writing and analyzing algorithms, and your knowledge will come in handy when it comes to picking a good algorithm from a library, or spotting the (rare) cases where the special features of your problem mean that you could improve on the generic library routine.

share|improve this answer

Most languages come with a good general purpose quicksort implementation.

They don't necessarily come with implementations of stable sorts, sorts that don't compare values directly, sorts that don't suffer when used on pre-sorted data, sorts that work well on disk-based data, sorts that work better if given lots of memory, sorts that work without requiring any extra memory at all, partial sorts that efficiently sort just a subset of the data, partitions that only sort data relative to a pivot threshold, and so on.

These are all useful from time to time.

share|improve this answer

I'll just add a short answer here: HIGHSCORE table...

share|improve this answer

As a more general answer, even if you never actually write your own sorting algorithm "in the field" (after all, as you've no doubt seen on Wikipedia, your average garden-variety sorting is a problem that's already been solved), sorting is one of the core aspects of computer science that helps in the kind of computational thinking that a programmer needs. Think of it as the "wax on, wax off" that you learn before you realize you can use that skill for karate, too :)

share|improve this answer
1  
"your average garden-variety sorting is a problem that's already been solved" - Not really. Timsort was invented as recently as 2002, burstsort in 2003, etc. I've been hearing "sorting is a solved problem" since I started studying CS in the early 90s, and yet we have so much better sorting algorithms now than then. –  user744 Nov 21 '10 at 10:09
    
Fair enough, Joe. What I meant by "garden-variety" is that, for the purposes of a simple sort of, say, a list of <100 items (as found in a high-score table or inventory item list), you don't need a whole lot of optimization; quicksort or even bubble sort would work just fine and you don't really need to have bleeding-edge sorting algorithms for that. –  Ian Schreiber Nov 24 '10 at 19:45
    
Actually, quicksort is really horrible in those cases, in terms of cost per item. Maybe in the grand scheme of your program it doesn't matter because you only sort it once per day and don't need it done fast, but if I have, say, 1000 lists of 10 items (inventory items of all online players in an MMO, e.g.), applying quicksort 1000 times is one of the worst possible solutions. –  user744 Nov 25 '10 at 15:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.