Fast sorting where order seldom changes

Question

I'm working on a 2D game with a scrolling view (think Red Alert or Zelda) but I'm stuggling with the drawing.

Basically there are two types of objects that are drawn on the map. Some have fixed positions (like trees and buildings) and others move around (players, enemies, flying arrows).

For things to appear in front of each other in a correct way they need to be drawn in a specific order (distant objects first and work towards the "camera").

Right now I'm sorting the list of all objects (both kinds) every time the game updates (100 times per second) and it feels a like a huge waste of CPU time. The order of the objects very seldom changes, and when they do they usually only move one position up or down in the list.

Another issue is that only the objects that are actually on screen needs to be be considered. As the maps could become quite large with 1000s of objects I don't want to sort them all 100 times per second.

How would you suggest I solve this?

Answer 1

Bubble Sort's best case is when the elements are already sorted. You'll get O(n) comparisons in that case. According to Wikipedia:

In computer graphics it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n).

But it's considered to be a "bad" algorithm for a variety of reasons mentioned in the linked article. You may want to profile the difference between it and Insertion Sort (also O(n) for sorted lists) to see which is faster in practice.

Another option is to use a data structure that keeps the sorted items in it, and which gets notified when an item's position changes. If objects don't move around much compared to how often they get re-drawn, that would save a lot of processing time since you'd only have to re-sort the elements whose position has changed, you could avoid re-sorting at all until at least one element has moved.

Answer 2

Keep track of which objects are on screen in a vector and add newly visible objects at the end of it. Use bubble sort or insertion sort for sorting. This is increadably inefficient for random data, but ~O(n) for almost sorted data.