I plan to make my new game and here is a problem I have to solve.

I always put all monsters and objects into one array. In the main cycle the game calls "do_AI(int monster)", where "monster" is the index to this array and this function does anything that is needed for the specific monster.

And here goes my problem - I plan to make an isometric game, so i need to draw the monsters that are behind first and last the monsters that are in front.
So I need really quick to find what monsters to draw in what order

Anybody can help? I'd like not to use classical quicksort (etc) to sort the y value

Is there a way to solve this with another structure as array ? (I mean to solve it faster?)

Thanx for any comment

Maybe a linked list where you add the monsters sorted instead. Or a list of pointers to your array. You sort the list, and use the pointers to know to which monster each makes use.

In the worst case, just use the qsort function to sort the array. It should be faster than what you think.

Unless you have about 10k items in that array using regular array with qsort will not cause any speed problems unless you do something stupid of cource

I would use some sort of priority queue.

Also if your array is mostly sorted something like bubblesort can be much faster than qsort

Having an array of indices and sorting that should already be faster than sorting the array itself (at least if it's an array of objects larger than 4 bytes in size).

That said, I do things slightly differently: I construct a linked list in my main draw loop using insertion sort. That sort takes care of the drawing order (among other things) and I just draw everything in the queue in order once the list is build. Works pretty well and is quite flexible.

My original reason for doing this, by the way, is that I have several types of objects on the screen with their own peculiarities (player character, monsters, treasure, particles, projectiles...). I can either make them all the same type and put them in the same array (which I don't want to do) or do it like this.

The bigger your objects are, the more effective is a linked list in comparison to an array.
But I believe you don't have to care about speed issues in that case. The drawing does mostly need the most performance.

well, i suppose you are right, linked list and sort it ..

(my array has about 100 bytes so i don't have to move all of this.)

Just to clarify, a list implies order. So, you insert elements in the correct order instead of inserting them anywhere, then ordering them

well, that's a good idea ...

cause inserting to drawing is about 1 to 99 percent, so in inserting I could easy handle where to put them..

BUT - my objects are moving, so if I insert it somewhere, I have to move it to another place in my array, as it moves

I thing I'll try to do my array, array of pointers and then simply sort the array when the level is redrawn.
(and take care that the sort is as fast as possible)

Make it work first, optimize it later. If you design things in a good way you will be able to change the way it sorts later on, and get it working soon.

Well, I'm not afraid that this would not work, I've done this hundred times before (in my every game is this monster-array), but the only thing different is the need to have the array sorted

I've done some different sorting algorytms before and know how they work, but I didn't realized the use of a linked array to another array

Another way to do it would be to put a pointer to the actor on the tile on each tile. So when you want to draw stuff, iterate through each tile and draw the tile-sprite and then anything on it (actor). This is easiest to implement if you have "grid-based" movements though. Otherwise you would need to make some evil offset value that changes as the actor moevs around and then at a certain point you move the actor "move" to another tile.

Or you can just use the might % operator (or even & for power-of-2-sized tiles) to determine the current tile for the actor each time it move.

We have recently went over several sorting routines in my C++ class. Most of the time, the teacher just showed us java applications for examples instead of programming everything out in C++.

You might find these websites pretty useful. All the work is done for you, so you just get a quick overview of how each sorting method works.

Links:
http://www.cs.pitt.edu/~kirk/cs1501/animations/Sort2.html
http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html
http://max.cs.kzoo.edu/~abrady/java/sorting/InsertionSort.html

But heres an idea...how about only a partial qsort? That is, instead of compleetly resorting the array, or vector, or whatever it is you want to use each logic step, only sort a small chunk of it. It would prevent the game from getting too slow with a very large number of objects, and who cares if one object breifly appears in front of some other object that it's not supposed to for only 1 frame as they move past each other. Once they are sorted, it's not going back...so it shouldn't cause any flicker. In special cases, you might wish to call a full resort (such as just loading a new room or map). Also, if objects will not just be jumping out everywhere randomly, you will want to choose a sorting algorithm that performs faster as things are more sorted.