Loop or sort for layered draw?

Question

Assuming a collection of objects, each of which needs to be drawn at a specific layer, at what point would it (or ever) be better to sort each object by layer rather than looping multiple times and drawing a layer at each pass? More importantly how would you arrive at this conclusion? Bonus points for a sort algorithm you would use if you would sort?

for (obj = each in collection) {
  for (i=0; i<=topLayer; i++) {
    if (obj.layer == i) {
      obj.draw()
    }
  }
}

/* vs. */

function layerCompare(obj1, obj2) {
  return (obj1.layer > obj2.layer)
}

collection.sort(layerCompare) 

for (obj = each in collection) {
    obj.draw()
}

Answer 1

If you loop through every layer and every object, that is O(m*n) where m is number of layers and n is number of objects. However, if you sort the layers ahead of time with something like quicksort, you can sort them in O(n*log(n)) and then draw them in O(n), yielding a total complexity of O(n*log(n) + n) = O(n*log(n)).

So in theory, its always better to sort them. In practice, you would have to benchmark.

EDIT: On second inspection, the cutoff is whether m < log(n). If the number of layers is less than the log of the number of objects, then you should do the double loop, otherwise sort them.

Answer 2

I would maintain a separate collection for each layer (and not have layer as a property of each object), rendering the question moot. Reassigning an object to a different layer (with an add and a remove) would only be (roughly) twice as expensive as changing an object's layer property, and you would completely avoid the cost of either a sort or a bunch of iterations to get the objects in each layer.

Answer 3

If your code is such that not many layers come and go, it makes vastly more sense to always keep your layers sorted. One such way to accomplish that trivially is to make a layer itself a drawable object that can contain objects. At this point, your layering is built into the recursive nature of the layer object itself.

Alternatively, you could just have a layer list which each layer being a single list of objects.

Answer 4

The big question is how smart your sort can be. How often do items get added/removed/change layers? Insertion and Bubble sort (generally considered poor performers) work very well for almost sorted data.

The other question is how much work do you save by sorting? Your rendering function is great for a small number of layers, but gets worse the more layers you have. From a complexity standpoint, you need to consider both the number of layers and the number of items, and possibly the distribution per layer.

If you have a small (small being relative of course) number of layers it might just make sense to have a separate collection (linked list probably) for each layer, and move it to the appropriate layer when it changes.

Answer 5

If the number of layers is fixed, you can use Pigeonhole sort which is an O(n) algorithm. For example, if there are 256 layers numbered 0 through 255, create an array List<Obj>[] a of size 256, then for each object obj in your collection, perform a[obj.layer].add(obj). Finally, iterate through your array back to front and draw your objects (if 0 is back, for (int i = 0; i < a.length; i++) {for (Obj obj : a[i]) {draw(obj);}}

But I agree that maintaining these lists is better than regenerating them all the time. The simplest approach is to store your objects in a set data structure ordered by layer that allows in-order iteration (for example, a TreeSet in Java).